Approximation Algorithms for Combinatorial Optimization: Third International Workshop, APPROX 2000 Saarbrücken, Germany, September 5–8, 2000 Proceedings

Sanjeev Arora (auth.), Klaus Jansen, Samir Khuller (eds.)3540679960, 9783540679967

This book constitutes the refereed proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2000, held in Saarbr?cken, Germany in September 2000. The 22 revised full papers presented together with four invited contributions were carefully reviewed and selected from 68 submissions. The topics dealt with include design and analysis of approximation algorithms, inapproximibility results, on-line 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 various applications.

---

Table of contents :
Approximation Algorithms That Take Advice….Pages 1-1
Instant Recognition of Polynomial Time Solvability, Half Integrality, and 2-Approximations….Pages 2-12
Scheduling under Uncertainty: Optimizing against a Randomizing Adversary….Pages 15-26
Approximation Algorithms for Facility Location Problems….Pages 27-32
An Approximation Algorithm for MAX DICUT with Given Sizes of Parts….Pages 34-41
Maximizing Job Benefits On-Line….Pages 42-50
Variable Length Sequencing with Two Lengths….Pages 51-59
Randomized Path Coloring on Binary Trees….Pages 60-71
Wavelength Rerouting in Optical Networks, or the Venetian Routing Problem….Pages 72-83
Greedy Approximation Algorithms for Finding Dense Components in a Graph….Pages 84-95
Online Real-Time Preemptive Scheduling of Jobs with Deadlines….Pages 96-107
On the Relative Complexity of Approximate Counting Problems….Pages 108-119
On the Hardness of Approximating NP Witnesses….Pages 120-131
Maximum Dispersion and Geometric Maximum Weight Cliques….Pages 132-141
New Results for Online Page Replication….Pages 144-154
Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses….Pages 155-166
Approximation Algorithms for a Capacitated Network Design Problem….Pages 167-176
An Approximation Algorithm for the Fault Tolerant Metric Facility Location Problem….Pages 177-182
Improved Approximations for Tour and Tree Covers….Pages 184-193
Approximating Node Connectivity Problems via Set Covers….Pages 194-205
Rectangle Tiling….Pages 206-213
Primal-Dual Approaches to the Steiner Problem….Pages 214-225
On the Inapproximability of Broadcasting Time….Pages 226-237
Polynomial Time Approximation Schemes for Class-Constrained Packing Problems….Pages 238-249
Partial Servicing of On-Line Jobs….Pages 250-261
Factor 4/3 Approximations for Minimum 2-Connected Subgraphs….Pages 262-273