Algorithms – ESA 2011: 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings

Front Matter....Pages -
Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility under Budget Constraints....Pages 1-12
Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph....Pages 13-24
Improved Approximation Algorithms for Bipartite Correlation Clustering....Pages 25-36
Bounds on Greedy Algorithms for MAX SAT....Pages 37-48
Approximating Minimum Manhattan Networks in Higher Dimensions....Pages 49-60
On Isolating Points Using Disks....Pages 61-69
An Output-Sensitive Approach for the L 1 / L  ∞  k -Nearest-Neighbor Voronoi Diagram....Pages 70-81
Can Nearest Neighbor Searching Be Simple and Always Fast?....Pages 82-92
On the Approximation Performance of Fictitious Play in Finite Games....Pages 93-105
How Profitable Are Strategic Behaviors in a Market?....Pages 106-118
Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms....Pages 119-130
Algorithms for Finding a Maximum Non- k -linked Graph....Pages 131-142
An $\mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs....Pages 143-154
Min-Cuts and Shortest Cycles in Planar Graphs in O ( n loglog n ) Time....Pages 155-166
Near-Popular Matchings in the Roommates Problem....Pages 167-179
The Hospitals/Residents Problem with Quota Lower Bounds....Pages 180-191
Multi-parameter Mechanism Design under Budget and Matroid Constraints....Pages 192-202
Quantified Linear Programs: A Computational Study....Pages 203-214
Recoverable Robustness by Column Generation....Pages 215-226
Passenger Flow-Oriented Train Disposition....Pages 227-238
One to Rule Them All: A General Randomized Algorithm for Buffer Management with Bounded Delay....Pages 239-250
Better Bounds for Incremental Frequency Allocation in Bipartite Graphs....Pages 251-262
Two-Bounded-Space Bin Packing Revisited....Pages 263-274
Output-Sensitive Listing of Bounded-Size Trees in Undirected Graphs....Pages 275-286
Exact Algorithm for the Maximum Induced Planar Subgraph Problem....Pages 287-298
Scheduling Partially Ordered Jobs Faster Than 2 n ....Pages 299-310
AdCell: Ad Allocation in Cellular Networks....Pages 311-322
Submodular Max-SAT....Pages 323-334
On Variants of the Matroid Secretary Problem....Pages 335-346
Hitting Sets Online and Vertex Ranking....Pages 347-357
Fast Sub-exponential Algorithms and Compactness in Planar Graphs....Pages 358-369
Isomorphism of (mis)Labeled Graphs....Pages 370-381
Paths, Flowers and Vertex Cover....Pages 382-393
Hitting and Harvesting Pumpkins....Pages 394-407
Deterministic Discrepancy Minimization....Pages 408-420
Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic....Pages 421-432
An Experimental Study on Approximating K Shortest Simple Paths....Pages 433-444
Scope-Based Route Planning....Pages 445-456
Maximum Flows by Incremental Breadth-First Search....Pages 457-468
Engineering Multilevel Graph Partitioning Algorithms....Pages 469-480
A Nearly Optimal Algorithm for Finding L 1 Shortest Paths among Polygonal Obstacles in the Plane....Pages 481-492
Motion Planning via Manifold Samples....Pages 493-505
Ray-Shooting Depth: Computing Statistical Data Depth of Point Sets in the Plane....Pages 506-517
Improved Algorithms for Partial Curve Matching....Pages 518-529
On the Configuration-LP for Scheduling on Unrelated Machines....Pages 530-542
Resource Allocation for Covering Time Varying Demands....Pages 543-554
Mixed-Criticality Scheduling of Sporadic Task Systems....Pages 555-566
Robust Algorithms for Preemptive Scheduling....Pages 567-578
Approximate Distance Queries for Weighted Polyhedral Surfaces....Pages 579-590
The Union of Probabilistic Boxes: Maintaining the Volume....Pages 591-602
Preprocess, Set, Query! ....Pages 603-614
Cuckoo Hashing with Pages....Pages 615-627
Approximation Algorithms and Hardness Results for the Joint Replenishment Problem with Constant Demands....Pages 628-639
Approximation Algorithms for Conflict-Free Vehicle Routing....Pages 640-651
A $\frac{3}{2}$ Approximation for a Constrained Forest Problem....Pages 652-663
External-Memory Network Analysis Algorithms for Naturally Sparse Graphs....Pages 664-676
Approximate Counting of Cycles in Streams....Pages 677-688
Algorithms for Solving Rubik’s Cubes....Pages 689-700
Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds....Pages 701-712
Optimal Discovery Strategies in White Space Networks....Pages 713-722
Social-Aware Forwarding Improves Routing Performance in Pocket Switched Networks....Pages 723-735
Tolerant Algorithms....Pages 736-747
Alphabet-Independent Compressed Text Indexing....Pages 748-759
Distribution-Aware Compressed Full-Text Indexes....Pages 760-771
Smoothed Performance Guarantees for Local Search....Pages 772-783
Improved Approximations for k -Exchange Systems....Pages 784-798
Cover-Decomposition and Polychromatic Numbers....Pages 799-810
Back Matter....Pages -