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

by Erlebach, Thomas; Kaklamanis, Christos

• ISBN13: 9783540695134
• ISBN10: 3540695133
• Format: Paperback
• Copyright: 2007-02-21
• Publisher: Springer Verlag

Summary

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

Approximation algorithms for scheduling problems with exact delays	p. 1
Bidding to the top : VCG and equilibria of position-based auctions	p. 15
Coping with interference : from maximum coverage to planning cellular networks	p. 29
Online dynamic programming speedups	p. 43
Covering many or few points with unit disks	p. 55
On the minimum corridor connection problem and other generalized geometric problems	p. 69
Online k-server routing problems	p. 83
Theoretical evidence for the superiority of LRU-2 over LRU for the paging problem	p. 95
Improved approximation bounds for edge dominating set in dense graphs	p. 108
A randomized algorithm for online unit clustering	p. 121
On hierarchical diameter-clustering, and the supplier problem	p. 132
Bin packing with rejection revisited	p. 146
On bin packing with conflicts	p. 160
Approximate distance queries in disk graphs	p. 174
Network design with edge-connectivity and degree constraints	p. 188
Approximating maximum cut with limited unbalance	p. 202
Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems	p. 214
Improved online hypercube packing	p. 226
Competitive online multicommodity routing	p. 240
The k-allocation problem and its variants	p. 253
An experimental study of the misdirection algorithm for combinatorial auctions	p. 265
Reversal distance for strings with duplicates : linear time approximation using hitting set	p. 279
Approximating the unweighted k-set cover problem : greedy meets local search	p. 290
Approximation algorithms for multi-criteria traveling salesman problems	p. 302
The survival of the weakest in networks	p. 316
Online distributed object migration	p. 330
Table of Contents provided by Blackwell. All Rights Reserved.