Algorithms – ESA 2007: 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007. Proceedings

Christos H. Papadimitriou (auth.), Lars Arge, Michael Hoffmann, Emo Welzl (eds.)3540755195, 9783540755197

This book constitutes the refereed proceedings of the 15th Annual European Symposium on Algorithms, ESA 2007, held in Eilat, Israel, in October 2007 in the context of the combined conference ALGO 2007.

The 63 revised full papers presented together with abstracts of three invited lectures were carefully reviewed and selected: 50 papers out of 165 submissions for the design and analysis track and 13 out of 44 submissions in the engineering and applications track. The papers address all current subjects in algorithmics reaching from design and analysis issues of algorithms over to real-world applications and engineering of algorithms in various fields.

---

Table of contents :
Front Matter….Pages –
Nash Equilibria: Where We Stand….Pages 1-1
Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation….Pages 2-11
Arrangements in Geometry: Recent Advances and Challenges….Pages 12-16
Nash Equilibria in Voronoi Games on Graphs….Pages 17-28
Evolutionary Equilibrium in Bayesian Routing Games: Specialization and Niche Formation….Pages 29-40
Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks….Pages 41-52
Finding Frequent Elements in Non-bursty Streams….Pages 53-62
Tradeoffs and Average-Case Equilibria in Selfish Routing….Pages 63-74
On the Variance of Subset Sum Estimation….Pages 75-86
On Minimum Power Connectivity Problems….Pages 87-98
On the Cost of Interchange Rearrangement in Strings….Pages 99-110
Finding Mobile Data: Efficiency vs. Location Inaccuracy….Pages 111-122
A Faster Query Algorithm for the Text Fingerprinting Problem….Pages 123-135
Polynomial Time Algorithms for Minimum Energy Scheduling….Pages 136-150
k -Mismatch with Don’t Cares….Pages 151-162
Finding Branch-Decompositions and Rank-Decompositions….Pages 163-174
Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover….Pages 175-186
Linear-Time Ranking of Permutations….Pages 187-193
Radix Sorting with No Extra Space….Pages 194-205
Fast Low Degree Connectivity of Ad-Hoc Networks Via Percolation….Pages 206-217
Order Statistics in the Farey Sequences in Sublinear Time….Pages 218-229
New Results on Minimax Regret Single Facility Ordered Median Location Problems on Networks….Pages 230-240
Dial a Ride from k -Forest….Pages 241-252
Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue….Pages 253-264
Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication….Pages 265-274
Optimal Algorithms for k -Search with Application in Option Pricing….Pages 275-286
Linear Data Structures for Fast Ray-Shooting Amidst Convex Polyhedra….Pages 287-298
Stackelberg Strategies for Atomic Congestion Games….Pages 299-310
Good Quality Virtual Realization of Unit Ball Graphs….Pages 311-322
Algorithms for Playing Games with Limited Randomness….Pages 323-334
Approximation of Partial Capacitated Vertex Cover….Pages 335-346
Optimal Resilient Dynamic Dictionaries….Pages 347-358
Determining the Smallest k Such That G Is k -Outerplanar….Pages 359-370
On the Size of Succinct Indices….Pages 371-382
Compact Oracles for Approximate Distances Around Obstacles in the Plane….Pages 383-394
Convex Combinations of Single Source Unsplittable Flows….Pages 395-406
Farthest-Polygon Voronoi Diagrams….Pages 407-418
Equitable Revisited….Pages 419-426
Online Scheduling of Equal-Length Jobs on Parallel Machines….Pages 427-438
k -Anonymization with Minimal Loss of Information….Pages 439-450
A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs….Pages 451-462
Improved Upper Bounds on the Competitive Ratio for Online Realtime Scheduling….Pages 463-474
Bundle Pricing with Comparable Items….Pages 475-486
Approximating Interval Scheduling Problems with Bounded Profits….Pages 487-497
Pricing Tree Access Networks with Connected Backbones….Pages 498-509
Distance Coloring….Pages 510-521
An O (log 2 k )-Competitive Algorithm for Metric Bipartite Matching….Pages 522-533
To Fill or Not to Fill: The Gas Station Problem….Pages 534-545
Online Bandwidth Allocation….Pages 546-557
Two’s Company, Three’s a Crowd: Stable Family and Threesome Roommates Problems….Pages 558-569
On the Complexity of Sequential Rectangle Placement in IEEE 802.16/WiMAX Systems….Pages 570-581
Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs….Pages 582-593
Dynamic Plane Transitive Closure….Pages 594-604
Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments….Pages 605-617
Estimating Clustering Indexes in Data Streams….Pages 618-632
Complete, Exact and Efficient Implementation for Computing the Adjacency Graph of an Arrangement of Quadrics….Pages 633-644
Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces: A First Step….Pages 645-656
Fast and Compact Oracles for Approximate Distances in Planar Graphs….Pages 657-668
Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra in Convex Pieces….Pages 669-680
A New ILP Formulation for 2-Root-Connected Prize-Collecting Steiner Networks….Pages 681-692
Algorithms to Separate ${{0,frac{1}{2}}}$ -Chvátal-Gomory Cuts….Pages 693-704
Fast Lowest Common Ancestor Computations in Dags….Pages 705-716
A Practical Efficient Fptas for the 0-1 Multi-objective Knapsack Problem….Pages 717-728
Solutions to Real-World Instances of PSPACE-Complete Stacking….Pages 729-740
Non-clairvoyant Batch Sets Scheduling: Fairness Is Fair Enough….Pages 741-753
An Experimental Study of New and Known Online Packet Buffering Algorithms….Pages 754-765
Back Matter….Pages –