ALGO 2009‎ > ‎[Untitled]‎ > ‎

Programme (preliminary)

All conferences have now selected their contributions and arranged them into sessions. The precise timings of coffee breaks are not quite fixed, but what fixtures we can provide — lunches and invited talks — should give some indication of when which talk will be given.

Monday 7 September

8.00 Registration and welcome.

9.00 ESA Session 1. Invited talk

  • Michael Mitzenmacher, Some Open Questions Related to Cuckoo Hashing

ESA Session 2a

  • Martin Fürer. Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks.
  • Moses Charikar, Mohammad Taghi Hajiaghayi, and Howard Karloff. Improved Approximation Algorithms for Label Cover Problems.
  • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono and Yushi Uno. A linear time algorithm for L(2, 1)-labeling of trees.

ESA Session 2b

  • Eyal Ackerman, Rom Pinchasi, Ludmila Scharf and Marc Scherfenberg. On Inducing Polygons and Related Problems.
  • Manuel Caroli and Monique Teillaud. Computing 3D Periodic Triangulations.
  • Therese Biedl and Burkay Genc. Cauchy’s theorem for orthogonal polyhedra of genus 0.

ESA Session 3a

  • David Pritchard. Approximability of Sparse Integer Programs.
  • Fabrizio Grandoni, Ravi R. and Mohit Singh. Iterative Rounding for Multi-Objective Optimization Problems.
  • Claudia D’Ambrosio, Jon Lee and Andreas Wächter. A global-optimization algorithm for mixed-integer nonlinear programs having separable non-convexity.

ESA Session 3b

  • Kevin Buchin. Constructing Delaunay Triangulations along Space-Filling Curves.
  • Adrian Dumitrescu and Minghui Jiang. Piercing translates and homothets of a convex body.
  • Khaled Elbassioni, Kazuhisa Makino and Imran Rauf. Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs.


ESA Session 4a

  • Yossi Azar, Benjamin Birnbaum, Anna Karlin and Thach Nguyen. On Revenue Maximization in Second-Price Ad Auctions.
  • Mohammad Mahdian and Grant Wang. Clustering-Based Bidding Languages for Sponsored Search.
  • Martin Hoefer and Alexander Skopalik. Altruism in Atomic Congestion Games.

ESA Session 4b

  • Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson and Michiel Smid. Geometric Spanners for Weighted Point Sets.
  • Yuval Emek. k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees.
  • Michael Elkin and Shay Solomon. Narrow-Shallow-Low-Light Trees with and without Steiner Points

ESA Session 5a

  • Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang and Jiajie Zhu. Bounded Budget Betweenness Centrality Game for Strategic Network Formations.
  • Elliot Anshelevich and Bugra Caskurlu. Exact and Approximate Equilibria for Optimal Group Network Formation.
  • George Christodoulou, Elias Koutsoupias and Paul Spirakis. On the performance of approximate equilibria in congestion games.

ESA Session 5b

  • Jurek Czyzowicz, Arnaud Labourel and Andrzej Pelc. Optimality and Competitiveness of Exploring Polygons by Mobile Robots.
  • Rafael Hassin, R Ravi and Fatma Sibel Salman. Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links.
  • Navin Goyal, Neil Olver and Bruce Shepherd. Dynamic vs Oblivious Routing in Network Design.

ESA/ALGO Business Meeting

Scroll Bar is open

Tuesday 8 September

9.00 ESA Session 6. Invited talk.

  • Eric Demaine. Algorithms Meet Art, Puzzles, and Magic

ESA Session 7a

  • Juraj Stacho and Michel Habib. Polynomial-time algorithm for the leafage of chordal graphs.
  • Edoardo Amaldi, Claudio Iuliano, Tomasz Jurkiewicz, Kurt Mehlhorn and Romeo Rizzi. Breaking the O(m2 n) Barrier for Minimum Cycle Basis.
  • Maarten Löffler and Jeff Phillips . Shape Fitting on Point Sets with Probability Distributions.

ESA Session 7b

  • Jing Xiao, Tiancheng Lou and Tao Jiang. An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants.
  • Gerold Jaeger, Sharlee Climer and Weixiong Zhang. Complete Parsimony Haplotype Inference Problem and Algorithms
  • Ross McConnell and Yahav Nussbaum. Linear-time recognition of probe interval graphs.

