Approximation and Online Algorithms

1. Front Matter

   PDF

2. Min-Sum 2-Paths Problems

   • Trevor Fenner, Oded Lachish, Alexandru Popa

   Pages 1-11

3. Low Dimensional Embeddings of Doubling Metrics

   • Ofer Neiman

   Pages 12-23

4. Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation

   • Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono

   Pages 24-36

5. On the max min vertex cover Problem

   • Nicolas Boria, Federico Della Croce, Vangelis Th. Paschos

   Pages 37-48

6. On Fixed Cost k-Flow Problems

   • MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Zeev Nutov

   Pages 49-60

7. Approximating the Quadratic Knapsack Problem on Special Graph Classes

   • Ulrich Pferschy, Joachim Schauer

   Pages 61-72

8. Approximating the Sparsest k-Subgraph in Chordal Graphs

   • Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau

   Pages 73-84

9. Improved Approximation Algorithm for k-Level UFL with Penalties, a Simplistic View on Randomizing the Scaling Parameter

   • Jaroslaw Byrka, Shanfei Li, Bartosz Rybicki

   Pages 85-96

10. Inapproximability Results for Graph Convexity Parameters

    • Erika M. M. Coelho, Mitre C. Dourado, Rudini M. Sampaio

    Pages 97-107

11. Continuum Armed Bandit Problem of Few Variables in High Dimensions

    • Hemant Tyagi, Bernd Gärtner

    Pages 108-119

12. Approximability of Connected Factors

    • Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, N. S. Narayanaswamy, C. S. Rahul

    Pages 120-131

13. Reordering Buffer Management with Advice

    • Anna Adamaszek, Marc P. Renault, Adi Rosén, Rob van Stee

    Pages 132-143

14. Online Knapsack Revisited

    • Marek Cygan, Łukasz Jeż

    Pages 144-155

15. Counting Approximately-Shortest Paths in Directed Acyclic Graphs

    • Matúš Mihalák, Rastislav Šrámek, Peter Widmayer

    Pages 156-167

16. Back Matter

    PDF

This book constitutes the thoroughly refereed workshop proceedings of the 11th International Workshop on Approximation and Online Algorithms, WAOA 2013, held in Sophia Antipolis, France, in September 2013 as part of the ALGO 2013 conference event. The 14 revised full papers presented were carefully reviewed and selected from 33 submissions. They focus on the design and analysis of algorithms for online and computationally hard problems, for example in algorithmic game theory, algorithmic trading, coloring and partitioning, competitive analysis, computational advertising, computational finance, cuts and connectivity, geometric problems, graph algorithms, inapproximability results, mechanism design, natural algorithms, network design, packing and covering, paradigms for the design and analysis of approximation and online algorithms, parameterized complexity, real-world applications, scheduling problems.

• algorithmic game theory
• algorithmic trading
• approximation algorithms
• coloring
• competitive analysis
• algorithm analysis and problem complexity

• Computer Technology Institute and Press “Diophantus” & Department of Computer Engineering and Informatics, University of Patras, Rio, Greece

  Christos Kaklamanis

• University of Pittsburgh, Pittsburgh, USA

  Kirk Pruhs

Policies and ethics