Approximation and Online Algorithms, 17 conf., WAOA 2019

Preface......Page 6
Organization......Page 7
On the Hardness of Computing the Diameter of a Polytope (Invited Talk)......Page 9
Contents......Page 10
 1 Introduction......Page 12
  2.2 Analysis......Page 15
  2.3 Maximum Independent Set......Page 18
  3.2 WV-polygons......Page 19
  3.3 WV-terrains: Removing the Monotonicity Assumption......Page 21
  4.1 The Semi-continuous Version......Page 22
  4.2 The Continuous Version......Page 23
 5 Terrain-Like vs. Non-jumping......Page 25
 References......Page 27
 1 Introduction......Page 29
  1.1 New Features of Our Work......Page 31
 2 The Input......Page 32
 3 Bounds on the Optimal Costs......Page 34
  4.1 The Assignment of Weights to Items......Page 35
  4.5 Using the Prices of Bin Types to Establish the Lower Bound on the Asymptotic Competitive Ratio......Page 36
 References......Page 39
 1 Introduction......Page 40
 2 Preliminaries......Page 42
 3 Competitive Ratio of Existing Strategies When max< k......Page 43
 4 Detour Strategy......Page 45
  4.1 Description of -Detour Strategy......Page 46
  4.2 Competitive Analysis......Page 47
  4.3 Discussion......Page 52
 References......Page 53
 1 Introduction......Page 54
  1.1 Related Works......Page 56
 2 Online Algorithms for Dynamic Problems: A Framework......Page 57
 3 2-Dimensional Strip Packing......Page 64
 4 Bin Packing......Page 66
 5 Vector Packing......Page 68
 References......Page 69
 1 Introduction......Page 71
 2 A 3-Approximation for Unrelated Machines......Page 73
 3 A 2- Inapproximability for Unrelated Machines......Page 74
 4 A PTAS for Identical Machines......Page 75
 5 EPTAS for Identical Machines......Page 79
 References......Page 81
 1 Introduction......Page 83
  1.1 Problems and Streaming Model......Page 84
  1.2 Our Results......Page 85
  2.1 Bin Packing......Page 86
  2.2 Scheduling......Page 88
 3 Bin Packing......Page 89
  3.1 Processing the Stream and Rounding......Page 91
  3.2 Bin Packing and Quantile Summaries......Page 94
 4 Vector Scheduling......Page 95
 References......Page 97
 1 Introduction......Page 100
 2 Preliminaries......Page 104
 3 Improved Upper Bound......Page 108
 4 Bounds for Small Instances......Page 113
 5 Conclusions......Page 114
 References......Page 115
 1 Introduction......Page 117
  1.3 Related Work on Online Bin Packing with Advice......Page 118
  2.1 k-Copy Online Algorithms......Page 119
  2.2 Bin Packing......Page 120
  3.1 Competitive Ratio......Page 121
  4.1 Competitive Ratio for PH3 as 1-Copy Online Algorithm......Page 122
  4.2 Competitive Ratio for PH3 as k-Copy Online Algorithm......Page 125
  4.3 Comparison to Related Algorithms......Page 127
 References......Page 129
Managing Multiple Mobile Resources......Page 131
  1.1 Related Work......Page 132
  1.2 Our Results and Outline of the Paper......Page 133
 2 Model and Notation......Page 134
 3 Lower Bounds......Page 135
 4 An Algorithm for the Unweighted Problem......Page 136
  4.1 Fast Resource Movement......Page 137
  4.2 Slow Resource Movement......Page 138
 5 Extension to the Weighted Problem......Page 144
 6 Open Problems......Page 146
 References......Page 147
 1 Introduction......Page 149
  1.1 Our Results......Page 150
  1.2 Related Work......Page 151
 2 Preliminaries......Page 152
  3.1 A 53-approximation......Page 154
  3.2 A (32+)-approximation......Page 157
 4 LP Relaxations for CycAP......Page 160
 References......Page 163
 1 Introduction......Page 165
  1.1 Graph Colouring Preliminaries......Page 166
  1.3 Approximate Strong Edge-Colouring Preliminaries......Page 167
  1.4 Main Results and Outline......Page 168
 2 A 6-approximation......Page 169
  2.1 Proof Outline of Theorem4......Page 171
 3 An Online 8-competitive algorithm......Page 175
 References......Page 179
Precedence-Constrained Scheduling and Min-Sum Set Cover......Page 181
 1 Introduction......Page 182
 2 A New Generalization of Min-Sum Set Cover......Page 187
 3 The Generalized Min-Sum Set Cover Problem......Page 190
  4.1 Linear Ordering Formulation......Page 192
  4.2 Completion Time Formulation......Page 193
 5 Conclusion......Page 195
 References......Page 196
 1 Introduction......Page 199
  1.1 Related Work......Page 200
 2 Problem Statements and Results......Page 201
  2.2 Our Results and Technique......Page 202
 3 Fault Tolerant k-Center with Outliers......Page 203
 4 Fault Tolerant k-Median with Outliers (v1)......Page 205
 5 Fault Tolerant k-Median with Outliers (v2)......Page 206
 6 Fault Tolerant k-Clustering with Outliers......Page 208
 References......Page 211
 1 Introduction......Page 213
 2 Definitions and Preliminaries......Page 215
  3.1 Inapproximability......Page 216
  3.2 Approximation......Page 221
  3.3 Bipartite Graphs......Page 223
  4.1 Inapproximability......Page 225
 References......Page 226
 1 Introduction......Page 228
 2 Preliminaries......Page 231
 3 Framework of Analysis......Page 233
  4.1 The Job Instance JG for the greedy algorithm G......Page 234
  4.2 A Job Instance JA for an Online Algorithm A......Page 238
 5 Conclusion......Page 239
 References......Page 240
 1 Introduction......Page 243
  1.1 Preliminaries......Page 246
 2 Fair Coresets and How to Get Them......Page 248
 3 Streaming PTAS and Constant-Factor Approximations......Page 254
 4 Practical Approximation Algorithms......Page 258
 References......Page 259
Author Index......Page 263