Approximation and Online Algorithms: 4th International Workshop, WAOA 2006, Zurich, Switzerland, September 14-15, 2006. Revised Papers

Alexander A. Ageev, Alexander V. Kononov (auth.), Thomas Erlebach, Christos Kaklamanis (eds.)3540695133, 9783540695134

This book constitutes the thoroughly refereed post-proceedings of the 4th International Workshop on Approximation and Online Algorithms, WAOA 2006, held in Zurich, Switzerland in September 2006 as part of the ALGO 2006 conference event.

The 26 revised full papers presented were carefully reviewed and selected from 62 submissions. Topics addressed by the workshop are algorithmic game theory, approximation classes, coloring and partitioning, competitive analysis, computational finance, cuts and connectivity, geometric problems, inapproximability results, mechanism design, network design, packing and covering, paradigms, randomization techniques, real-world applications, and scheduling problems.

---

Table of contents :
Front Matter….Pages –
Approximation Algorithms for Scheduling Problems with Exact Delays….Pages 1-14
Bidding to the Top: VCG and Equilibria of Position-Based Auctions….Pages 15-28
Coping with Interference: From Maximum Coverage to Planning Cellular Networks….Pages 29-42
Online Dynamic Programming Speedups….Pages 43-54
Covering Many or Few Points with Unit Disks….Pages 55-68
On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems….Pages 69-82
Online k -Server Routing Problems….Pages 83-94
Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem….Pages 95-107
Improved Approximation Bounds for Edge Dominating Set in Dense Graphs….Pages 108-120
A Randomized Algorithm for Online Unit Clustering….Pages 121-131
On Hierarchical Diameter-Clustering, and the Supplier Problem….Pages 132-145
Bin Packing with Rejection Revisited….Pages 146-159
On Bin Packing with Conflicts….Pages 160-173
Approximate Distance Queries in Disk Graphs….Pages 174-187
Network Design with Edge-Connectivity and Degree Constraints….Pages 188-201
Approximating Maximum Cut with Limited Unbalance….Pages 202-213
Worst Case Analysis of Max-Regret, Greedy and Other Heuristics for Multidimensional Assignment and Traveling Salesman Problems….Pages 214-225
Improved Online Hypercube Packing….Pages 226-239
Competitive Online Multicommodity Routing….Pages 240-252
The k -Allocation Problem and Its Variants….Pages 253-264
An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions….Pages 265-278
Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set….Pages 279-289
Approximating the Unweighted k -Set Cover Problem: Greedy Meets Local Search….Pages 290-301
Approximation Algorithms for Multi-criteria Traveling Salesman Problems….Pages 302-315
The Survival of the Weakest in Networks….Pages 316-329
Online Distributed Object Migration….Pages 330-344
Back Matter….Pages –