Approximation and Online Algorithms: 8th International Workshop, WAOA 2010, Liverpool, UK, September 9-10, 2010. Revised Papers

✍ Scribed by Elliot Anshelevich, Bugra Caskurlu, Ameya Hate (auth.), Klaus Jansen, Roberto Solis-Oba (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2011
• Tongue: English
• Leaves: 283
• Series: Lecture Notes in Computer Science 6534 Theoretical Computer Science and General Issues
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the thoroughly refereed post workshop proceedings of the 8th International Workshop on Approximation and Online Algorithms, WAOA 2010, held in Liverpool, UK, in September 2010 as part of the ALGO 2010 conference event.

The 23 revised full papers presented were carefully reviewed and
selected from 58 submissions. The workshop covered areas such as
algorithmic game theory, approximation classes, coloring and
partitioning, competitive analysis, computational finance, cuts and
connectivity, geometric problems, inapproximability results, mechanism design, network design, packing and covering, paradigms for design and analysis of approximation and online algorithms, parameterized complexity, randomization techniques, real-world applications, and scheduling problems.

✦ Table of Contents

Front Matter....Pages -
Strategic Multiway Cut and Multicut Games....Pages 1-12
Approximating Directed Buy-at-Bulk Network Design....Pages 13-24
New Lower Bounds for Certain Classes of Bin Packing Algorithms....Pages 25-36
On the Approximation Complexity Hierarchy....Pages 37-46
The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers....Pages 47-58
Tradeoff between Energy and Throughput for Online Deadline Scheduling....Pages 59-70
New Models and Algorithms for Throughput Maximization in Broadcast Scheduling....Pages 71-82
Densest k -Subgraph Approximation on Intersection Graphs....Pages 83-93
The Train Delivery Problem - Vehicle Routing Meets Bin Packing....Pages 94-105
An FPTAS for Flows over Time with Aggregate Arc Capacities....Pages 106-117
List Factoring and Relative Worst Order Analysis....Pages 118-129
Approximation Algorithms for Domination Search....Pages 130-141
Lower Bounds for Smith’s Rule in Stochastic Machine Scheduling....Pages 142-153
Approximating Survivable Networks with Minimum Number of Steiner Points....Pages 154-165
A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks....Pages 166-177
Online Tracking of the Dominance Relationship of Distributed Multi-dimensional Data....Pages 178-189
How to Play Unique Games on Expanders....Pages 190-200
Online Ranking for Tournament Graphs....Pages 201-212
Throughput Maximization for Periodic Packet Routing on Trees and Grids....Pages 213-224
k -Edge-Connectivity: Approximation and LP Relaxation....Pages 225-236
Minimizing Maximum Flowtime of Jobs with Arbitrary Parallelizability....Pages 237-248
An Improved Algorithm for Online Rectangle Filling....Pages 249-260
Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems....Pages 261-272
Back Matter....Pages -

✦ Subjects

Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Computer Graphics; Information Systems Applications (incl.Internet); Algorithms