Approximation and Online Algorithms [recurso electrónico] 11th International Workshop, WAOA 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers

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. Front Matter....Pages - Min-Sum 2-Paths Problems....Pages 1-11 Low Dimensional Embeddings of Doubling Metrics....Pages 12-23 Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation....Pages 24-36 On the max min vertex cover Problem....Pages 37-48 On Fixed Cost k -Flow Problems....Pages 49-60 Approximating the Quadratic Knapsack Problem on Special Graph Classes....Pages 61-72 Approximating the Sparsest k -Subgraph in Chordal Graphs....Pages 73-84 Improved Approximation Algorithm for k -Level UFL with Penalties, a Simplistic View on Randomizing the Scaling Parameter....Pages 85-96 Inapproximability Results for Graph Convexity Parameters....Pages 97-107 Continuum Armed Bandit Problem of Few Variables in High Dimensions....Pages 108-119 Approximability of Connected Factors....Pages 120-131 Reordering Buffer Management with Advice....Pages 132-143 Online Knapsack Revisited....Pages 144-155 Counting Approximately-Shortest Paths in Directed Acyclic Graphs....Pages 156-167 Back Matter....Pages - This book constitutes the thoroughly refereed post workshop proceedings of the 10th International Workshop on Approximation and Online Algorithms, WAOA 2012, held in Ljubljana, Slovenia, in September 2012 as part of the ALGO 2012 conference event.