This book constitutes the thoroughly refereed post proceedings of the Third International Workshop on Approximation and Online Algorithms, WAOA 2005, held in Palma de Mallorca, Spain in October 2005 as part of the ALGO 2005 event.
The 26 revised full papers presented were carefully reviewed and selected from 68 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, Giuseppe Persiano
Series: Lecture ... Computer Science and General Issues
Edition: 1
Publisher: Springer
Year: 2006
Language: English
Pages: 342
Front Matter
......Page 1
Introduction......Page 9
Inapproximability of MIN-BP-SR and MIN-BP-SRT......Page 12
Polynomial-Time Algorithm for Fixed $K$......Page 18
Upper and Lower Bounds for $bp(I)$......Page 20
Concluding Remarks......Page 21
Introduction......Page 23
Preliminaries......Page 24
Polynomial Time Algorithms for Trees......Page 26
An Approximation Algorithm for Graphs with $Genus g$......Page 29
Approximation for General Graphs......Page 30
Random Multi-graphs......Page 32
MLCP with More Than Two Colors......Page 33
Introduction......Page 35
A Semidefinite Programming Relaxation for MAX NAE-SAT......Page 37
$RPR^2$ - Random Projection Followed by Randomized Rounding......Page 38
Analysis......Page 39
The $RPR^2$ Function......Page 41
Asano's MAX SAT Approximations Algorithms......Page 42
A Hybrid 0.7968-Approximation Algorithm for MAX SAT......Page 44
An Improved Approximation Algorithm Using $RPR^2$......Page 46
Concluding Remarks......Page 47
Selfish Routing......Page 49
Our Results......Page 50
The Model......Page 51
Nash Equilibrium and Coordination Ratio......Page 52
Linear Latency Functions......Page 53
Polynomial Latency Functions......Page 57
General Latency Functions......Page 59
The Limitation on the Power of Network Design......Page 61
References......Page 62
Introduction......Page 63
Preliminaries......Page 65
Form of an Optimal Solution......Page 66
Dynamic Programming Algorithm......Page 68
Simple Trees......Page 73
Local Ratio Algorithm......Page 74
References......Page 75
Introduction......Page 77
Previous Work......Page 78
The Model......Page 79
Observations About the Optimal Solution......Page 80
Deleting Pairs from the Input Sequence......Page 82
A Good Solution......Page 83
Local Ratio Schema......Page 84
Applying the Schema......Page 86
Applying the Schema on a Heavy Instance......Page 87
Applying the Schema on a Light Instance......Page 88
Introduction......Page 90
Preliminaries......Page 92
The Basic Gadgets......Page 93
The Construction......Page 94
Structure of an Optimal Tour......Page 95
Hardness Results......Page 96
Cycle Cover Games......Page 99
A Traveling Salesman Game as a Combination of Several Cycle Cover Games......Page 100
Introduction......Page 104
Baranyai's Rounding Lemma and Applications in Statistics......Page 105
Flexible Transfer Line Scheduling......Page 106
Basic Algorithm......Page 107
Correctness......Page 109
Error Bounds......Page 110
Naïve Generalization......Page 111
Linear Time Generalization......Page 112
Extensions......Page 113
Lower Bounds......Page 114
Row Intervals......Page 115
Introduction......Page 118
The Upper Bound......Page 119
The Lower Bound......Page 122
Introduction......Page 127
Algorithms for the Arc Version......Page 130
Algorithm GP-ER......Page 131
Analysis of PIM and GP-ER......Page 132
Algorithm Arc-Combination......Page 137
Algorithm P-ER......Page 138
Algorithm Directed-DAG......Page 139
Conclusion......Page 140
11 The Conference Call Search Problem in Wireless Networks......Page 141
Introduction......Page 142
NP-Hardness for the Oblivious Problem......Page 144
Two Users......Page 146
m Users......Page 149
Polynomial Time Algorithms for Finding Optimal Semi-adaptive Search Protocols......Page 152
Open Questions......Page 153
Introduction......Page 155
Previous Works and Our Contribution......Page 159
A Payment Scheme for Discrete Types......Page 161
A Payment Scheme for Rational Types......Page 163
Applications to $Q||C_max$ Problem......Page 166
Introduction......Page 169
Definitions and Preliminaries......Page 172
Greedy Best Response in Series-Parallel Networks......Page 174
The Price of Anarchy in Networks of Uniformly Related Links......Page 177
Computing a Symmetric Nash Equilibrium......Page 178
Bounding the Price of Anarchy......Page 179
Introduction......Page 184
LP Relaxation......Page 186
Structural Properties of the Optimal Dual for Simple b-Edge Cover......Page 188
Rounding the Optimal Dual for Simple b-Edge Cover......Page 189
Performance Ratio......Page 191
Proof of Lemma 3......Page 194
Introduction......Page 198
Previous Work......Page 199
Our Contribution......Page 200
An Algorithm with Sublinear Competitive Ratio......Page 201
Lower Bounds......Page 207
Introduction and Related Work......Page 211
Quadratic Programming Relaxation......Page 214
QP Based Greedy Algorithm......Page 218
Lower Bounds......Page 220
Generalizations......Page 221
Introduction......Page 224
Lower Bounds......Page 226
Optimal Algorithm with Repacking......Page 227
Packing by Using Bricks......Page 229
Competitive Algorithm......Page 231
Analysis of Competitive Ratio......Page 233
A PTAS for Offline Packing......Page 236
Concluding Remarks......Page 237
18 The Online Target Date Assignment Problem......Page 238
Introduction......Page 239
Minimizing Total Downstream Cost......Page 241
Downstream Bin-Packing......Page 243
Downstream Parallel-Machine Scheduling......Page 244
Minimizing Maximum Downstream Cost......Page 246
Downstream Bin-Packing......Page 247
Downstream Parallel-Machine Scheduling......Page 249
Traveling Salesman Problem......Page 251
Introduction......Page 252
Contribution and Paper Outline......Page 253
A Negative Result for the $F_max$-OlDarp......Page 254
The $F_max$-OlTsp Against the Fair Adversary: An Easy 2-Competitive Algorithm......Page 257
Competitiveness of fcfs......Page 258
A General Lower Bound......Page 261
Introduction......Page 264
Definitions......Page 265
The Algorithm......Page 266
Algorithm Analysis......Page 267
One-Neighborhoods......Page 268
Choosing Sides......Page 269
Shared Edges......Page 270
Diagonal Edges......Page 271
Bounding the Shared Edges......Page 272
Putting the Approximation Bound Together......Page 273
Algorithm - Stage 1......Page 274
Algorithm - Stage 2......Page 275
Introduction......Page 276
Preliminaries......Page 277
Existing Results......Page 278
New Results......Page 279
The Generic Reduction......Page 280
Clamps......Page 282
The Reduction......Page 283
Clamps in Directed Graphs......Page 285
Approximation Algorithms......Page 286
Approximating Directed Cycle Covers......Page 287
Solving Max-4-UCC in Polynomial Time......Page 288
Vertex Cover in Regular Graphs......Page 289
Introduction......Page 290
Definitions and Preliminaries......Page 292
Local Dominating Sets......Page 293
Efficient Construction of Suitable Subsets......Page 295
Discussion......Page 298
Conclusion......Page 299
Motivation......Page 301
Summary of Our Results......Page 302
Related Results......Page 303
No Precedence Constraints......Page 304
One Speed for All Machines......Page 305
The Power Equality......Page 306
Algorithm......Page 309
Analysis......Page 310
Conclusions......Page 312
Introduction......Page 314
Results and Techniques......Page 316
The GVY Algorithm......Page 317
The Prize-Collecting Algorithm......Page 318
Initial Assumptions......Page 320
The Lagrangian Relaxation......Page 321
Finding Useful Integral Solutions......Page 322
A Greedy Partial Cover Algorithm......Page 323
A Greedy Combination......Page 324
The Algorithm......Page 325
Analysis......Page 326
Introduction......Page 328
Related Work......Page 330
Preliminaries......Page 331
Hardness of BPF......Page 332
Discrete Instances......Page 333
A Dual PTAS......Page 334
An APTAS for BP-SPF......Page 335
A Dual AFPTAS for BP-SPF......Page 337
Analysis of the Scheme......Page 339
Bin Packing with Size-Increasing Fragmentation......Page 340
back-matter......Page 342
