Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques: 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA, USA, August 18–20, 2001 Proceedings

Michel X. Goemans (auth.), Michel Goemans, Klaus Jansen, José D. P. Rolim, Luca Trevisan (eds.)3540424709, 9783540424703

This book constitutes the joint refereed proceedings of the 4th International Workshop on Approximation Algorithms for Optimization Problems, APPROX 2001 and of the 5th International Workshop on Ranomization and Approximation Techniques in Computer Science, RANDOM 2001, held in Berkeley, California, USA in August 2001. The 26 revised full papers presented were carefully reviewed and selected from a total of 54 submissions. Among the issues addressed are design and analysis of approximation algorithms, inapproximability results, on-line problems, randomization, de-randomization, average-case analysis, approximation classes, randomized complexity theory, scheduling, routing, coloring, partitioning, packing, covering, computational geometry, network design, and applications in various fields.

---

Table of contents :
Using Complex Semidefinite Programming for Approximating MAX E2-LIN3….Pages 1-1
Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems….Pages 2-5
Web Search via Hub Synthesis….Pages 6-6
Error-Correcting Codes and Pseudorandom Projections….Pages 7-9
Order in Pseudorandomness….Pages 10-11
Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows….Pages 12-24
On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique….Pages 24-36
Online Weighted Flow Time and Deadline Scheduling….Pages 36-47
An Online Algorithm for the Postman Problem with a Small Penalty….Pages 48-54
A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem….Pages 55-63
Approximation Schemes for Ordered Vector Packing Problems….Pages 63-75
Incremental Codes….Pages 75-90
A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set….Pages 90-101
Approximation Algorithms for Budget-Constrained Auctions….Pages 102-113
Minimizing Average Completion of Dedicated Tasks and Interval Graphs….Pages 114-126
A Greedy Facility Location Algorithm Analyzed Using Dual Fitting….Pages 127-137
0.863-Approximation Algorithm for MAX DICUT….Pages 138-146
The Maximum Acyclic Subgraph Problem and Degree-3 Graphs….Pages 147-158
Some Approximation Results for the Maximum Agreement Forest Problem….Pages 159-169
Near-optimum Universal Graphs for Graphs with Bounded Degrees….Pages 170-180
On a Generalized Ruin Problem….Pages 181-191
On the b -Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation….Pages 192-201
Exact Sampling in Machine Scheduling Problems….Pages 202-210
On Computing Ad-hoc Selective Families….Pages 211-222
L Infinity Embeddings….Pages 223-228
On Euclidean Embeddings and Bandwidth Minimization….Pages 229-240
The Non-approximability of Non-Boolean Predicates….Pages 241-249
On the Derandomization of Constant Depth Circuits….Pages 249-260
Testing Parenthesis Languages….Pages 261-272
Proclaiming Dictators and Juntas or Testing Boolean Formulae….Pages 273-285
Equitable Coloring Extends Chernoff-Hoeffding Bounds….Pages 285-296