ESA Session 8a

  • Magnus M. Halldorsson. Wireless scheduling with power control.
  • Chen Avin, Zvi Lotker and Yvonne Anne Pignolet. On the Power of Uniform Power: Capacity of Wireless Networks with Bounded Resources
  • Marcel Ochel and Berthold Vöcking. Approximability of OFDMA Scheduling

ESA Session 8b

  • Haim Kaplan and Yahav Nussbaum. Maximum Flow in Directed Planar Graphs with Vertex Capacities.
  • Andrzej Lingas. A fast output-sensitive algorithm for Boolean matrix multiplication.
  • Paolo Ferragina, Igor Nitto and Rossano Venturini. On optimally partitioning a text to improve its compression.


ESA Session 9a

  • Andreas Karrenbauer and Thomas Rothvoss. An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling.
  • Chandra Chekuri, Sungjin Im and Benjamin Moseley. Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling.
  • Gyorgy Dosa and Leah Epstein. Preemptive online scheduling with reordering

ESA Session 9b

  • Sumit Ganguly and Christian Sohler. d-dimensional Knapsack in the Streaming Model.
  • Atish Das Sarma, Sreenivas Gollapudi and Rina Panigrahy. Sparse Cut Projections in Graph Streams.
  • Sebastian Eggert, Lasse Kliemann and Anand Srivastav. Bipartite Graph Matchings in the Semi-Streaming Model.

ESA Session 10a

  • Andrew McGregor, Krzysztof Onak and Rina Panigrahy. The Oil Searching Problem.
  • David Kirkpatrick. Hyperbolic dovetailing.

ESA Session 10b

  • Alberto Pettarin, Andrea Pietracaprina and Geppino Pucci. On the Expansion and Diameter of Bluetooth-like Topologies.
  • Inge Li Gørtz, Viswanath Nagarajan and R. Ravi. Minimum Makespan Multi-vehicle Dial-a-Ride.

Conference dinner

Wednesday 9 September

9.00 Session 11. Invited talk

  • Noam Nisan. Google’s Auction for TV Ads.

ESA Session 12a

  • Johan M. M. van Rooij, Jesper Nederlof and Thomas C. van Dijk. Inclusion/Exclusion Meets Measure and Conquer: Exact algorithms for counting dominating sets.
  • Johan M. M. van Rooij, Hans L. Bodlaender and Peter Rossmanith. Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution.
  • Andreas Bjorklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto. Counting Paths and Packings in Halves.

ESA Session 12b

  • Daniel Delling, Thomas Pajor and Dorothea Wagner. Accelerating Multi-Modal Route Planning by Access-Nodes.
  • Jakub Chaloupka. Parallel Algorithms for Mean-Payoff Games: An Experimental Evaluation.
  • Rudolf Fleischer, Xi Wu and Liwei Yuan. Experimental study of FPT algorithms for the directed feedback vertex set problem.

ESA Session 13a

  • Markus Blaeser and Christian Hoffmann. Fast Computation of Interlace Polynomials on Graphs of Bounded Treewidth.
  • Hans L. Bodlaender, Stephan Thomasse and Anders Yeo. Kernel Bounds for Disjoint Cycles and Disjoint Paths.
  • Dániel Marx and Igor Razgon. Constant ratio fixed-parameter approximation of the edge multicut problem.

ESA Session 13b

  • Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan. Rank-Pairing Heaps.
  • Rina Panigrahy and Eric Lehman. 3.5-Way Cuckoo Hashing for the Price of 2.
  • Djamal Belazzougui, Fabiano Botelho and Martin Dietzfelbinger. Hash, displace, and compress.


ESA Session 14a

  • Geevarghese Philip, Venkatesh Raman and Somnath Sikdar. Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels.
  • Fedor Fomin, Petr Golovach and Dimitrios Thilikos. Contraction Bidimensionality: the accurate picture.
  • Erik D. Demaine, Mohammad Taghi Hajiaghayi and Dániel Marx. Minimizing Movement: Fixed-Parameter Tractability.

