Algorithms - ESA 2007

Invited Lectures.- Nash Equilibria: Where We Stand.- Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation.- Arrangements in Geometry: Recent Advances and Challenges.- Contributed Papers: Design and Analysis Track.- Nash Equilibria in Voronoi Games on Graphs.- Evolutionary Equilibrium in Bayesian Routing Games: Specialization and Niche Formation.- Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks.- Finding Frequent Elements in Non-bursty Streams.- Tradeoffs and Average-Case Equilibria in Selfish Routing.- On the Variance of Subset Sum Estimation.- On Minimum Power Connectivity Problems.- On the Cost of Interchange Rearrangement in Strings.- Finding Mobile Data: Efficiency vs. Location Inaccuracy.- A Faster Query Algorithm for the Text Fingerprinting Problem.- Polynomial Time Algorithms for Minimum Energy Scheduling.- k-Mismatch with Don't Cares.- Finding Branch-Decompositions and Rank-Decompositions.- Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover.- Linear-Time Ranking of Permutations.- Radix Sorting with No Extra Space.- Fast Low Degree Connectivity of Ad-Hoc Networks Via Percolation.- Order Statistics in the Farey Sequences in Sublinear Time.- New Results on Minimax Regret Single Facility Ordered Median Location Problems on Networks.- Dial a Ride from k-Forest.- Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue.- Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication.- Optimal Algorithms for k-Search with Application in Option Pricing.- Linear Data Structures for Fast Ray-Shooting Amidst Convex Polyhedra.- Stackelberg Strategies for Atomic Congestion Games.- Good Quality VirtualRealization of Unit Ball Graphs.- Algorithms for Playing Games with Limited Randomness.- Approximation of Partial Capacitated Vertex Cover.- Optimal Resilient Dynamic Dictionaries.- Determining the Smallest k Such That G Is k-Outerplanar.- On the Size of Succinct Indices.- Compact Oracles for Approximate Distances Around Obstacles in the Plane.- Convex Combinations of Single Source Unsplittable Flows.- Farthest-Polygon Voronoi Diagrams.- Equitable Revisited.- Online Scheduling of Equal-Length Jobs on Parallel Machines.- k-Anonymization with Minimal Loss of Information.- A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs.- Improved Upper Bounds on the Competitive Ratio for Online Realtime Scheduling.- Bundle Pricing with Comparable Items.- Approximating Interval Scheduling Problems with Bounded Profits.- Pricing Tree Access Networks with Connected Backbones.- Distance Coloring.- An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching.- To Fill or Not to Fill: The Gas Station Problem.- Online Bandwidth Allocation.- Two's Company, Three's a Crowd: Stable Family and Threesome Roommates Problems.- On the Complexity of Sequential Rectangle Placement in IEEE 802.16/WiMAX Systems.- Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs.- Dynamic Plane Transitive Closure.- Contributed Papers: Engineering and Applications Track.- Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments.- Estimating Clustering Indexes in Data Streams.- Complete, Exact and Efficient Implementation for Computing the Adjacency Graph of an Arrangement of Quadrics.- Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces: A First Step.- Fast and Compact Oracles for Approximate Distances in Planar Graphs.- Exact Minkowksi Sumsof Polyhedra and Exact and Efficient Decomposition of Polyhedra in Convex Pieces.- A New ILP Formulation for 2-Root-Connected Prize-Collecting Steiner Networks.- Algorithms to Separate -Chvátal-Gomory Cuts.- Fast Lowest Common Ancestor Computations in Dags.- A Practical Efficient Fptas for the 0-1 Multi-objective Knapsack Problem.- Solutions to Real-World Instances of PSPACE-Complete Stacking.- Non-clairvoyant Batch Sets Scheduling: Fairness Is Fair Enough.- An Experimental Study of New and Known Online Packet Buffering Algorithms.