Algorithms - ESA 2010

Inhalt

Invited Talk.- The Robustness of Level Sets.- Session 1a.- Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods.- Non-clairvoyant Speed Scaling for Weighted Flow Time.- A Robust PTAS for Machine Covering and Packing.- Session 1b.- Balancing Degree, Diameter and Weight in Euclidean Spanners.- Testing Euclidean Spanners.- Fast Approximation in Subspaces by Doubling Metric Decomposition.- f-Sensitivity Distance Oracles and Routing Schemes.- Session 2a.- Fast Minor Testing in Planar Graphs.- On the Number of Spanning Trees a Planar Graph Can Have.- Contractions of Planar Graphs in Polynomial Time.- Session 2b.- Communication Complexity of Quasirandom Rumor Spreading.- A Complete Characterization of Group-Strategyproof Mechanisms of Cost-Sharing.- Contribution Games in Social Networks.- Session 3a.- Improved Bounds for Online Stochastic Matching.- Online Stochastic Packing Applied to Display Ad Allocation.- Caching Is Hard - Even in the Fault Model.- Session 3b.- Superselectors: Efficient Constructions and Applications.- Estimating the Average of a Lipschitz-Continuous Function from One Sample.- Streaming Graph Computations with a Helpful Advisor.- Session 4a.- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier.- Minimum Vertex Cover in Rectangle Graphs.- Feedback Vertex Sets in Tournaments.- Session 4b.- n-Level Graph Partitioning.- Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns.- Finding the Diameter in Real-World Graphs.- Session 5a.- Budgeted Red-Blue Median and Its Generalizations.- All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables.- Strong Formulations for the Multi-module PESP and a Quadratic Algorithm for Graphical Diophantine Equation Systems.- Robust Algorithms for Sorting Railway Cars.- Session 5b.- Cloning Voronoi Diagrams via Retroactive Data Structures.- A Unified Approach to Approximate Proximity Searching.- Spatio-temporal Range Searching over Compressed Kinetic Sensor Data.- Constructing the Exact Voronoi Diagram of Arbitrary Lines in Three-Dimensional Space.- Invited Talk.- Local Graph Exploration and Fast Property Testing.- Session 6a.- A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings.- Fast Prefix Search in Little Space, with Applications.- On the Huffman and Alphabetic Tree Problem with General Cost Functions.- Medium-Space Algorithms for Inverse BWT.- Session 6b.- Median Trajectories.- Optimal Cover of Points by Disks in a Simple Polygon.- Stability of ?-Kernels.- The Geodesic Diameter of Polygonal Domains.- Session 7a.- Polyhedral and Algorithmic Properties of Quantified Linear Programs.- Approximating Parameterized Convex Optimization Problems.- Approximation Schemes for Multi-Budgeted Independence Systems.- Session 7b.- Algorithmic Meta-theorems for Restrictions of Treewidth.- Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus.- Constructing the R* Consensus Tree of Two Trees in Subcubic Time.