ESA Session 14b

  • Johannes B Hreinsson, Morten Krøyer and Rasmus Pagh. Storing a Compressed Function with Constant Time Access.
  • Martin Aumüller, Martin Dietzfelbinger and Michael Rink. Experimental variations of a theoretically good retrieval data structure.
  • Johannes Fischer. Short Labels for Lowest Common Ancestors in Trees.

ESA Session 15. Best paper awards

  • Best student paper: Heidi Gebauer. Disproof of the Neighborhood Conjecture with Implications to SAT.
  • Best paper: Christoph Dürr, Flavio Guiñez and Martín Matamala. Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard.

Bicycle trip through Copenhagen.

Reception at Copenhagen City Hall

Thursday 10 September

9.00 Invited talk

  • Vijay Vazirani. Combinatorial Algorithms for Convex Programs Capturing Market Equilibria and Nash Bargaining Solutions

IWPEC Session 1

  • R. Ganian, P. Hlineny, J. Kneis, A. Langer, J. Obdržálek, and P. Rossmanith. On Digraph Width Measures in Parameterized Algorithmics
  • M. Fellows, D. Hermelin, and F. A. Rosamond. Well-Quasi-Ordering Bounded Treewidth Graphs
  • S. Gutner. Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor

ATMOS Session 1

  • Martin Aronsson, Markus Bohlin and Per Kreuger. MILP formulations of cumulative constraints for railway scheduling - A comparative study
  • Peter Marton, Jens Maue and Marc Nunkesser. An Improved Train Classification Procedure for the Hump Yard Lausanne Triage
  • Twan Dollevoet, Dennis Huisman, Marie Schmidt and Anita Schoebel. Delay Management with Re-Routing of Passengers

WAOA Session 1

  • Xin Han and Kazuhisa Makino. Online Minimization Knapsack Problem
  • Christoph Dürr, Lukasz Jez. and Kim Thang Nguyen. Online Scheduling of Bounded Length Jobs to Maximize Throughput
  • Prudence W.H. Wong and Fencol C.C. Yung. Competitive Multi-Dimensional Dynamic Bin Packing via L-Shape Bin Packing

IWPEC Session 2

  • M. Koivisto. Partitioning into Sets of Bounded Cardinality
  • D. Lokshtanov and S. Saurabh. Even Faster Algorithm for Set Splitting!
  • R. Enciso, M. Fellows, J. Guo, I. Kanj, F. Rosamond, and O. Suchý. What Makes Equitable Connected Partition Easy

ATMOS Session 2

  • Joondong Kim, Alexander Kroeller, Joseph Mitchell and Girishkumar Sabhnani. Scheduling Aircraft to Reduce Controller Workload
  • Daniel Delling, Thomas Pajor, Dorothea Wagner and Christos Zaroliagis. Efficient Route Planning in Flight Networks
  • Apostolos Bessas and Christos Zaroliagis. On Assessing Robustness in Transportation Planning

WAOA Session 2

  • Elisabeth Günther, Felix König and Nicole Megow. Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width
  • Chandra Chekuri, Sungjin Im and Benjamin Moseley. Longest Wait First for Broadcast Scheduling
  • Klaus Jansen and Christina Otte. Approximation Algorithms for Multiple Strip Packing

13.00–14.00 Lunch

Invited talk

  • Dorothea Wagner. Algorithm Engineering for Route Planning in Realistic Scenarios

IWPEC Session 3

  • D. Raible, H. Fernau, J. Kneis, D. Kratsch, A. Langer, P. Rossmanith, and M. Liedloff. An exact algorithm for the Maximum Leaf Spanning Tree problem
  • J. Daligault and S. Thomasse. On finding directed trees with many leaves
  • S. Sikdar, D. Lokshtanov, V. Raman, and S. Saurabh. On the Directed Degree-Preserving Spanning Tree Problem

ATMOS Session 3

  • Olaf Beyersdorff and Yevgen Nebesov. Edges as Nodes - a New Approach to Timetable Information
  • Annabell Berger, Daniel Delling, Andreas Gebhardt and Matthias Müller-Hannemann. Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected
  • Emanuele Berrettini, Gianlorenzo D'Angelo and Daniel Delling. Arc-Flags in Dynamic Graphs

