Algorithms - ESA 2009

This volume contains the papers presented at ESA 2009: The 17th Annual - ropean Symposium on Algorithms, September 79, 2009. ESA has been held annually since 1993, and seeks to cover both theoretical and engineering aspects of algorithms. The authors were asked to classify their paper under one or more categories as described in Fig. 1. Since 2001, ESA has been the core of the larger ALGO conference, which typically includes several satellite conferences. ALGO 2009 was held at the IT University of Copenhagen, Denmark. The ?ve members of the ALGO 2009 - ganizing Committee were chaired by Thore Husfeldt. The ESA submission deadline was April 12, Easter Sunday. This was clearly an error and we o?er profuse apologies for this mistake. Albeit no excuse, the hard constraints we faced were (a) ICALP noti?cation, April 6, and (b) ESA in Copenhagen, September 7. Between these two endpoints we needed to design a schedule that allowed modifying ICALP rejections for resubmission (1 week), Program Committee deliberations (7 weeks), preparing ?nal versions (4 weeks), and, to prepare, publish, and transport the proceedings (9 weeks). ESA 2009had 272submissions ofwhich 14 werewithdrawn overtime. Of the remaining 222 submissions to Track A (Design and Analysis), 56 were accepted. Of the remaining 36 submissions to Track B (Engineering and Applications), 10 were accepted. This gives an acceptance rate of slightly under 25%.

Klappentext

This book constitutes the refereed proceedings of the 17th Annual European Symposium on Algorithms, ESA 2009, held in Copenhagen, Denmark, in September 2009 in the context of the combined conference ALGO 2009.

The 67 revised full papers presented together with 3 invited lectures were carefully reviewed and selected: 56 papers out of 222 submissions for the design and analysis track and 10 out of 36 submissions in the engineering and applications track. The papers are organized in topical sections on trees, geometry, mathematical programming, algorithmic game theory, navigation and routing, graphs and point sets, bioinformatics, wireless communiations, flows, matrices, compression, scheduling, streaming, online algorithms, bluetooth and dial a ride, decomposition and covering, algorithm engineering, parameterized algorithms, data structures, and hashing and lowest common ancestor.

Inhalt
Invited Talk.- Some Open Questions Related to Cuckoo Hashing.- Trees.- Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks.- Improved Approximation Algorithms for Label Cover Problems.- A Linear Time Algorithm for L(2,1)-Labeling of Trees.- Geometry I.- On Inducing Polygons and Related Problems.- Computing 3D Periodic Triangulations.- Cauchy's Theorem for Orthogonal Polyhedra of Genus 0.- Mathematical Programming.- Approximability of Sparse Integer Programs.- Iterative Rounding for Multi-Objective Optimization Problems.- A Global-Optimization Algorithm for Mixed-Integer Nonlinear Programs Having Separable Non-convexity.- Geometry II.- Constructing Delaunay Triangulations along Space-Filling Curves.- Piercing Translates and Homothets of a Convex Body.- Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs.- Algorithmic Game Theory I.- On Revenue Maximization in Second-Price Ad Auctions.- Clustering-Based Bidding Languages for Sponsored Search.- Altruism in Atomic Congestion Games.- Geometry III.- Geometric Spanners for Weighted Point Sets.- k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees.- Narrow-Shallow-Low-Light Trees with and without Steiner Points.- Algorithmic Game Theory II.- Bounded Budget Betweenness Centrality Game for Strategic Network Formations.- Exact and Approximate Equilibria for Optimal Group Network Formation.- On the Performance of Approximate Equilibria in Congestion Games.- Navigation and Routing.- Optimality and Competitiveness of Exploring Polygons by Mobile Robots.- Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links.- Dynamic vs. Oblivious Routing in Network Design.- Invited Talk.- Algorithms Meet Art, Puzzles, andMagic.- Graphs and Point Sets.- Polynomial-Time Algorithm for the Leafage of Chordal Graphs.- Breaking the O(m 2 n) Barrier for Minimum Cycle Bases.- Shape Fitting on Point Sets with Probability Distributions.- Bioinformatics.- An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants (Extended Abstract).- Complete Parsimony Haplotype Inference Problem and Algorithms.- Linear-Time Recognition of Probe Interval Graphs.- Wireless Communications.- Wireless Scheduling with Power Control.- On the Power of Uniform Power: Capacity of Wireless Networks with Bounded Resources.- Approximability of OFDMA Scheduling.- Flows, Matrices, Compression.- Maximum Flow in Directed Planar Graphs with Vertex Capacities.- A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication.- On Optimally Partitioning a Text to Improve Its Compression.- Scheduling.- An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling.- Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling.- Preemptive Online Scheduling with Reordering.- Streaming.- d-Dimensional Knapsack in the Streaming Model.- Sparse Cut Projections in Graph Streams.- Bipartite Graph Matchings in the Semi-streaming Model.- Online Algorithms.- The Oil Searching Problem.- Hyperbolic Dovetailing.- Bluetooth and Dial a Ride.- On the Expansion and Diameter of Bluetooth-Like Topologies.- Minimum Makespan Multi-vehicle Dial-a-Ride.- Invited Talk.- Google's Auction for TV Ads.- Decomposition and Covering.- Inclusion/Exclusion Meets Measure and Conquer.- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution.- Counting Paths and Packings in Halves.- Algorithm Engineering.- Accelerating Multi-modal Route Planning by Access-Nodes.-Parallel Algorithms for Mean-Payoff Games: An Experimental Evaluation.- Experimental Study of FPT Algorithms for the Directed Feedback Vertex Set Problem.- Parameterized Algorithms I.- Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.- Kernel Bounds for Disjoint Cycles and Disjoint Paths.- Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem.- Data Structures.- Rank-Pairing Heaps.- 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit.- Hash, Displace, and Compress.- Parameterized Algorithms II.- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels.- Contraction Bidimensionality: The Accurate Picture.- Minimizing Movement: Fixed-Parameter Tractability.- Hashing and Lowest Common Ancestor.- Storing a Compressed Function with Constant Time Access.- Experimental Variations of a Theoretically Good Retrieval Data Structure.- Short Labels for Lowest Common Ancestors in Trees.- Best Paper Awards.- Disproof of the Neighborhood Conjecture with Implications to SAT.- Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard.