Approximation and Online Algorithms
Description
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, echanism
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.
More details
Other editions
Additional editions
Content
- Title Page
- Preface
- Organization
- Table of Contents
- WAOA 2010
- Strategic Multiway Cut and Multicut Games
- Introduction and Model
- Preliminaries and Basic Results
- Single-Source Network Cutting Game
- Network Multiway Cut Game
- Poly-time Computable Nash Equilibrium
- Network Multicut Game
- Edges with Non-uniform Costs
- References
- Approximating Directed Buy-at-Bulk Network Design
- Introduction
- Preliminaries
- Structural Results
- Approximation Algorithms
- Concluding Remarks and Open Problems
- References
- New Lower Bounds for Certain Classes of Bin Packing Algorithms
- Introduction
- Reformulated Packing Pattern Technique
- The Right Choice of the Weights
- The New Parametric On-Line Lower Bound
- Improved Lower Bound for Decreasing Lists
- Conclusions
- References
- On the Approximation Complexity Hierarchy
- Introduction
- Preliminaries
- Results
- Proofs
- Restricted Power Oracles
- References
- The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers
- Introduction
- Preliminaries
- Contributions
- A Polynomial-Time Algorithm for Uniform UdBp-Min
- Hardness of Approximation of UdBp-Min
- Approximation Algorithm for Non-Uniform UdBp-Min
- Approximability of UdBp-Max
- Conclusions
- References
- Tradeoff between Energy and Throughput for Online Deadline Scheduling
- Introduction
- Preliminaries
- Unbounded Speed Model
- Algorithm PS(c)
- Value Discarded by PS(c)
- Energy Usage of PS(c)
- Bounded Speed Model
- Lower Bound
- Algorithm BPS
- References
- New Models and Algorithms for Throughput Maximization in Broadcast Scheduling
- Introduction
- Preliminaries
- An LP Relaxation for MAX-THP
- Dependent Rounding Scheme of [17]
- Throughput and Profit Maximization
- Offline Algorithms
- Online Algorithms
- References
- Densest k-Subgraph Approximation on Intersection Graphs
- Introduction
- Preliminaries
- Elimination Orders and Intersection Graphs
- Approximating DS-k on Graphs with s-QEO
- The Maximum Density Subgraph Problem (MDSP)
- A Constant Factor Approximation Framework
- A PTAS for DS-k on Unit Disk Graphs
- Conclusions
- References
- The Train Delivery Problem - Vehicle Routing Meets Bin Packing
- Introduction
- Algorithm for Theorem 1
- Rounding
- Partitioning into Regions
- Solving the Relaxed Problem in a Region
- Extending a Relaxed Solution of the Region
- Algorithm for Theorem 2
- Partitioning into Close and Far
- Solving the Far Instance
- References
- An FPTAS for Flows over Time with Aggregate Arc Capacities
- Introduction
- Aggregate Arc Capacities
- Discretizations
- Path Decompositions
- Understanding the Problem
- Approximation Scheme
- Conclusion
- References
- List Factoring and Relative Worst Order Analysis
- Introduction
- List Accessing
- Relative Worst Order Analysis
- List Factoring
- Worst Orderings
- Algorithm Comparisons
- Deterministic Algorithms
- Randomized Algorithms
- Open Problems
- References
- Approximation Algorithms for Domination Search
- Introduction
- Definitions and Preliminaries
- r-Domination Cop Number for Apex-Minor-Free Graphs
- r-Domination Cop Number for H-Minor-Free Graphs
- Graph Minor Theorem and Preliminary Results
- Approximation of the r-Domination Cop Number
- Open Problems
- References
- Lower Bounds for Smith's Rule in Stochastic Machine Scheduling
- Introduction
- The Kawaguchi and Kyan Instance
- Preliminaries on Jobs with Exponentially Distributed Processing Times
- The Stochastic Instance
- Intuition about the Schedules
- Lower Bound on Performance of WSEPT
- Conclusion
- References
- Approximating Survivable Networks with Minimum Number of Steiner Points
- Introduction
- Problem Definition and Motivation
- Our Results
- Proof of the Main Result
- References
- A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks
- Introduction
- Related Work
- Our Contribution
- Preliminaries
- Matchings and Schedules
- The Algorithm
- Experimental Results
- References
- Online Tracking of the Dominance Relationship of Distributed Multi-dimensional Data
- Introduction
- Definitions and Lower Bound
- Structures and Crossings
- Cell Intersection and Smallest Rectangles
- Crossings
- Algorithm
- Analysis
- References
- How to Play Unique Games on Expanders
- Introduction
- Overview
- Preliminaries
- Expanders: Second Eigenvalue and Edge Expansion
- Semidefinite Relaxation for Unique Games
- Algorithm
- References
- Online Ranking for Tournament Graphs
- Introduction
- Online Feedback Arc Set on Tournaments
- Analysis of Greedy
- Deterministic and Randomized Lower Bounds
- Random Order Arrivals: A Better Algorithm
- Random Order Lower Bounds
- Maximum Acyclic Subgraph
- Analysis of Greedy
- Deterministic and Randomized Lower Bounds
- Random Order Arrivals
- References
- Throughput Maximization for Periodic Packet Routing on Trees and Grids
- Introduction
- Our Contribution
- Related Work
- Unweighted Tasks in Bidirected Trees
- Weighted Tasks on Bidirected Trees
- Price of Directness on Trees
- Grid Graphs
- References
- k-Edge-Connectivity: Approximation and LP Relaxation
- Introduction
- Contributions
- Hardness Results
- k-ECSM Conjecture and Connectivity Decomposition
- Complex Extreme Points for (N'2)
- Relation to Asymmetric TSP
- References
- Minimizing Maximum Flowtime of Jobs with Arbitrary Parallelizability
- Introduction
- Previous Results
- Our Results
- Definitions and Notation
- The Lower Bound on the Competitive Ratio
- Analysis of the Batching Algorithm on ParSeq Instances
- The General Lower Bound
- Reduction from the General Setting to ParSeq Instances
- References
- An Improved Algorithm for Online Rectangle Filling
- Introduction
- Lower Bound
- Algorithm MoreFilling
- Analysis
- Block Partitioning
- Conclusions
- References
- Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems
- Background and Challenges
- Basic Definitions
- Signatures, Holant Problems, and #CSPs
- Randomized Approximation Schemes
- T-Constructibility
- Relations and Signature Sets
- Counting Complex-Weighted Solutions
- Elementary AP-Reductions
- Affine Support and Imp Support
- Lower Bounds of #CSP*s
- The Trichotomy Theorem
- References
- Author Index
