Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings

640 Seiten, Taschenbuch

Kurzbeschreibung des Verlags

Contributed Talks of APPROX.- Approximation Algorithms and Hardness for Domination with Propagation.- A Knapsack Secretary Problem with Applications.- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem.- Improved Approximation Algorithms for the Spanning Star Forest Problem.- Packing and Covering ?-Hyperbolic Spaces by Balls.- Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems.- Two Randomized Mechanisms for Combinatorial Auctions.- Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs.- Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows.- Stochastic Steiner Tree with Non-uniform Inflation.- On the Approximation Resistance of a Random Predicate.- Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to ?1 Embeddability of Negative Type Metrics.- Optimal Resource Augmentations for Online Knapsack.- Soft Edge Coloring.- Approximation Algorithms for the Max-Min Allocation Problem.- Hardness of Embedding Metric Spaces of Equal Size.- Coarse Differentiation and Multi-flows in Planar Graphs.- Maximum Gradient Embeddings and Monotone Clustering.- Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems.- Encouraging Cooperation in Sharing Supermodular Costs.- Almost Exact Matchings.- Contributed Talks of RANDOM.- On Approximating the Average Distance Between Points.- On Locally Decodable Codes, Self-correctable Codes, and t-Private PIR.- A Sequential Algorithm for Generating Random Graphs.- Local Limit Theorems for the Giant Component of Random Hypergraphs.- Derandomization of Euclidean Random Walks.- High Entropy Random Selection Protocols.- Testingst-Connectivity.- Properly 2-Colouring Linear Hypergraphs.- Random Subsets of the Interval and P2P Protocols.- The Cover Time of Random Digraphs.- Eigenvectors of Random Graphs: Nodal Domains.- Lower Bounds for Swapping Arthur and Merlin.- Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects.- On Estimating Frequency Moments of Data Streams.- Distribution-Free Testing Lower Bounds for Basic Boolean Functions.- On the Randomness Complexity of Property Testing.- On the Benefits of Adaptivity in Property Testing of Dense Graphs.- Slow Mixing of Markov Chains Using Fault Lines and Fat Contours.- Better Binary List-Decodable Codes Via Multilevel Concatenation.- Worst-Case to Average-Case Reductions Revisited.- On Finding Frequent Elements in a Data Stream.- Implementing Huge Sparse Random Graphs.- Sublinear Algorithms for Approximating String Compressibility.

• Reihe: Lecture Notes in Computer Science
• Themen: Informatik und Informationstechnologie Informatik Theoretische Informatik Mathematik für Informatiker
• ISBN: 9783540742074
• Sprache: Englisch
• Erscheinungsdatum: 07.08.2007
• Größe: 235 x 155 mm
• Verlag: Springer
• Herausgegeben von: Klaus Jansen, José D. P. Rolim, Moses Charikar, Omer Reingold