Skip to main content
SpringerLink
Log in
Book cover

Approximation and Online Algorithms

13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers

  • Conference proceedings
  • © 2015

Overview

Editors:
  1. Laura Sanità

    1. University of Waterloo, Waterloo, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Martin Skutella

    1. Technische Universität Berlin, Berlin, Germany

    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 9499)

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

Included in the following conference series:

Conference proceedings info: WAOA 2015.

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 (17 papers)

  1. Front Matter

    Pages I-X
    Download chapter PDF

  2. Approximation Algorithms for k-Connected Graph Factors

    • Bodo Manthey, Marten Waanders
    Pages 1-12

  3. Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows

    • Fabrizio Grandoni, Salvatore Ingala, Sumedha Uniyal
    Pages 13-24

  4. Maximum ATSP with Weights Zero and One via Half-Edges

    • Katarzyna Paluch
    Pages 25-34

  5. An FPT 2-Approximation for Tree-cut Decomposition

    • Eunjung Kim, Sang-il Oum, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos
    Pages 35-46

  6. Tight Bounds for Double Coverage Against Weak Adversaries

    • Nikhil Bansal, Marek Eliáš, Łukasz Jeż, Grigorios Koumoutsos, Kirk Pruhs
    Pages 47-58

  7. Shortest Augmenting Paths for Online Matchings on Trees

    • Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych
    Pages 59-71

  8. Buyback Problem with Discrete Concave Valuation Functions

    • Shun Fukuda, Akiyoshi Shioura, Takeshi Tokuyama
    Pages 72-83

  9. On Temporally Connected Graphs of Small Cost

    • Eleni C. Akrida, Leszek Gąsieniec, George B. Mertzios, Paul G. Spirakis
    Pages 84-96

  10. Efficient Vertex-Label Distance Oracles for Planar Graphs

    • Shay Mozes, Eyal E. Skop
    Pages 97-109

  11. Constant-Time Local Computation Algorithms

    • Yishay Mansour, Boaz Patt-Shamir, Shai Vardi
    Pages 110-121

  12. An \(O(\log \mathrm{OPT})\)-Approximation for Covering/Packing Minor Models of \(\theta _{r}\)

    • Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos
    Pages 122-132

  13. Submodular Function Maximization on the Bounded Integer Lattice

    • Corinna Gottschalk, Britta Peis
    Pages 133-144

  14. Geometric Hitting Set for Segments of Few Orientations

    • Sándor P. Fekete, Kan Huang, Joseph S. B. Mitchell, Ojas Parekh, Cynthia A. Phillips
    Pages 145-157

  15. On Independent Set on B1-EPG Graphs

    • M. Bougeret, S. Bessy, D. Gonçalves, C. Paul
    Pages 158-169

  16. On the Smoothness of Paging Algorithms

    • Jan Reineke, Alejandro Salinger
    Pages 170-182

  17. Scheduling Parallel Jobs Online with Convex and Concave Parallelizability

    • Roozbeh Ebrahimi, Samuel McCauley, Benjamin Moseley
    Pages 183-195

  18. Scheduling with State-Dependent Machine Speed

    • Veerle Timmermans, Tjark Vredeveld
    Pages 196-208

  19. Back Matter

    Pages 209-209
    Download chapter PDF
Back to top

Other volumes

  1. Approximation and Online Algorithms

Keywords

About this book

This book constitutes the thoroughly refereed post-workshop proceedings of the 13th International Workshop on Approximation and Online Algorithms, WAOA 2015, held in Patras, Greece, in September 2015 as part of ALGO 2015.

The 17 revised full papers presented were carefully reviewed and selected from 40 submissions. Topics of interest for WAOA 2015 were: algorithmic game theory, algorithmic trading, coloring and partitioning, competitive analysis, computational advertising, computational finance, cuts and connectivity, geometric problems, graph algorithms, inapproximability, mechanism design, natural algorithms, network design, packing and covering, paradigms for the design and analysis of approximation and online algorithms, parameterized complexity, scheduling problems,and real-world applications.

Editors and Affiliations

  • University of Waterloo, Waterloo, Canada

    Laura Sanità

  • Technische Universität Berlin, Berlin, Germany

    Martin Skutella

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation