Algorithms –- ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings (Lecture Notes in Computer Science, 7501)

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. 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 -