Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Inhaltsverzeichnis

• 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.