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.
Author(s): Thomas Erlebach, Christos Kaklamanis
Series: Lecture Notes in Computer Science - Theoretical Computer Science and General Issues
Publisher: Springer
Year: 2007
Language: English
Pages: 140
01......Page 1
Introduction......Page 9
Our Results......Page 10
Algorithms for Special Cases......Page 11
Algorithm for the General Case......Page 15
Algorithm for the Two-Machine Problem......Page 16
Inapproximability Lower Bounds......Page 18
Problem $1\;|\mbox{ exact }l_j,\; a_j=b_j\;|\;C_{\max}$......Page 19
Problem $F2\;|\mbox{ exact }l_j,\;a_j=b_j\;|\;C_{\max}$......Page 21
Introduction......Page 23
Prefix Position Auction Mechanisms......Page 26
Analysis of the Top-Down Prefix Auction......Page 28
Equilibrium in the Top-Down Auction......Page 30
Concluding Remarks......Page 34
Introduction......Page 37
Budgeted Maximum Coverage and Budgeted Unique Coverage......Page 40
Budgeted Facility Location......Page 41
Inapproximability......Page 42
The $k4k$-Budgeted Cell Planning Problem......Page 43
The Structure of BCPP Solutions......Page 44
An $\frac{e-1}{2e-1}$\,-Approximation Algorithm......Page 46
Conclusions and Future Work......Page 49
Introduction......Page 51
Relations to Monge......Page 53
The Algorithm......Page 54
The Main Algorithm......Page 55
Applications......Page 57
D-Medians on a Directed Line......Page 58
Wireless Mobile Paging......Page 59
Dropping the Extra Condition......Page 61
Introduction......Page 63
Notation and Preliminaries......Page 65
Approximation Algorithms for $M(P,m)$......Page 66
Approximation Algorithms for $min(P,X)$......Page 72
Introduction......Page 77
Exact Algorithms with Branchwidth......Page 80
Perturbation and Curved Dissection......Page 82
Portals and Portal Respecting Trees......Page 83
The Algorithm......Page 84
Extensions of the PTAS......Page 85
An Approximation Algorithm for MCC with Rooms of Varying Sizes......Page 86
Introduction......Page 91
Preliminaries......Page 93
The $k$-Traveling Salesman Problem......Page 94
The $k$-Traveling Repairman Problem......Page 95
An Asymptotically Optimal Algorithm......Page 97
Lower Bounds......Page 99
Lower Bounds on the Plane......Page 100
Conclusions and Open Problems......Page 101
Introduction......Page 103
Competitive Ratio Characterizations......Page 105
Relative Worst Order Characterizations......Page 107
Concluding Remarks......Page 113
Introduction......Page 116
Analysis of Algorithm 1......Page 118
Conclusion......Page 126
Introduction......Page 129
Naïve Algorithms......Page 131
Analysis......Page 132
The Combined Algorithm......Page 136
Beyond One Dimension......Page 137
Closing Remarks......Page 138
12......Page 140
