Approximation and Online Algorithms: 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers

✍ Scribed by Laura Sanit`, Martin Skutella (eds.)

• Publisher: Springer International Publishing
• Year: 2015
• Tongue: English
• Leaves: 219
• Series: Lecture Notes in Computer Science 9499
• Edition: 1
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Front Matter....Pages I-X
Approximation Algorithms for k-Connected Graph Factors....Pages 1-12
Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows....Pages 13-24
Maximum ATSP with Weights Zero and One via Half-Edges....Pages 25-34
An FPT 2-Approximation for Tree-cut Decomposition....Pages 35-46
Tight Bounds for Double Coverage Against Weak Adversaries....Pages 47-58
Shortest Augmenting Paths for Online Matchings on Trees....Pages 59-71
Buyback Problem with Discrete Concave Valuation Functions....Pages 72-83
On Temporally Connected Graphs of Small Cost....Pages 84-96
Efficient Vertex-Label Distance Oracles for Planar Graphs....Pages 97-109
Constant-Time Local Computation Algorithms....Pages 110-121
An (O(\log \mathrm{OPT})) -Approximation for Covering/Packing Minor Models of (\theta _{r}) ....Pages 122-132
Submodular Function Maximization on the Bounded Integer Lattice....Pages 133-144
Geometric Hitting Set for Segments of Few Orientations....Pages 145-157
On Independent Set on B1-EPG Graphs....Pages 158-169
On the Smoothness of Paging Algorithms....Pages 170-182
Scheduling Parallel Jobs Online with Convex and Concave Parallelizability....Pages 183-195
Scheduling with State-Dependent Machine Speed....Pages 196-208
Back Matter....Pages 209-209

✦ Subjects

Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Data Structures; Algorithms; Computation by Abstract Devices; Numeric Computing