Algorithms -- ESA 2011
19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011, Proceedings
Published on 31. August 2011
XIX, 813 pages
978-3-642-23719-5 (ISBN)
Description
This book constitutes the refereed proceedings of the 19th Annual European Symposium on Algorithms, ESA 2011, held in Saarbrücken, Germany, in September 2011 in the context of the combined conference ALGO 2011.
The 67 revised full papers presented were carefully reviewed and selected from 255 initial submissions: 55 out of 209 in track design and analysis and 12 out of 46 in track engineering and applications. The papers are organized in topical sections on approximation algorithms, computational geometry, game theory, graph algorithms, stable matchings and auctions, optimization, online algorithms, exponential-time algorithms, parameterized algorithms, scheduling, data structures, graphs and games, distributed computing and networking, strings and sorting, as well as local search and set systems.
More details
Other editions
Additional editions
Camil Demetrescu | Magnus M. Halldorsson
Algorithms -- ESA 2011
19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011, Proceedings
Book
09/2011
Springer
€106.99
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Approximation Algorithms I
- Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility under Budget Constraints
- Introduction
- Gross Substitutes Utility and M-Concave Functions
- PTAS for k-Budgeted M-Concave Maximization
- PTAS for 1-Budgeted M-Concave Intersection
- References
- Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph
- Introduction
- Definitions and Notation
- Approximation Algorithms
- Minimal k-VCSS
- The Cheriyan-Thurimella Algorithm
- Linear-Time Algorithm
- Hybrid Algorithms
- Experimental Results
- Implementation and Experimental Setup
- Instances
- Evaluation
- References
- Improved Approximation Algorithms for Bipartite Correlation Clustering
- Introduction
- Our Results
- Paper Structure
- A Deterministic LP Rounding Algorithm
- The Combinatorial 4-Approximation Algorithm
- Notation
- Algorithm Description
- Algorithm Analysis
- Contradicting Structures
- Obtaining the Competitive Analysis
- Future Work
- References
- Bounds on Greedy Algorithms for MAX SAT
- Introduction
- Priority Algorithms for MAX SAT
- The Slack-Algorithm
- Limits of Priority Algorithms for MAX SAT
- Optimal Bounds for Online MAX SAT
- Adaptive Priority Algorithms for MAX SAT
- A Refined Analysis of the Slack-Algorithm
- References
- Computational Geometry I
- Approximating Minimum Manhattan Networks in Higher Dimensions
- Introduction
- k-Plane Case
- Two Planes
- Recursive Algorithm for k Planes
- General Case
- Open Problems
- References
- On Isolating Points Using Disks
- Introduction
- Preliminaries
- Separating Two Points
- Bounding the Size of the Output
- Separating Multiple Points
- Conclusions
- References
- An Output-Sensitive Approach for the L1/L$_8$ k-Nearest-Neighbor Voronoi Diagram
- Introduction
- The k-Nearest-Neighbor Delaunay Graph
- Paradigm for the k-NN Delaunay Graph in R2
- k-NN Delaunay Triangles, Circuits, Components and Hull
- Traversal-Based Operation among Triangles
- Planar k-NN Delaunay Graph in the L$_8$ Metric
- L$_8$ k-NN Delaunay Hull Computation
- L$_8$ k-NN Traversal Operation among Triangles
- Complexity of L$_8$ k-NN Voronoi Diagram
- Conclusion
- References
- Can Nearest Neighbor Searching Be Simple and Always Fast?
- Introduction
- Preliminaries
- A Voronoi Diagram Construction
- Exponentiality of the Construction
- Conclusions and Remarks
- References
- Game Theory
- On the Approximation Performance of Fictitious Play in Finite Games
- Introduction
- Lower Bound
- Upper Bound
- Discussion
- References
- How Profitable Are Strategic Behaviors in a Market?
- Introduction
- Related Work
- Preliminaries
- Market Equilibrium Mechanism
- Incentive Ratio
- Incentive Ratio Is Independent of the Number of Buyers
- Incentive Ratio Is Independent of the Number of Items
- Proof of Theorem 4
- Conclusions
- References
- Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms
- Introduction
- Continuous Latency Functions Yield No Improvement
- A Simple Coordination Mechanism
- Two Links
- Many Links
- An Improved Mechanism for the Case of Two Links
- A Lower Bound for the Case of Two Links
- Open Problems
- References
- Graph Algorithms I
- Algorithms for Finding a Maximum Non-k-linked Graph
- Introduction
- Weakly 2-Linkedness of Graphs
- 2-Linkedness of Graphs
- Finding a Vertex Set X with |X| = c -4
- Finding a Vertex Set X with |X| = c -3
- NP-Hardness of Max 2-VDP-free Induced Subgraph
- References
- An O(n$^4$) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs
- The Problem and Our New Approach
- Properties of Optimal k-Cuts
- Computing Optimal k-Cuts
- Counting Segments and IFS Covering Sets
- Discussion
- References
- Min-Cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time
- Introduction
- Preliminaries
- Chalermsook et al. Algorithm
- An O(n logn) Time Algorithm
- An O(n loglogn) Time Algorithm
- Dividing Step
- Conquering Step
- Reducing Step
- Terminal Step
- Dynamic Shortest Cycle
- Shortest Cycles through Given Edge
- Data Structures and Updates
- References
- Stable Matchings and Auctions
- Near-Popular Matchings in the Roommates Problem
- Introduction
- A Low Unpopularity Factor Matching
- Our Algorithm
- Least Unpopularity Factor Matching
- Correctness of Our Reduction
- References
- The Hospitals/Residents Problem with Quota Lower Bounds
- Introduction
- Preliminaries
- Minimum-Blocking-Pair HRMQ
- Exponential-Time Exact Algorithm
- Minimum-Blocking-Resident HRMQ
- Our Algorithm
- Analysis of the Approximation Ratio
- Inapproximability of Min-BR HRMQ
- Concluding Remarks
- References
- Multi-parameter Mechanism Design under Budget and Matroid Constraints
- Introduction
- Problem Definition
- Correlated Item Valuations
- Independent Item Valuations
- Valuation Distributions with Monotone Hazard Rate
- Constant Approximations for Specific Matroids and MHR
- References
- Optimization
- Quantified Linear Programs: A Computational Study
- Introduction
- State-of-the-Art
- The Problem Statement: Quantified Linear Programs
- How to Solve QLP Problems
- Equivalent Linear Program Formulations of SLPs and QLPs
- Nested Benders Decomposition
- Computational Experiments
- The Data Set
- Analysis of Twostage QLPs
- Analysis of Multistage QLPs
- Conclusion and Further Work
- References
- Recoverable Robustness by Column Generation
- Introduction
- Recoverable Robustness
- Size Robust Knapsack Problem
- Separate Recovery Decomposition
- Combined Recovery Decomposition
- Demand Robust Shortest Path Problem
- Computational Results
- Generalization and Conclusion
- References
- Passenger Flow-Oriented Train Disposition
- Introduction
- Model
- Timetable and Events
- The Event Graph
- Passenger Flows and Objective Functions
- Algorithmic Approach
- Experiments
- Conclusions and Future Work
- References
- Online Algorithms I
- One to Rule Them All: A General Randomized Algorithm for Buffer Management with Bounded Delay
- Introduction
- Competitive Analysis
- Basic Definitions
- Previous and Related Work, Restricted Variants
- Our Contribution
- General Upper Bound
- Analysis Technique
- The Algorithm
- Rationale behind the Probability Distribution
- Optimality for Item Collection
- Implications for Restricted Variants
- Conclusion and Open Problems
- References
- Better Bounds for Incremental Frequency Allocation in Bipartite Graphs
- Introduction
- Preliminaries
- Competitive F-Systems
- An Upper Bound
- A Lower Bound
- Final Comments
- References
- Two-Bounded-Space Bin Packing Revisited
- Introduction
- Technical Preliminaries
- An Offline Approximation Algorithm
- Relaxed Packings
- Proof of the Transformation from the Initial Segment Lemma
- Proof of the Initial Segment Lemma
- An Asymptotic Lower Bound for Offline Algorithms
- Absolute Bounds for Offline Algorithms
- An Asymptotic Lower Bound for Online Algorithms
- References
- Exponential-Time Algorithms
- Output-Sensitive Listing of Bounded-Size Trees in Undirected Graphs
- Introduction
- Preliminaries
- Basic Approach: Recursion Tree
- Improved Approach: Certificates
- Introducing Certificates
- Maintaining the Invariant Using a New choose
- Analysis
- Optimal Approach: Amortization
- Internal Edges of V[S]
- Amortization
- References
- Exact Algorithm for the Maximum Induced Planar Subgraph Problem
- Introduction
- Preliminaires
- Minimal Triangulations of Planar Graphs
- Proof of Theorem 1
- Open Questions
- References
- Scheduling Partially Ordered Jobs Faster Than 2$n^$
- Introduction
- The Algorithm
- High-Level Overview-Part 1
- The Large Matching Case
- High-Level Overview-Part 2
- Technical Preliminaries
- The Core Lemma
- Important Jobs at n/2
- Quarters and Applications of the Core Lemma
- The Remaining Case
- Conclusion
- References
- Online Algorithms I
- AdCell: Ad Allocation in Cellular Networks
- Introduction
- AdCell Model and Problem Formulation
- Our Results and Techniques
- Related Work
- Online Setting
- Offline Setting
- References
- Submodular Max-SAT
- Introduction
- Preliminaries
- A Linear Time Approximation Algorithm
- Submodular Maximization under a Binary Partition Matroid
- The Algorithm
- A Hardness Bound for the Online Version
- A Hardness Bound for the Offline Version
- Concluding Remarks
- References
- On Variants of the Matroid Secretary Problem
- Introduction
- Recent Related Work
- Our Results
- Approximation for Adversarial Order and Random Assignment
- Approximation Algorithms for Unknown Matroids
- Classical Secretary with Unknown n
- References
- Hitting Sets Online and Vertex Ranking
- Introduction
- Preliminaries
- Summary of Our Results
- Vertex Ranking and Online Hitting-Set Algorithms
- Applications to Geometric Range-spaces
- Vertices and Connected Subgraphs
- An Online Hitting Set Algorithm
- Analysis of the Competitive Ratio
- An Algorithm for Vertex Ranking
- Points and Half-Planes
- Analysis of the Competitive Ratio
- Points and Unit Discs
- Lower Bounds
- A Path of n Vertices
- Points and Half-Planes
- References
- Parameterized Algorithms
- Fast Sub-exponential Algorithms and Compactness in Planar Graphs
- Introduction
- Basic Definitions and Preliminaries
- Radially Extremal Sets and Branchwidth
- Conclusions and Open Problems
- References
- Isomorphism of (mis)Labeled Graphs
- Introduction
- The Permutation Distance as Similarity Measure
- Correctness:
- Running Time:
- Extension to Maximum Common Subgraph Distance
- Similarity Measures and Intractability
- References
- Paths, Flowers and Vertex Cover
- Introduction
- Preliminaries
- Outline of the Algorithm
- König Graphs with Extendable Vertex Covers
- Important Separators and the Algorithm
- Conclusion
- References
- Hitting and Harvesting Pumpkins
- Introduction
- Preliminaries
- A Single-Exponential FPT Algorithm
- An Approximation Algorithm for Hitting and Packing Pumpkins
- Concluding Remarks
- References
- Best Paper Session
- Deterministic Discrepancy Minimization
- Introduction
- Preliminaries
- Spencer's Bound
- Algorithm (Phase 1)
- Analysis
- Pseudo-approximation for Discrepancy
- Algorithm
- Analysis
- References
- Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
- Introduction
- Overview of the Algorithm
- Preliminaries
- Snippets Toolbox
- Constructing Balanced Grammar
- Processing Balanced Grammar
- Conclusions
- References
- Graph Algorithms I
- An Experimental Study on Approximating K Shortest Simple Paths
- Introduction
- Bernstein's Approach
- A Practical Improvement
- Implementation Issues
- Experimental Results
- Results for Road Maps
- Results for Square Grids
- Results for Rectangle Grids
- References
- Scope-Based Route Planning
- Introduction
- Preliminaries
- The New Concept - Scope
- S-Dijkstra's Algorithm and S-Reach
- The Route-Planning Algorithm
- Preprocessing into a Boundary Graph
- Route Planning Query
- Conclusions
- References
- Maximum Flows by Incremental Breadth-First Search
- Introduction
- Definitions and Notation
- BK Algorithm
- Incremental Breadth-First Search
- Correctness and Running Time
- VariantsofIBFS
- Experimental Results
- Implementation Details
- Experiments
- Concluding Remarks
- References
- Engineering Multilevel Graph Partitioning Algorithms
- Introduction
- Preliminaries
- Basic Concepts
- Related Work
- Local Improvement
- Max-Flow Min-Cut Computations for Local Improvement
- Multi-try FM
- Scheduling Quotient Graph Refinement
- Global Search
- Experiments
- Insights about Flows
- Insights about Global Search Strategies
- Removal / Knockout Tests
- Comparison with Other Partitioners
- The Walshaw Benchmark
- Conclusions and Future Work
- References
- Computational Geometry II
- A Nearly Optimal Algorithm for Finding L$_1$ Shortest Paths among Polygonal Obstacles in the Plane
- Introduction
- Shortest Paths among Convex Obstacles
- Notation and Observations
- The Shortest Path Algorithm
- Computing a Shortest Path Map
- Shortest Paths among General Polygonal Obstacles
- Preprocessing
- The Main Algorithm
- Applications
- References
- Motion Planning via Manifold Samples
- Introduction
- Contribution
- General Scheme for Planning with Manifold Samples
- Desirable Properties of Manifold Families
- Exploration and Connection Strategies
- The Case of Rigid Polygonal Motion
- Manifold Families
- Exploration and Connection Strategies
- Path Planning Query
- Efficient Implementation of Manifold Decomposition
- Experimental Results
- Algorithm Properties
- Comparison with PRM
- Further Directions
- References
- Ray-Shooting Depth: Computing Statistical Data Depth of Point Sets in the Plane
- Introduction
- Computing a Point of Ray-Shooting Depth at Least n2/9
- Computing a Point of Ray-Shooting Depth Approximately n$^2$/9
- Implementation
- References
- Improved Algorithms for Partial Curve Matching
- Introduction
- Preliminaries
- The Data Structure
- Applications
- Matching a Curve in a DAG
- Conclusions
- References
- Scheduling
- On the Configuration-LP for Scheduling on Unrelated Machines
- Introduction
- Related Work
- Our Contribution
- LP-Based Approaches
- Integrality Gap of the Configuration-LP
- Unrelated Graph Balancing Case of MaxMin-Allocation
- References
- Resource Allocation for Covering Time Varying Demands
- Introduction
- Approximating the Partial MultiResAll Problem
- Existence of Good SRA Covers
- Computing Optimal SRA Covers
- Approximation Algorithm for the (0,1)-ResAll Problem
- References
- Mixed-Criticality Scheduling of Sporadic Task Systems
- Introduction
- Model
- Single Machine
- Two Criticality Levels
- K Criticality Levels
- Multiple Identical Machines
- Scheduling a Finite Collection of Independent Jobs
- Scheduling a Sporadic Task System
- References
- Robust Algorithms for Preemptive Scheduling
- Introduction
- An Optimal Robust Algorithm for Identical Machines
- Properties of Load Vectors in Strongly Optimal Solutions
- The Procedure Assign
- A Robust Algorithm
- Lower Bounds on the Migration Factor
- References
- Data Structures
- Approximate Distance Queries for Weighted Polyhedral Surfaces
- Introduction
- Preliminaries
- Definitions
- Domain Discretization
- Approximate Distance Oracles for Planar Graphs
- Discretization, Pseudo-planarization, and Separator Decomposition
- Discretizing the Weights
- Pseudo-planarization
- Preprocessing Algorithm
- Answering Approximate Shortest-Path Queries
- Overview of the Method
- Divide-and-Conquer Approach
- Proof of Theorem 2
- References
- The Union of Probabilistic Boxes: Maintaining the Volume
- Introduction
- Probabilistic Volume: Expectation and Tail Bounds
- Maintaining the Expected Measure in 1D
- Anonymous Segment Tree
- An Abstract Anonymous Segment Tree
- Measure of Probabilistic Segments
- Dynamic Probabilistic Volume in d Dimensions
- Discrete Volume
- Experimental Evaluation
- Conclusions
- References
- Preprocess, Set, Query!
- Introduction
- Preprocess
- Set
- Query
- Concluding Remarks and Open Problems
- References
- Cuckoo Hashing with Pages
- Introduction
- Problem Description
- Algorithms
- Experiments
- Static Case
- Dynamic Case
- Conclusion
- References
- Approximation Algorithms I
- Approximation Algorithms and Hardness Results for the Joint Replenishment Problem with Constant Demands
- Introduction
- A Hardness Result for GICF
- Approximation Algorithm for Finite Horizon
- GI Model
- References
- Approximation Algorithms for Conflict-Free Vehicle Routing
- Introduction
- Tree Approximation
- Hot Spot Routing
- Low-Stretch Routing
- References
- A 3/2Approximation for a Constrained Forest Problem
- Introduction
- Algorithm Outline
- Analysis of the Algorithm
- Notations and Definitions
- Preliminary Lemmas
- Main Inequality
- Conclusion
- References
- Graphs and Games
- External-Memory Network Analysis Algorithms for Naturally Sparse Graphs
- Introduction
- Naturally Sparse Graphs
- External-Memory Algorithms
- Previous Related Work
- Our Results
- Approximating a d-Degeneracy Ordering
- Short Paths and Cycles
- All Maximal Cliques
- References
- Approximate Counting of Cycles in Streams
- Introduction
- A Review of Jowhari and Ghodsi's Algorithm
- Algorithm Framework
- Proof of the Main Theorem
- Conclusions
- References
- Algorithms for Solving Rubik's Cubes
- Introduction
- Common Definitions
- Diameter of n × n × 1× Rubik's Cube
- n × n × 1 Upper Bound
- n × n × 1 Lower Bound
- Diameter of n × n × n Rubik's Cube
- n × n × n Upper Bound
- n × n × n Lower Bound
- Optimally Solving a Subset of the n × n × 1 Rubik's Cube is NP-Hard
- Optimally Solving an O(1) × O(1) × n Rubik's Cube
- References
- Distributed Computing and Networking
- Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
- Introduction
- Boundary Patrolling Algorithms
- Fence Patrolling: The Proportional Solution
- Patrolling a Unidirectional Boundary
- Allowing Movement in Both Directions
- Conclusion and Open Problems
- References
- Optimal Discovery Strategies in White Space Networks
- Introduction
- Optimal Discovery Strategies
- Applications in Wireless Networking and Related Work
- Related Work on Rendezvous Games
- Analysis of Discovery Strategies
- Proof of Theorem 1, Upper Bound on the Discovery Time
- Proof of Theorem 1, Lower Bound on the Discovery Time
- References
- Social-Aware Forwarding Improves Routing Performance in Pocket Switched Networks
- Introduction
- The Network Model
- Bounds on the Expected Delivery Time
- Extensions
- Simulations
- Real-World Trace Based Evaluation
- Synthetic Data Simulation
- Discussion
- Conclusion
- References
- Strings and Sorting
- Tolerant Algorithms
- Introduction
- Finding the Maximum of n Numbers
- Sorting
- Searching
- Linear Programming in 2 Dimensions
- References
- Alphabet-Independent Compressed Text Indexing
- Introduction
- Compressed Self-indexes
- Monotone Minimal Perfect Hash Functions
- Fast Locating and Extracting Using Select
- Improving Child Operation in Suffix Trees
- Improving Counting Time in Compressed Suffix Trees
- Backward Search in O(m) Time
- Final Remarks
- References
- Distribution-Aware Compressed Full-Text Indexes
- Introduction
- Background
- The FM-Index Family
- The CSA Family
- Locate and Extract Queries
- Optimal Distribution-Aware Locate and Extract
- On Finding a Minimum Weight K-Link Path over a DAG
- Experiments
- Future Work
- References
- Local Search and Set Systems
- Smoothed Performance Guarantees for Local Search
- Introduction
- Unrestricted Related Machines
- Jump Optimal Schedules
- List Schedules and Lex-Jump Optimal Schedules
- Restricted Machines
- Jump Neighborhood on Restricted Machines
- Lex-Jump Optimal Schedules on Restricted Identical Machines
- Concluding Remarks
- References
- Improved Approximations for k-Exchange Systems
- Introduction
- Our Results
- Related Work
- Preliminaries
- Applications
- Combinatorial Local Search Approximation Algorithms
- Analysis of Algorithm 1
- Analysis of Algorithm 2
- Open Questions
- References
- Cover-Decomposition and Polychromatic Numbers
- Introduction
- Terminology and Notation
- Results
- Related Work
- Hypergraphs of Bounded Edge Size
- Lower Bounds
- Paths in Trees
- Future Work
- References
- Author Index
