Efficient Approximation and Online Algorithms: Recent Progress on Classical Combinatorial Optimization Problems and New Applications

Evripidis Bampis, Klaus Jansen, Claire Kenyon9783540322122, 3540322124

This book provides a good opportunity for computer science practitioners and researchers to get in sync with the current state-of-the-art and future trends in the field of combinatorial optimization and online algorithms. Recent advances in this area are presented focusing on the design of efficient approximation and on-line algorithms. One central idea in the book is to use a linear program relaxation of the problem, randomization and rounding techniques.This state-of-the-art survey contains 11 carefully selected papers that cover some classical problems of scheduling, of packing, and of graph theory, but also new optimization problems arising in various applications like networks, data mining or classification.

---

Table of contents :
front-matter.pdf……Page 1
Introduction……Page 7
Formal Techniques and Tools……Page 8
Dimensionality Reduction……Page 9
The Data Stream Computation Model……Page 12
Sampling……Page 13
Approximating the Lp Distance. Sketches……Page 15
Data Mining Tasks and Applications……Page 17
Association Rules……Page 19
Mining for Frequent Itemsets……Page 20
Other Measures for Association Rules……Page 21
Mining for Similarity Rules……Page 22
Transversals……Page 23
Clustering……Page 24
The k-Median Approach……Page 25
Similarity Measures……Page 26
Quality of Clustering……Page 27
Mining the Web……Page 28
Conclusion……Page 30
Introduction……Page 36
Introduction……Page 37
Convergence Issue……Page 38
Polynomially Solvable Problems……Page 39
Definitions and Problems……Page 40
Oblivious Local Search for max k-sat……Page 41
Non-oblivious Local Search for max k-sat……Page 43
Non-oblivious Local Search for max k-ccsp……Page 44
Applications for Graph and Hypergraph Coloring Problems……Page 46
The Traveling Salesman Problem……Page 47
The Quadratic Assignment Problem……Page 50
Set Packing and Independent Set……Page 53
Oblivious Local Search for k-set packing……Page 54
Oblivious Local Search for w-independent set on d-Claw Free Graphs……Page 55
Non-oblivious Local Search for w-independent set on d-Claw Free Graphs……Page 57
independent set on Bounded Degree Graphs……Page 58
Semi-local Search for k-set cover……Page 60
The Maximum Cut Problem……Page 62
Facility Location Related Problems……Page 65
Scheduling Problems……Page 68
Minimum Label Spanning Tree Problem……Page 70
Replica Placement in a Distributed File Systems……Page 71
Summary and Conclusion……Page 73
Motivation……Page 80
Problem Definition……Page 82
Hardness Results and Lower Bounds……Page 83
Coloring Symmetric Sets of Paths……Page 85
Greedy Path Coloring Algorithms in Undirected Trees……Page 86
Greedy Path Coloring Algorithms in Bidirected Trees……Page 88
A Lower Bound Technique……Page 92
Lower Bounds……Page 93
Upper Bounds……Page 94
Fractional Path Coloring and Applications……Page 95
Fractional Path Coloring on Binary Bidirected Trees……Page 96
Applications to Path Coloring on Bounded-Degree Bidirected Trees……Page 97
On-Line Algorithms……Page 98
Open Problems……Page 100
Introduction……Page 103
Definition of Graph Classes and Graph Parameters……Page 105
Polynomial-Time Solvable Cases and Hardness Results……Page 106
The Greedy Algorithm……Page 107
The Bounded-Length Greedy Algorithm……Page 108
The Shortest-Path-First Greedy Algorithm……Page 112
Inapproximability for Directed Graphs……Page 114
Linear Programming and Randomized Rounding……Page 116
Trees and Trees of Rings……Page 119
Meshes and Densely Embedded Graphs……Page 121
Expander Graphs……Page 125
Complete Graphs……Page 126
MEDP with Pre-determined Paths……Page 127
The Unsplittable Flow Problem……Page 128
UFP Approximations in Terms of Routing Number and Flow Number……Page 129
A Combinatorial Algorithm for Classical UFP……Page 130
Combinatorial Algorithms for Extended and Bounded UFP……Page 133
LP-Based Algorithms for UFP……Page 134
Further Results for Related Problems……Page 135
Introduction……Page 141
Preliminaries……Page 142
The Maximum Independent Set Problem……Page 143
Independent Sets in Unit Disk Graphs……Page 144
Independent Sets in General Disk Graphs……Page 147
Independent Sets in Bounded Disk Graphs……Page 148
Coloring Unit Disk Graphs……Page 149
Off-Line Coloring of Disk Graphs……Page 151
On-Line Coloring of Disk Graphs……Page 153
Conclusion……Page 158
Introduction……Page 162
Min-Max Resource Sharing……Page 164
Max-Min Resource Sharing……Page 167
Scheduling Jobs on Unrelated Machines……Page 170
A 2 Approximation Algorithm……Page 171
A Faster (2 + $epsilon$) Approximation Algorithm……Page 174
Strip Packing……Page 178
Fractional Strip Packing……Page 180
Improving the Running Time of the AFPTAS……Page 189
Analysis for Min-Max Resource Sharing……Page 192
Analysis for Max-Min Resource Sharing……Page 200
Introduction……Page 209
Analysis of SRPT……Page 211
Conclusions……Page 217
Introduction……Page 219
LaP in Various Contexts……Page 220
Approximation Algorithms……Page 222
Related Graph Partition Problems……Page 224
Complexity and Approximability Results for the MCP……Page 225
Approximation Results for the 0-EP……Page 231
The k=2 Case……Page 233
The Uniform Metric Case……Page 234
The Linear Metric Case……Page 235
The Uniform Metric Case……Page 237
The Truncated Linear Metric Case……Page 240
The Uniform Metric Case……Page 244
The Linear Metric Case……Page 247
The Truncated Linear Metric Case……Page 248
The General Metric Case……Page 249
Conclusion……Page 250
Introduction……Page 256
Non-preemptive and Preemptive List Scheduling……Page 259
A Generalization of Smith’s Ratio Rule to 1| rj, pmtn|$sum$wjCj……Page 261
The Concept of α-Points……Page 262
List Scheduling in Order of α-Points……Page 263
Preemptive List Scheduling in Order of α-Points……Page 266
Scheduling in Order of α-Points for Only One α……Page 267
Ane/(e − 1)-Approximation Algorithm for 1| rj |$sum$Cj……Page 269
Time-Indexed LP Relaxations……Page 271
Another Time-Indexed LP Relaxation……Page 275
Combinatorial Relaxations……Page 276
On the Quality of Time-Indexed LP Relaxations……Page 278
Scheduling in Order of LP Completion Times……Page 280
Approximations for Single Machine Scheduling with Release Dates……Page 281
A 1.6853-Approximation Algorithm for 1| rj |$sum$wjCj……Page 285
A 4/3-Approximation Algorithm for 1| rj, pmtn|$sum$wjCj……Page 288
Approximations for Single Machine Scheduling with Precedence Constraints……Page 290
On-Line Results……Page 293
References……Page 294
Introduction……Page 298
Hardness of the k-Median Problem……Page 301
Linear Programming Based Algorithms……Page 302
Integer Program Formulation……Page 303
Filtering……Page 304
An Algorithm with Constant Performance Ratio……Page 306
Analysis……Page 307
The Uncapacitated Facility Location Problem……Page 310
Performance Ratio……Page 312
Running Time……Page 314
Algorithm for the k-Median Problem……Page 315
A Local Search Algorithm……Page 319
Large Deviations……Page 327
The Lovász-Local-Lemma……Page 329
Basic Randomized Rounding — A Warming-Up Exercise……Page 333
Job Shop Scheduling……Page 335
Problem and History……Page 338
The First Approximation……Page 339
Improvement by the LLL……Page 342
Inapproximability……Page 343
The Base: 0/1 Random Variables……Page 344
Extension I: General Random Variables — Small Domains……Page 348
Extension II: General Random Variables — Large Domains……Page 349
Resource Constrained Scheduling Revisited……Page 351
back-matter.pdf……Page 354