Algorithms -- ESA 2011

Name: Algorithms -- ESA 2011 | 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011, Proceedings
Brand: Springer
Price: 96.29 EUR
Availability: OnlineOnly

19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011, Proceedings

Camil Demetrescu Magnus M. Halldorsson(Herausgeber*in)

Springer (Verlag)

Erschienen am 31. August 2011

XIX, 813 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-23719-5 (ISBN)

96,29 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken