Approximation and Online Algorithms: 4th International Workshop, WAOA 2006, Zurich, Switzerland, September 14-15, 2006, Revised Papers (Lecture Notes in Computer Science (4368))

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

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.

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.