Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings

Front Matter....Pages -
On Big Data Algorithmics....Pages 1-1
Open Problems in Throughput Scheduling....Pages 2-11
Preemptive Coordination Mechanisms for Unrelated Machines....Pages 12-23
Hierarchical Hub Labelings for Shortest Paths....Pages 24-35
Bottleneck Non-crossing Matching in the Plane....Pages 36-47
Lower Bounds for Sorted Geometric Queries in the I/O Model....Pages 48-59
Constructing Street Networks from GPS Trajectories....Pages 60-71
I/O-efficient Hierarchical Diameter Approximation....Pages 72-83
On the Value of Job Migration in Online Makespan Minimization....Pages 84-95
Simplifying Massive Contour Maps....Pages 96-107
Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash....Pages 108-120
On Online Labeling with Polynomially Many Labels....Pages 121-132
A 5-Approximation for Capacitated Facility Location....Pages 133-144
Weighted Geometric Set Multi-cover via Quasi-uniform Sampling....Pages 145-156
A Bicriteria Approximation for the Reordering Buffer Problem....Pages 157-168
Time-Dependent Route Planning with Generalized Objective Functions....Pages 169-180
New Lower and Upper Bounds for Representing Sequences....Pages 181-192
Span Programs and Quantum Algorithms for st -Connectivity and Claw Detection....Pages 193-204
The Stretch Factor of L 1 - and L  ∞  -Delaunay Triangulations....Pages 205-216
Two Dimensional Range Minimum Queries and Fibonacci Lattices....Pages 217-228
Locally Correct Fréchet Matchings....Pages 229-240
The Clique Problem in Ray Intersection Graphs....Pages 241-252
Revenue Guarantees in Sponsored Search Auctions....Pages 253-264
Optimizing Social Welfare for Network Bargaining Games in the Face of Unstability, Greed and Spite....Pages 265-276
Optimal Lower Bound for Differentially Private Multi-party Aggregation....Pages 277-288
A Model for Minimizing Active Processor Time....Pages 289-300
Polynomial-Time Algorithms for Energy Games with Special Weight Structures....Pages 301-312
Data Structures on Event Graphs....Pages 313-324
Improved Distance Oracles and Spanners for Vertex-Labeled Graphs....Pages 325-336
The Quantum Query Complexity of Read-Many Formulas....Pages 337-348
A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees....Pages 349-360
Steiner Forest Orientation Problems....Pages 361-372
A Dual-Fitting $\\frac{3}{2}$ -Approximation Algorithm for Some Minimum-Cost Graph Problems....Pages 373-382
Kinetic Compressed Quadtrees in the Black-Box Model with Applications to Collision Detection for Low-Density Scenes....Pages 383-394
Finding Social Optima in Congestion Games with Positive Externalities....Pages 395-406
Better Bounds for Graph Bisection....Pages 407-418
On the Complexity of Metric Dimension....Pages 419-430
Embedding Paths into Trees: VM Placement to Minimize Congestion....Pages 431-442
Faster Geometric Algorithms via Dynamic Determinant Computation....Pages 443-454
Lines through Segments in 3D Space....Pages 455-466
A Polynomial Kernel for Proper Interval Vertex Deletion ....Pages 467-478
Knowledge, Level of Symmetry, and Time of Leader Election....Pages 479-490
An Experimental Study of Dynamic Dominators....Pages 491-502
Optimizing over the Growing Spectrahedron....Pages 503-514
Induced Disjoint Paths in Claw-Free Graphs....Pages 515-526
On Min-Power Steiner Tree....Pages 527-538
Maximum Multicommodity Flows over Time without Intermediate Storage....Pages 539-550
Approximating Earliest Arrival Flows in Arbitrary Networks....Pages 551-562
Resource Buying Games....Pages 563-574
Succinct Data Structures for Path Queries....Pages 575-586
Approximation of Minimum Cost Homomorphisms....Pages 587-598
Property Testing in Sparse Directed Graphs: Strong Connectivity and Subgraph-Freeness....Pages 599-610
Improved Implementation of Point Location in General Two-Dimensional Subdivisions....Pages 611-623
Parameterized Complexity of Induced H -Matching on Claw-Free Graphs....Pages 624-635
Solving Simple Stochastic Games with Few Coin Toss Positions....Pages 636-647
Efficient Communication Protocols for Deciding Edit Distance....Pages 648-658
Approximation Algorithms for Wireless Link Scheduling with Flexible Data Rates....Pages 659-670
Extending Partial Representations of Function Graphs and Permutation Graphs....Pages 671-682
A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization....Pages 683-694
Minimum Average Distance Triangulations....Pages 695-706
Colouring AT-Free Graphs....Pages 707-718
Routing Regardless of Network Stability....Pages 719-730
The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes....Pages 731-742
Succinct Posets....Pages 743-754
Polynomial-Time Approximation Schemes for Shortest Path with Alternatives....Pages 755-765
On Computing Straight Skeletons by Means of Kinetic Triangulations....Pages 766-777
A Self-adjusting Data Structure for Multidimensional Point Sets....Pages 778-789
TSP Tours in Cubic Graphs: Beyond 4/3....Pages 790-801
FPT Algorithms for Domination in Biclique-Free Graphs....Pages 802-812
Maximum Flow Networks for Stability Analysis of LEGO ® Structures....Pages 813-824
Average Case Analysis of Java 7’s Dual Pivot Quicksort....Pages 825-836
Back Matter....Pages -