Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques: 8th International Workshop on Approximation Algorithms for . Computer Science and General Issues)

Chekuri, Chandra [Editor]; Jansen, Klaus [Editor]; Rolim, José D.P. [Editor]; Trevisan, Luca [Editor];

ISBN 10: 3540282394 / ISBN 13: 9783540282396

Editore: Springer, 2005

Riguardo questo articolo

Ex-library paperback in very nice condition with the usual markings and attachments. Except for library markings, interior clean and unmarked. Tight binding. Codice articolo UTD14a17867

Dati bibliografici

Titolo: Approximation, Randomization and ...

Casa editrice: Springer

Data di pubblicazione: 2005

Legatura: Paperback

Condizione: Very Good

Descrizione articolo

Riassunto:

volume contains 20 contributed papers selected by the APPROX P- gram Committee out of 50 submissions, and 21 contributed papers selected by the RANDOM Program Committee out of 51 submissions.

Contenuti:

Contributed Talks of APPROX.- The Network as a Storage Device: Dynamic Routing with Bounded Buffers.- Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT.- What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs.- A Rounding Algorithm for Approximating Minimum Manhattan Networks.- Packing Element-Disjoint Steiner Trees.- Approximating the Bandwidth of Caterpillars.- Where’s the Winner? Max-Finding and Sorting with Metric Costs.- What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization.- The Complexity of Making Unique Choices: Approximating 1-in-k SAT.- Approximating the Distortion.- Approximating the Best-Fit Tree Under L p Norms.- Beating a Random Assignment.- Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints.- Approximation Algorithms for Network Design and Facility Location with Service Capacities.- Finding Graph Matchings in Data Streams.- A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses.- Efficient Approximation of Convex Recolorings.- Approximation Algorithms for Requirement Cut on Graphs.- Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems.- Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy.- Contributed Talks of RANDOM.- Bounds for Error Reduction with Few Quantum Queries.- Sampling Bounds for Stochastic Optimization.- An Improved Analysis of Mergers.- Finding a Maximum Independent Set in a Sparse Random Graph.- On the Error Parameter of Dispersers.- Tolerant Locally Testable Codes.- A Lower Bound on List Size for List Decoding.- A Lower Bound for Distribution-Free Monotonicity Testing.- On Learning Random DNF Formulas Under the Uniform Distribution.- Derandomized Constructions of k-Wise (Almost) Independent Permutations.- Testing Periodicity.- The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem.- The Online Clique Avoidance Game on Random Graphs.- A Generating Function Method for the Average-Case Analysis of DPLL.- A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas.- Mixing Points on a Circle.- Derandomized Squaring of Graphs.- Tight Bounds for String Reconstruction Using Substring Queries.- Reconstructive Dispersers and Hitting Set Generators.- The Tensor Product of Two Codes Is Not Necessarily Robustly Testable.- Fractional Decompositions of Dense Hypergraphs.