Approximation and Online Algorithms

1. Front Matter

   Pages I-X

   PDF

2. Capacitated Domination Problems on Planar Graphs

   • Amariah Becker

   Pages 1-16

3. On Approximability of Connected Path Vertex Cover

   • Toshihiro Fujito

   Pages 17-25

4. Improved PTASs for Convex Barrier Coverage

   • Paz Carmi, Matthew J. Katz, Rachel Saban, Yael Stein

   Pages 26-40

5. Complexity and Approximation of the Longest Vector Sum Problem

   • Vladimir Shenmaier

   Pages 41-51

6. Deadline TSP

   • Boaz Farbstein, Asaf Levin

   Pages 52-65

7. A Bicriteria Approximation Algorithm for the k-Center and k-Median Problems

   • Soroush Alamdari, David Shmoys

   Pages 66-75

8. Approximating Domination on Intersection Graphs of Paths on a Grid

   • Saeed Mehrabi

   Pages 76-89

9. Submodular Function Minimization with Submodular Set Covering Constraints and Precedence Constraints

   • Naoyuki Kamiyama

   Pages 90-101

10. Lower Bounds for Several Online Variants of Bin Packing

    • János Balogh, József Békési, György Dósa, Leah Epstein, Asaf Levin

    Pages 102-117

11. The Online Multicommodity Connected Facility Location Problem

    • Mário César San Felice, Cristina G. Fernandes, Carla Negri Lintzmayer

    Pages 118-131

12. A Match in Time Saves Nine: Deterministic Online Matching with Delays

    • Marcin Bienkowski, Artur Kraska, Paweł Schmidt

    Pages 132-146

13. Online Packing of Rectangular Items into Square Bins

    • Janusz Januszewski, Łukasz Zielonka

    Pages 147-163

14. A Tight Lower Bound for Online Convex Optimization with Switching Costs

    • Antonios Antoniadis, Kevin Schewior

    Pages 164-175

15. A k-Median Based Online Algorithm for the Stochastic k-Server Problem

    • Abhijin Adiga, Alexander D. Friedman, Sharath Raghvendra

    Pages 176-189

16. On Packet Scheduling with Adversarial Jamming and Speedup

    • Martin Böhm, Łukasz Jeż, Jiří Sgall, Pavel Veselý

    Pages 190-206

17. Non-clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times

    • Alexander Mäcker, Manuel Malatyali, Friedhelm Meyer auf der Heide, Sören Riechers

    Pages 207-222

18. On-line Search in Two-Dimensional Environment

    • Dariusz Dereniowski, Dorota Urbańska

    Pages 223-237

19. Online Unit Clustering in Higher Dimensions

    • Adrian Dumitrescu, Csaba D. Tóth

    Pages 238-252

20. On Conceptually Simple Algorithms for Variants of Online Bipartite Matching

    • Allan Borodin, Denis Pankratov, Amirali Salehi-Abari

    Pages 253-268

This book constitutes the thoroughly refereed workshop post-proceedings of the 15th International Workshop on Approximation and Online Algorithms, WAOA 2017, held in Vienna, Austria, in September 2017 as part of ALGO 2017.


The 23 revised full papers presented in this book were carefully reviewed and selected from 50 submissions. Topics of interest for WAOA 2017 were: graph algorithms; inapproximability results; network design; packing and covering; paradigms for the design and analysis of approximation and online algorithms; parameterized complexity; scheduling problems; algorithmic game theory; coloring and partitioning; competitive analysis; computational advertising; computational finance; cuts and connectivity; geometric problems; mechanism design; resource augmentation; and real-world applications.

• Approximation algorithms
• online algorithms
• combinatorial optimization
• networks
• game theory
• scheduling
• packing and covering
• graph theory
• approximation algorithms
• graphic methods
• telecommunication networks
• artificial intelligence
• cluster analysis
• clustering
• bin packing
• planar graph
• directed graphs
• randomized algorithms
• nash equilibrium
• algorithm analysis and problem complexity
• data structures

• The University of Western Ontario, London, Canada

  Roberto Solis-Oba

• German University of Technology in Oman, Muscat, Oman

  Rudolf Fleischer

Policies and ethics