Approximation Algorithms for Combinatorial Optimization: 5th International Workshop, APPROX 2002 Rome, Italy, September 17–21, 2002 Proceedings

✍ Scribed by Yuval Rabani (auth.), Klaus Jansen, Stefano Leonardi, Vijay Vazirani (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2002
• Tongue: English
• Leaves: 279
• Series: Lecture Notes in Computer Science 2462
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002, held in Rome, Italy in September 2002.
The 20 revised full papers presented were carefully reviewed and selected from 54 submissions. Among the topics addressed are design and analysis of approximation algorithms, inapproximability results, online problems, randomization techniques, average-case analysis, approximation classes, scheduling problems, routing and flow problems, coloring and partitioning, cuts and connectivity, packing and covering, geometric problems, network design, and applications to game theory and other fields.

✦ Table of Contents

Search and Classification of High Dimensional Data....Pages 1-2
Bicriteria Spanning Tree Problems....Pages 3-4
Improved Approximation Algorithms for Multilevel Facility Location Problems....Pages 5-13
On Constrained Hypergraph Coloring and Scheduling....Pages 14-25
On the Power of Priority Algorithms for Facility Location and Set Cover....Pages 26-39
Two Approximation Algorithms for 3-Cycle Covers....Pages 40-50
Approximation Algorithms for the Unsplittable Flow Problem....Pages 51-66
1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor....Pages 67-80
Typical Rounding Problems....Pages 81-93
Approximating Min-sum Set Cover....Pages 94-107
Approximating Maximum Edge Coloring in Multigraphs....Pages 108-121
Approximating the Complement of the Maximum Compatible Subset of Leaves of k Trees....Pages 122-134
A 27/26-Approximation Algorithm for the Chromatic Sum Coloring of Bipartite Graphs....Pages 135-145
Facility Location and the Geometric Minimum-Diameter Spanning Tree....Pages 146-160
Improved Approximation Algorithms for the Partial Vertex Cover Problem....Pages 161-174
Minimum Restricted Diameter Spanning Trees....Pages 175-184
Hardness of Approximation for Vertex-Connectivity Network-Design Problems....Pages 185-199
Routing and Admission Control in Networks with Advance Reservations....Pages 200-214
Improved Approximation Algorithms for Metric Facility Location Problems....Pages 215-228
Complexity of Makespan Minimization for Pipeline Transportation of Petroleum Products....Pages 229-242
Primal-Dual Algorithms for Connected Facility Location Problems....Pages 243-255
....Pages 256-270

✦ Subjects

Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Operations Research, Mathematical Programming