Approximation and Online Algorithms
9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers
Published on 26. March 2012
X, 278 pages
978-3-642-29116-6 (ISBN)
Description
This book constitutes the thoroughly refereed post-proceedings of the 9th International Workshop on Approximation and Online Algorithms, WAOA 2011, held in Saarbrücken, Germany, in September 2011.
The 21 papers presented were carefully reviewed and selected from 48 submissions. The volume also contains an extended abstract of the invited talk of Prof. Klaus Jansen.
The Workshop on Approximation and Online Algorithms focuses on the design and analysis of algorithms for online and computationally hard problems. Both kinds of problems have a large number of applications
in a wide variety of fields. Topics of interest for WAOA 2011 were: 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 and scheduling problems.
More details
Other editions
Additional editions
Roberto Solis-Oba | Giuseppe Persiano
Approximation and Online Algorithms
9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers
Book
03/2012
Springer
€53.49
Shipment within 7-9 days
Content
- Title Page
- Preface
- Organization
- Table of Contents
- Approximation Algorithms for Schedulingand Packing Problems
- Introduction
- Scheduling with Fixed Jobs
- Related Results
- New Results
- 2D Strip Packing
- Related Work
- New Results
- Multiple Knapsack Problem
- Known Results
- New Results
- Scheduling on Uniform Processors
- Known Results
- New Results
- References
- Approximating Subset $k$ -Connectivity Problems
- Introduction
- Proof of Theorem 1
- Proof of Theorem 2
- Proof of Theorem 3
- References
- Learning in Stochastic Machine Scheduling
- Introduction
- Preliminaries and Scheduling Policies
- Bayesian Methodology
- Bayesian Scheduling Policies
- Bounds on Scheduling Policies
- Upper Bound on Performance Guarantees
- Tightness of the Performance Guarantees
- Lower Bound on the Performance Guarantee of SEPT
- Lower Bound on the Performance Guarantee of -SEPT
- Computational Results
- Concluding Remarks
- References
- An Online Algorithm Optimally Self-tuning to Congestion for Power Management Problems
- Introduction
- Problem Statement
- Our Algorithm
- Decrease and Reset Algorithm (DRA)
- How to Set the Coefficients for ``Optimality
- Queueing Analysis
- Analysis
- Numerical Examples
- Conclusions
- References
- Single Approximation for Biobjective Max TSP
- Introduction
- Preliminaries
- Non Existence of a Single -Approximate Solution
- A Generic Algorithm for Biobjective Max TSP
- An Improved Analysis
- Future Work
- References
- Parameterized Approximation Algorithms for Hitting Set
- Introduction
- A Simple Design for Parameterized Approximation
- A Simple Branching for Approximation
- A More Elaborated Analysis of a Factor-2 Approximation Algorithm for 3-HS
- Approximating 3-HS with Degree Constraints
- Further Questions
- References
- Approximation Algorithmsfor the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs
- Introduction
- Indegree-Based Algorithm
- Expansion Algorithm
- Expansion Algorithm for Undirected Graphs
- Expansion Algorithm for Acyclic Digraphs
- Performance Guarantee
- Tight Example
- MaxSNP-Hardness
- Concluding Remarks
- References
- Optimization over Integers with Robustness in Cost and Few Constraints
- Introduction
- Uncertainty in the Objective
- Uncertainty in Constraints
- Applications
- References
- A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines without Preemption
- Introduction
- Lower Bound
- Conclusions
- References
- Scheduling Jobs on Identical and Uniform Processors Revisited
- Introduction
- Bounds for max-Gap(A) and the Running-Time
- Scheduling on Uniform Processors
- Algorithm for Case 3
- References
- Approximation Algorithms for Fragmenting a Graph against a Stochastically-Located Threat
- Introduction
- 2-Stage Stochastic Graph Protection Problem in Trees
- 1-Stage Extension to Probabilistic Edge Transmission
- References
- Non-clairvoyant Weighted Flow Time Scheduling on Different Multi-processor Models
- Introduction
- Formal Problem Definitions
- Analyzing WLAPS for Homogeneous Processors
- Restricting the Input Instance
- A Lower Bound on WOpt
- Potential Function Analysis
- An O(1)-Competitive Algorithm for Two Functionality Types
- Restricting the Input Instance
- A Lower Bound of Opt
- Potential Function Analysis
- A Better Competitive Algorithm with $m_1 = m_ 2 = 1$
- References
- A New Perspective on List Update: Probabilistic Locality and Working Set
- Introduction
- List Update with Locality of Reference
- Working Set Property for List Update
- Experimental Results
- Conclusions
- References
- OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm
- Introduction
- Randomized Selection Process
- Preliminaries
- Selection Process for OnlineMin
- Probability Distribution of Ck
- Algorithm OnlineMin
- Algorithm
- Algorithm Implementation
- Data Structures
- References
- Faster and Simpler Approximation of Stable Matchings
- Introduction
- Algorithm
- Description of Algorithm GS Modified
- Correctness of Algorithm GS Modified
- Extension to Stable b-Matchings
- Data Structures and Running Time
- Correctness of Algorithm ASBM
- References
- Simpler 3/4-Approximation Algorithms for MAX SAT
- Introduction
- Analysis with a Potential Function
- Poloczek and Schnitger's Potential Function
- A New Combinatorial Randomized Algorithm
- A New Deterministic LP Rounding Algorithm
- Conclusion and Future Directions
- References
- On Online Algorithms with Advice for the $k$ -Server Problem
- Introduction
- Preliminaries
- An Upper Bound for General Metric Spaces
- $k$ -Server with Advice on Trees
- Non-lazy Optimum
- The Algorithm
- Special Metric Spaces and PATH-COVER
- Conclusions
- References
- Improved Lower Bound for Online Strip Packing
- Introduction
- Sequence Construction
- Lower Bound
- Upper Bound
- References
- Competitive Router Scheduling with Structured Data
- Introduction
- Preliminaries
- Models
- Algorithm
- Multiple Capacitated Links
- Analysis of Algorithm PLink
- A Lower Bound
- The Effect of Many Links and Large Capacity
- Extensions
- Effective Redundancy
- Multiple Service Levels
- Instantaneous Network Model
- References
- Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems
- Introduction
- Preliminaries on Multi-objective Optimization and Approximation
- Approximation with a Given Number of Solutions
- Max Pos NAE
- Max Partition
- Max Matching
- Approximation with One Solution
- Max Bisection
- Conclusion
- References
- Generalized Maximum Flows over Time
- Introduction
- Preliminaries
- Complexity and Hardness of Approximation
- Lossy Networks
- Proportional Losses
- A Variant of the Successive Shortest Path Algorithm
- Turning the Algorithm into an FPTAS
- Conclusion
- References
- The Price of Anarchy for Minsum Related Machine Scheduling
- Introduction
- Characterization of Optimal Solutions
- Coordination Mechanism and Nash Equilibria
- Upper Bound on the Price of Anarchy
- Lower Bound on the Price of Anarchy
- Concluding Remarks
- References
- Author Index
