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.

Lunch

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(m₂ 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.

Lunch

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.

Lunch

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 2ⁿ
• 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