Optimization and approximation on systems of geometric objects

Optimization Problems and Systems of Geometric Objects......Page 11
Wireless Networks......Page 12
Wireless Network Planning......Page 13
Thesis Overview......Page 14
Published Papers......Page 17
I Foundations......Page 19
Classic Notions......Page 21
Asymptotic Approximation Schemes......Page 24
Intersection Graphs......Page 27
Interval Graphs and Generalizations......Page 28
Intersection Graphs of Higher Dimensional Objects......Page 30
Disk Graphs and Ball Graphs......Page 31
Models for Wireless Networks......Page 33
Relation to Other Graph Classes......Page 35
Relation to Planar Graphs......Page 36
Scalable and epsilon-Separated Objects......Page 39
Finite Representation......Page 43
Polynomial Representation and Separation......Page 44
From Representation to Separation......Page 45
From Separation to Representation......Page 47
II Approximation on Geometric Intersection Graphs......Page 51
Problems......Page 53
Previous Work......Page 54
Graph Decompositions......Page 59
Thickness......Page 63
Algorithms on Strong, Relaxed Tree Decompositions......Page 64
Maximum Independent Set and Minimum Vertex Cover......Page 65
Minimum Dominating Set......Page 66
Minimum Connected Dominating Set......Page 69
Unit Disk Graphs of Bounded Thickness......Page 72
The Density of Unit Disk Graphs......Page 77
Relation to Thickness......Page 78
Approximation Schemes......Page 80
Maximum Independent Set......Page 81
Minimum Vertex Cover......Page 84
Minimum Dominating Set......Page 87
Minimum Connected Dominating Set......Page 89
Generalizations......Page 92
Optimality......Page 94
Connected Dominating Set on Graphs Excluding a Minor......Page 98
The Ply of Disk Graphs......Page 101
Approximating Minimum Vertex Cover......Page 102
Properties of the size and sol-Functions......Page 103
Computing the size- and sol-Functions......Page 105
An eptas for Minimum Vertex Cover......Page 108
Approximating Maximum Independent Set......Page 109
Further Improvements......Page 114
Maximum Nr. of Disjoint Unit Disks Intersecting a Unit Square......Page 116
Domination on Geometric Intersection Graphs......Page 123
Small epsilon-Nets......Page 124
Generic Domination......Page 126
Homothetic Convex Polygons......Page 129
Regular Polygons......Page 133
More General Objects......Page 135
Disk Graphs of Bounded Ply......Page 136
Ply-Dependent Approximation Ratio......Page 137
A Constant Approximation Ratio......Page 139
A Better Constant......Page 148
Hardness of Approximation......Page 155
Intersection Graphs of Polygons......Page 156
Intersection Graphs of Fat Objects......Page 158
Intersection Graphs of Rectangles......Page 160
III Approximating Geometric Coverage Problems......Page 167
Problems......Page 169
Previous Work......Page 171
A ptas on Unit Squares......Page 175
Geometric Budgeted Maximum Coverage......Page 185
Optimality and Relation to Domination......Page 187
Hardness of Approximation......Page 188
Unique Coverage......Page 191
Approximation Algorithm on Unit Disks......Page 192
Budgets and Satisfactions......Page 195
Approximation Algorithm on Unit Squares......Page 197
Unique Coverage on Disks of Bounded Ply......Page 198
Properties of the cost- and sol-Functions......Page 199
Computing the cost- and sol-Functions......Page 202
The Approximation Algorithm......Page 204
Geometric Membership Set Cover......Page 206
Hardness of Approximation......Page 209
Conclusion......Page 217
Bibliography......Page 219
Author Index......Page 247
Index......Page 253
Samenvatting......Page 259
Summary......Page 261
Acknowledgments......Page 263