WAOA Session 3

  • Hadas Shachnai, gal tamir and Tami Tamir. Minimal Cost Reconfiguration of Data Placement in Storage Area Network
  • Dries Goossens, Sergey Polyakovskiy, Frits Spieksma and Gerhard Woeginger. Between a rock and a hard place: The two-to-one assignment problem
  • Danny Hermelin and Dror Rawitz. Optimization Problems in Multiple Subtree Graphs

IWPEC Session 4

  • J. A. Telle, B.-M. Bui-Xuan and M. Vatshelle. Boolean-width of graphs
  • P. Golovach and D. Thilikos. Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms
  • P. Damaschke. Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms
  • L. Kowalik, T. Walen, M. Krnc, and R. Erma. Improved induced matchings in sparse graphs

WAOA Session 4

  • Reuven Bar-Yehuda, Danny Hermelin and Dror Rawitz. An Extension of the Nemhauser&Trotter Theorem to Generalized Vertex Cover with Applications
  • Spyros Angelopoulos. On the Competitiveness of the Online Asymmetric and Euclidean Steiner Tree Problems
  • Atish Das Sarma, Amit Deshpande and Ravi Kannan. Finding Dense Subgraphs in G(n,1/2)
  • Thomas Erlebach and Matus Mihalak. A (4+e)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs

Friday 11 September

9.00 Invited talk

  • Hans Bodlaender. Kernelization: new upper and lower bound techniques

IWPEC Session 5

  • K. Suchan and Y. Villanger. Computing pathwidth faster than 2n
  • C. Calabro, R. Impagliazzo, and R. Paturi. The complexity of satisfiability of small depth circuits
  • M. Furer, S. Gaspers, and S. Kasiviswanathan. An Exponential Time 2-Approximation Algorithm for Bandwidth

WAOA Session 5

  • Bodo Manthey. Multi-Criteria TSP: Min and Max Combined
  • Yuval Emek, Pierre Fraigniaud, Amos Korman and Adi Rosen. On the Additive Constant of the k-Server Work Function Algorithm
  • Ilya Chernykh, Nikita Dryuck, Alexander Kononov and Sergey Sevastianov. The Routing Open Shop Problem: New Approximation Algorithms

IWPEC Session 6

  • H. L. Bodlaender, D. Lokshtanov, and E. Penninkx. Planar Capacitated Dominating Set is W[1]-hard
  • S. Kratsch and M. Wahlström. Two Edge Modification Problems Without Polynomial Kernels
  • P. Giannopoulos, C. Knauer, and G. Rote. The parameterized complexity of some geometric problems in unbounded dimensions

WAOA Session 6

  • Britta Peis, Martin Skutella and Andreas Wiese. Packet Routing: Complexity and Algorithms
  • Christine Chung, George Christodoulou, Katrina Ligett, Evangelia Pyrga and Rob van Stee. On the Price of Stability for Undirected Network Design
  • Fedor Fomin, Petr Golovach and Daniel Lokshtanov. Guard games on graphs: keep the intruder out!
13:00-14:00 lunch

13.00–14.00: Lunch

Invited talk

  • Noga Alon. Color Coding, Balanced Hashing and Approximate Counting

IWPEC Session 7

  • G. Gutin, E. J. Kim, S. Szeider, and A. Yeo. Probabilistic Approach to Problems Parameterized Above Tight Lower Bound
  • P. Damaschke. Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover
  • D. Marx and I. Schlotter. Stable Assignment with Couples: Parameterized Complexity and Local Search

WAOA Session 7

  • Reza Dorrigiv, Martin R. Ehmsen and Alejandro Lopez-Ortiz. Parameterized Analysis of Paging and List Update Algorithms
  • Marcin Bienkowski. Price Fluctuations: To Buy or to Rent
  • Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee and Hing-Fung Ting. Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window

IWPEC Session 8

  • N. Simjour. Improved Parameterized Algorithms for the Kemeny Aggregation Problem
  • G. Gutin, D. Karapetyan, and I. Razgon. FPT Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs
  • S. Böcker, F. Hüffner, A. Truss, and M. Wahlström. A faster fixed-parameter approach to drawing binary tanglegrams