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

This book constitutes the refereed proceedings of the 20th Annual European Symposium on Algorithms, ESA 2012, held in Ljubljana, Slovenia, in September 2012 in the context of the combined conference ALGO 2012. The 69 revised full papers presented were carefully reviewed and selected from 285 initial submissions: 56 out of 231 in track design and analysis and 13 out of 54 in track engineering and applications. The papers are organized in topical sections such as algorithm engineering; algorithmic aspects of networks; algorithmic game theory; approximation algorithms; computational biology; computational finance; computational geometry; combinatorial optimization; data compression; data structures; databases and information retrieval; distributed and parallel computing; graph algorithms; hierarchical memories; heuristics and meta-heuristics; mathematical programming; mobile computing; on-line algorithms; parameterized complexity; pattern matching, quantum computing; randomized algorithms; scheduling and resource allocation problems; streaming algorithms.

---

This book constitutes the refereed proceedings of the 20th Annual European Symposium on Algorithms, ESA 2012, held in Ljubljana, Slovenia, in September 2012 in the context of the combined conference ALGO 2012. The 69 revised full papers presented were carefully reviewed and selected from 285 initial submissions: 56 out of 231 in track design and analysis and 13 out of 54 in track engineering and applications. The papers are organized in topical sections such as algorithm engineering; algorithmic aspects of networks; algorithmic game theory; approximation algorithms; computational biology; computational finance; computational geometry; combinatorial optimization; data compression; data structures; databases and information retrieval; distributed and parallel computing; graph algorithms; hierarchical memories; heuristics and meta-heuristics; mathematical programming; mobile computing; on-line algorithms; parameterized complexity; pattern matching, quantum computing; randomized algorithms; scheduling and resource allocation problems; streaming algorithms.

---

This book constitutes the refereed proceedings of the 20th Annual European Symposium on Algorithms, ESA 2012, held in Ljubljana, Slovenia, in September 2012 in the context of the combined conference ALGO 2012. The 69 revised full papers presented were carefully reviewed and selected from 285 initial submissions: 56 out of 231 in track design and analysis and 13 out of 54 in track engineering and applications. The papers are organized in topical sections such as algorithm engineering; algorithmic aspects of networks; algorithmic game theory; approximation algorithms; computational biology; computational finance; computational geometry; combinatorial optimization; data compression; data structures; databases and information retrieval; distributed and parallel computing; graph algorithms; hierarchical memories; heuristics and meta-heuristics; mathematical programming; mobile computing; on-line algorithms; parameterized complexity; pattern matching, quantum computing; randomized algorithms; scheduling and resource allocation problems; streaming algorithms.
Content:
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
Two Dimensional Range Minimum Queries and Fibonacci Lattices....Pages 205-216
Locally Correct Fr?chet Matchings....Pages 217-228
The Clique Problem in Ray Intersection Graphs....Pages 229-240
Revenue Guarantees in Sponsored Search Auctions....Pages 241-252
Optimizing Social Welfare for Network Bargaining Games in the Face of Unstability, Greed and Spite....Pages 253-264
Optimal Lower Bound for Differentially Private Multi-party Aggregation....Pages 265-276
A Model for Minimizing Active Processor Time....Pages 277-288
Polynomial-Time Algorithms for Energy Games with Special Weight Structures....Pages 289-300
Data Structures on Event Graphs....Pages 301-312
Improved Distance Oracles and Spanners for Vertex-Labeled Graphs....Pages 313-324
The Quantum Query Complexity of Read-Many Formulas....Pages 325-336
A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees....Pages 337-348
Steiner Forest Orientation Problems....Pages 349-360
Kinetic Compressed Quadtrees in the Black-Box Model with Applications to Collision Detection for Low-Density Scenes....Pages 361-372
Finding Social Optima in Congestion Games with Positive Externalities....Pages 373-382
Better Bounds for Graph Bisection....Pages 383-394
On the Complexity of Metric Dimension....Pages 395-406
Embedding Paths into Trees: VM Placement to Minimize Congestion....Pages 407-418
Faster Geometric Algorithms via Dynamic Determinant Computation....Pages 419-430
Lines through Segments in 3D Space....Pages 431-442
Knowledge, Level of Symmetry, and Time of Leader Election....Pages 443-454
An Experimental Study of Dynamic Dominators....Pages 455-466
Optimizing over the Growing Spectrahedron....Pages 467-478
Induced Disjoint Paths in Claw-Free Graphs....Pages 479-490
On Min-Power Steiner Tree....Pages 491-502
Maximum Multicommodity Flows over Time without Intermediate Storage....Pages 503-514
Approximating Earliest Arrival Flows in Arbitrary Networks....Pages 515-526
Resource Buying Games....Pages 527-538
Succinct Data Structures for Path Queries....Pages 539-550
Approximation of Minimum Cost Homomorphisms....Pages 551-562
Property Testing in Sparse Directed Graphs: Strong Connectivity and Subgraph-Freeness....Pages 563-574
Improved Implementation of Point Location in General Two-Dimensional Subdivisions....Pages 575-586
Parameterized Complexity of Induced H-Matching on Claw-Free Graphs....Pages 587-598
Solving Simple Stochastic Games with Few Coin Toss Positions....Pages 599-610
Efficient Communication Protocols for Deciding Edit Distance....Pages 611-623
Approximation Algorithms for Wireless Link Scheduling with Flexible Data Rates....Pages 624-635
Extending Partial Representations of Function Graphs and Permutation Graphs....Pages 636-647
A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization....Pages 648-658
Minimum Average Distance Triangulations....Pages 659-670
Colouring AT-Free Graphs....Pages 671-682
Routing Regardless of Network Stability....Pages 683-694
The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes....Pages 695-706
Succinct Posets....Pages 707-718
Polynomial-Time Approximation Schemes for Shortest Path with Alternatives....Pages 719-730
On Computing Straight Skeletons by Means of Kinetic Triangulations....Pages 731-742
A Self-adjusting Data Structure for Multidimensional Point Sets....Pages 743-754
TSP Tours in Cubic Graphs: Beyond 4/3....Pages 755-765
FPT Algorithms for Domination in Biclique-Free Graphs....Pages 766-777
Maximum Flow Networks for Stability Analysis of LEGO®Structures....Pages 778-789
Average Case Analysis of Java 7’s Dual Pivot Quicksort....Pages 790-801
Back Matter....Pages 802-812
....Pages 813-824