Skip to main content
SpringerLink
Log in
Book cover

Approximation and Online Algorithms

15th International Workshop, WAOA 2017, Vienna, Austria, September 7–8, 2017, Revised Selected Papers

  • Conference proceedings
  • © 2018

Overview

Editors:
  1. Roberto Solis-Oba

    1. The University of Western Ontario, London, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Rudolf Fleischer

    1. German University of Technology in Oman, Muscat, Oman

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 10787)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: WAOA 2017.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (23 papers)

  1. Front Matter

    Pages I-X
    Download chapter 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
Back to top

Other volumes

  1. Approximation and Online Algorithms

Keywords

About this book

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.

Editors and Affiliations

  • The University of Western Ontario, London, Canada

    Roberto Solis-Oba

  • German University of Technology in Oman, Muscat, Oman

    Rudolf Fleischer

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation