Version of September 10, 17:10

Monday 7 September

8.00–8.40 Registration
8.40–9.00 Welcome (AUD1)
9.00‑9.50 Invited talk (AUD1, Chair: Rasmus Pagh)
Michael Mitzenmacher, Some Open Questions Related to Cuckoo Hashing
10.00‑11.15 ESA Session 2a
AUD1, Chair: Lars Arge
ESA Session 2b
Scroll Bar, Chair: Uli Wagner
10.00‑10.25 Martin Fürer. Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks. Eyal Ackerman, Rom Pinchasi, Ludmila Scharf and Marc Scherfenberg. On Inducing Polygons and Related Problems.
10.25‑10.50 Moses Charikar, Mohammad Taghi Hajiaghayi, and Howard Karloff. Improved Approximation Algorithms for Label Cover Problems. Manuel Caroli and Monique Teillaud. Computing 3D Periodic Triangulations.
10.50‑11.15 Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono and Yushi Uno. A linear time algorithm for L(2, 1)-labeling of trees. Therese Biedl and Burkay Genc. Cauchy’s theorem for orthogonal polyhedra of genus 0.
11.15‑11.40 Coffee
11.40‑12.55 ESA Session 3a
AUD1, Chair: Lars Arge
ESA Session 3b
Scroll Bar, Chair: Uli Wagner
11.40‑12.05 David Pritchard. Approximability of Sparse Integer Programs. Kevin Buchin. Constructing Delaunay Triangulations along Space-Filling Curves.
12.05‑12.30 Fabrizio Grandoni, Ravi R. and Mohit Singh. Iterative Rounding for Multi-Objective Optimization Problems. Adrian Dumitrescu and Minghui Jiang. Piercing translates and homothets of a convex body.
12.30‑12.55 Claudia D’Ambrosio, Jon Lee and Andreas Wächter. A global-optimization algorithm for mixed-integer nonlinear programs having separable non-convexity. Khaled Elbassioni, Kazuhisa Makino and Imran Rauf. Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs.
13.00‑14.00 Lunch
14.00‑15.15 ESA Session 4a
AUD1, Chair: Caragiannis Ioannis
ESA Session 4b
AUD2, Chair: Bengt Nilsson
14.00‑14.25 Yossi Azar, Benjamin Birnbaum, Anna Karlin and Thach Nguyen. On Revenue Maximization in Second-Price Ad Auctions. Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson and Michiel Smid. Geometric Spanners for Weighted Point Sets.
14.25‑14.50 Mohammad Mahdian and Grant Wang. Clustering-Based Bidding Languages for Sponsored Search. Yuval Emek. k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees.
14.50‑15.15 Martin Hoefer and Alexander Skopalik. Altruism in Atomic Congestion Games. Michael Elkin and Shay Solomon. Narrow-Shallow-Low-Light Trees with and without Steiner Points
15.15‑15.40 Coffee
15.40‑16.55 ESA Session 5a
AUD1, Chair: Caragiannis Ioannis
ESA Session 5b
AUD2, Chair: Bengt Nilsson
15.40‑16.05 Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang and Jiajie Zhu. Bounded Budget Betweenness Centrality Game for Strategic Network Formations. Jurek Czyzowicz, Arnaud Labourel and Andrzej Pelc. Optimality and Competitiveness of Exploring Polygons by Mobile Robots.
16.05‑16.30 Elliot Anshelevich and Bugra Caskurlu. Exact and Approximate Equilibria for Optimal Group Network Formation. Rafael Hassin, R Ravi and Fatma Sibel Salman. Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links.
16.30‑16.55 George Christodoulou, Elias Koutsoupias and Paul Spirakis. On the performance of approximate equilibria in congestion games. Navin Goyal, Neil Olver and Bruce Shepherd. Dynamic vs Oblivious Routing in Network Design.
17.00‑18.00 ESA/ALGO Business Meeting (AUD1)
18.00‑21.00 Scroll Bar is open (Scroll Bar)

Tuesday 8 September

8.30–9.00 Coffee. (Registration desk is open.)
9.00–9.50 Invited talk (AUD1, Chair: Peter Sanders)
Erik Demaine. Algorithms Meet Art, Puzzles, and Magic
10.00‑11.15 ESA Session 7a
AUD1, Chair: Alberto Marchetti-Spaccamela
ESA Session 7b
Scroll Bar, Chair: Jiri Sgall
10.00‑10.25 Juraj Stacho and Michel Habib. Polynomial-time algorithm for the leafage of chordal graphs. Jing Xiao, Tiancheng Lou and Tao Jiang. An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants.
10.25‑10.50 Edoardo Amaldi, Claudio Iuliano, Tomasz Jurkiewicz, Kurt Mehlhorn and Romeo Rizzi. Breaking the O(m2 n) Barrier for Minimum Cycle Basis. Gerold Jaeger, Sharlee Climer and Weixiong Zhang. Complete Parsimony Haplotype Inference Problem and Algorithms
10.50‑11.15 Maarten Löffler and Jeff Phillips . Shape Fitting on Point Sets with Probability Distributions. Ross McConnell and Yahav Nussbaum. Linear-time recognition of probe interval graphs.
11.15‑11.40 Coffee
11.40‑12.55 ESA Session 8a
AUD1, Chair: Alberto Marchetti-Spaccamela
ESA Session 8b
Scroll Bar, Chair: Jiri Sgall
11.40‑12.05 Magnus M. Halldorsson. Wireless scheduling with power control. Haim Kaplan and Yahav Nussbaum. Maximum Flow in Directed Planar Graphs with Vertex Capacities.
12.05‑12.30 Chen Avin, Zvi Lotker and Yvonne Anne Pignolet. On the Power of Uniform Power: Capacity of Wireless Networks with Bounded Resources Andrzej Lingas. A fast output-sensitive algorithm for Boolean matrix multiplication.
12.30‑12.55 Marcel Ochel and Berthold Vöcking. Approximability of OFDMA Scheduling Paolo Ferragina, Igor Nitto and Rossano Venturini. On optimally partitioning a text to improve its compression.
13.00‑14.00 Lunch
14.00‑15.15 ESA Session 9a
AUD1, Chair: Kurt Mehlhorn
ESA Session 9b
AUD2, Chair: Philip Bille
14.00‑14.25 Andreas Karrenbauer and Thomas Rothvoss. An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling. Sumit Ganguly and Christian Sohler. d-dimensional Knapsack in the Streaming Model.
14.25‑14.50 Chandra Chekuri, Sungjin Im and Benjamin Moseley. Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling. Atish Das Sarma, Sreenivas Gollapudi and Rina Panigrahy. Sparse Cut Projections in Graph Streams.
14.50‑15.15 Gyorgy Dosa and Leah Epstein. Preemptive online scheduling with reordering Sebastian Eggert, Lasse Kliemann and Anand Srivastav. Bipartite Graph Matchings in the Semi-Streaming Model.
15.15‑15.40 Coffee
15.40‑16.30 ESA Session 10a
AUD1, Chair: Kurt Mehlhorn
ESA Session 10b
AUD2, Chair: Philip Bille
15.40‑16.05 Andrew McGregor, Krzysztof Onak and Rina Panigrahy. The Oil Searching Problem. Alberto Pettarin, Andrea Pietracaprina and Geppino Pucci. On the Expansion and Diameter of Bluetooth-like Topologies.
16.05‑16.30 David Kirkpatrick. Hyperbolic dovetailing. Inge Li Gørtz, Viswanath Nagarajan and R. Ravi. Minimum Makespan Multi-vehicle Dial-a-Ride.
19.00 Conference dinner at Restaurant Hercegovina

Wednesday 9 September

8.30–9.00 Coffee. (Registration desk is open.)
9.00–9.50 Invited talk (AUD1, Chair: Amos Fiat)
Noam Nisan. Google’s Auction for TV Ads.
10.00‑11.15 ESA Session 12a
AUD1, Chair: Pierre Fraigniaud
ESA Session 12b
Scroll Bar, Chair: Christos Zaroliagis
10.00‑10.25 Johan M. M. van Rooij, Jesper Nederlof and Thomas C. van Dijk. Inclusion/Exclusion Meets Measure and Conquer: Exact algorithms for counting dominating sets. Daniel Delling, Thomas Pajor and Dorothea Wagner. Accelerating Multi-Modal Route Planning by Access-Nodes.
10.25‑10.50 Johan M. M. van Rooij, Hans L. Bodlaender and Peter Rossmanith. Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution. Jakub Chaloupka. Parallel Algorithms for Mean-Payoff Games: An Experimental Evaluation.
10.50‑11.15 Andreas Björklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto. Counting Paths and Packings in Halves. Rudolf Fleischer, Xi Wu and Liwei Yuan. Experimental study of FPT algorithms for the directed feedback vertex set problem.
11.15‑11.40 Coffee
11.40‑12.55 ESA Session 13a
AUD1, Chair: Prierre Fraigniaud
ESA Session 13b
Scroll Bar, Chair: Christos Zaroliagis
11.40‑12.05 Markus Blaeser and Christian Hoffmann. Fast Computation of Interlace Polynomials on Graphs of Bounded Treewidth. Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan. Rank-Pairing Heaps.
12.05‑12.30 Hans L. Bodlaender, Stephan Thomasse and Anders Yeo. Kernel Bounds for Disjoint Cycles and Disjoint Paths. Rina Panigrahy and Eric Lehman. 3.5-Way Cuckoo Hashing for the Price of 2.
12.30‑12.55 Dániel Marx and Igor Razgon. Constant ratio fixed-parameter approximation of the edge multicut problem. Djamal Belazzougui, Fabiano Botelho and Martin Dietzfelbinger. Hash, displace, and compress.
13.00‑14.00 Lunch
14.00‑15.15 ESA Session 14a
AUD1, Chair: Stefan Szeider
ESA Session 14b
AUD2, Chair: Christoph Dürr
14.00‑14.25 Geevarghese Philip, Venkatesh Raman and Somnath Sikdar. Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels. Johannes B Hreinsson, Morten Krøyer and Rasmus Pagh. Storing a Compressed Function with Constant Time Access.
14.25‑14.50 Fedor Fomin, Petr Golovach and Dimitrios Thilikos. Contraction Bidimensionality: the accurate picture. Martin Aumüller, Martin Dietzfelbinger and Michael Rink. Experimental variations of a theoretically good retrieval data structure.
14.50‑15.15 Erik D. Demaine, Mohammad Taghi Hajiaghayi and Dániel Marx. Minimizing Movement: Fixed-Parameter Tractability. Johannes Fischer. Short Labels for Lowest Common Ancestors in Trees.
15.15‑15.40 Coffee
15.40‑16.30 ESA Session 15. Best paper awards (AUD1, Chair: Thore Husfeldt)
15.40‑16.10 Best student paper: Heidi Gebauer. Disproof of the Neighborhood Conjecture with Implications to SAT.
16.10‑16.40 Best paper: Christoph Dürr, Flavio Guiñez and Martín Matamala. Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard.
16.40‑16.50 Award ceremony, ESA closing remarks
Helge Sander, Danish Minister of Science, Technology, and Innovation
17.00‑18.00 Bicycle trip through Copenhagen (30 min of cycling)
18.00‑20.00 Reception at Copenhagen City Hall

Thursday 10 September

8.30–9.00 Coffee. (Registration desk is open.)
9.00-9.50 Invited talk (AUD1, Chair: Evripidis Bampis)
Vijay Vazirani. Combinatorial Algorithms for Convex Programs Capturing Market Equilibria and Nash Bargaining Solutions
10.00‑11.15 IWPEC Session 1
AUD1, Chair: H. Fernau
WAOA Session 1
Scroll Bar, Chair: T. Erlebach
ATMOS Session 1
2A20, Chair: A. Schoebel
10.00‑10.25 R. Ganian, P. Hlineny, J. Kneis, A. Langer, J. Obdržálek, and P. Rossmanith. On Digraph Width Measures in Parameterized Algorithmics Xin Han and Kazuhisa Makino. Online Minimization Knapsack Problem Martin Aronsson, Markus Bohlin and Per Kreuger. MILP formulations of cumulative constraints for railway scheduling - A comparative study
10.25‑10.50 M. Fellows, D. Hermelin, and F. A. Rosamond. Well-Quasi-Ordering Bounded Treewidth Graphs Christoph Dürr, Lukasz Jez. and Kim Thang Nguyen. Online Scheduling of Bounded Length Jobs to Maximize Throughput Peter Marton, Jens Maue and Marc Nunkesser. An Improved Train Classification Procedure for the Hump Yard Lausanne Triage
10.50‑11.15 S. Gutner. Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor Prudence W.H. Wong and Fencol C.C. Yung. Competitive Multi-Dimensional Dynamic Bin Packing via L-Shape Bin Packing Twan Dollevoet, Dennis Huisman, Marie Schmidt and Anita Schoebel. Delay Management with Re-Routing of Passengers
11.15‑11.40 Coffee
11.40‑12.55 IWPEC Session 2
AUD1, Chair: Igor Razgon
WAOA Session 2
AUD2: T. Erlebach
ATMOS Session 2
Scroll Bar, Chair: Julie J. Groth
11.40‑12.05 M. Koivisto. Partitioning into Sets of Bounded Cardinality Elisabeth Günther, Felix König and Nicole Megow. Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width Joondong Kim, Alexander Kroeller, Joseph Mitchell and Girishkumar Sabhnani. Scheduling Aircraft to Reduce Controller Workload
12.05‑12.30 D. Lokshtanov and S. Saurabh. Even Faster Algorithm for Set Splitting! Chandra Chekuri, Sungjin Im and Benjamin Moseley. Longest Wait First for Broadcast Scheduling Daniel Delling, Thomas Pajor, Dorothea Wagner and Christos Zaroliagis. Efficient Route Planning in Flight Networks
12.30‑12.55 R. Enciso, M. Fellows, J. Guo, I. Kanj, F. Rosamond, and O. Suchý. What Makes Equitable Connected Partition Easy Klaus Jansen and Christina Otte. Approximation Algorithms for Multiple Strip Packing Apostolos Bessas and Christos Zaroliagis. On Assessing Robustness in Transportation Planning
13.00‑14.00 Lunch
14.00‑14.50 Invited talk (AUD1, Chair: Christos Zaroliagis)
Dorothea Wagner. Algorithm Engineering for Route Planning in Realistic Scenarios
15.00‑16.15 IWPEC Session 3
AUD1, Chair: Thore Husfeldt
WAOA Session 3
AUD2, Chair: B. Nilsson
ATMOS Session 3
Scroll Bar, Chair: Jens Clausen
15.00‑15.25 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 Hadas Shachnai, gal tamir and Tami Tamir. Minimal Cost Reconfiguration of Data Placement in Storage Area Network Olaf Beyersdorff and Yevgen Nebesov. Edges as Nodes - a New Approach to Timetable Information
15.25‑15.50 J. Daligault and S. Thomasse. On finding directed trees with many leaves Dries Goossens, Sergey Polyakovskiy, Frits Spieksma and Gerhard Woeginger. Between a rock and a hard place: The two-to-one assignment problem Annabell Berger, Daniel Delling, Andreas Gebhardt and Matthias Müller-Hannemann. Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected
15.50‑16.15 S. Sikdar, D. Lokshtanov, V. Raman, and S. Saurabh. On the Directed Degree-Preserving Spanning Tree Problem Danny Hermelin and Dror Rawitz. Optimization Problems in Multiple Subtree Graphs Emanuele Berrettini, Gianlorenzo D'Angelo and Daniel Delling. Arc-Flags in Dynamic Graphs
16.15‑16.35 Coffee
16.35‑18.15 IWPEC Session 4
AUD1, Chair: Jonathan Buss
WAOA Session 4
AUD2, Chair: B. Nilsson
16.35‑17.00 J. A. Telle, B.-M. Bui-Xuan and M. Vatshelle. Boolean-width of graphs Reuven Bar-Yehuda, Danny Hermelin and Dror Rawitz. An Extension of the Nemhauser&Trotter Theorem to Generalized Vertex Cover with Applications
17.00‑17.25 P. Golovach and D. Thilikos.Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms Spyros Angelopoulos. On the Competitiveness of the Online Asymmetric and Euclidean Steiner Tree Problems
17.25‑17.50 P. Damaschke. Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms Atish Das Sarma, Amit Deshpande and Ravi Kannan. Finding Dense Subgraphs in G(n,1/2)
17.50‑18.15 L. Kowalik, T. Walen, M. Krnc, and R. Erma. Improved induced matchings in sparse graphs Thomas Erlebach and Matus Mihalak. A (4+e)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs

Friday 11 September

8.30–9.00 Coffee. (Registration desk is open.)
9.00-9.50 Invited talk (AUD1, Chair: Jianer Chen)
Hans Bodlaender. Kernelization: new upper and lower bound techniques
10.00‑11.15 IWPEC Session 5
AUD1, Chair: Saket Saurabh
WAOA Session 5
Scoll Bar, Chair: Danny Hermelin
10.00‑10.25 K. Suchan and Y. Villanger. Computing pathwidth faster than 2n Bodo Manthey. Multi-Criteria TSP: Min and Max Combined
10.25‑10.50 C. Calabro, R. Impagliazzo, and R. Paturi. The complexity of satisfiability of small depth circuits Yuval Emek, Pierre Fraigniaud, Amos Korman and Adi Rosen. On the Additive Constant of the k-Server Work Function Algorithm
10.50‑11.15 M. Furer, S. Gaspers, and S. Kasiviswanathan. An Exponential Time 2-Approximation Algorithm for Bandwidth Ilya Chernykh, Nikita Dryuck, Alexander Kononov and Sergey Sevastianov. The Routing Open Shop Problem: New Approximation Algorithms
11.15‑11.40 Coffee
11.40‑12.55 IWPEC Session 6
AUD1, Chair: Gregory Gutin
WAOA Session 6
Scroll Bar, Chair: Alexander Kononov
11.40‑12.05 H. L. Bodlaender, D. Lokshtanov, and E. Penninkx. Planar Capacitated Dominating Set is W[1]-hard Britta Peis, Martin Skutella and Andreas Wiese. Packet Routing: Complexity and Algorithms
12.05‑12.30 S. Kratsch and M. Wahlström. Two Edge Modification Problems Without Polynomial Kernels Christine Chung, George Christodoulou, Katrina Ligett, Evangelia Pyrga and Rob van Stee. On the Price of Stability for Undirected Network Design
12.30‑12.55 P. Giannopoulos, C. Knauer, and G. Rote. The parameterized complexity of some geometric problems in unbounded dimensions Fedor Fomin, Petr Golovach and Daniel Lokshtanov. Guard games on graphs: keep the intruder out!
13:00‑14:00 Lunch
14.00‑14.50 Invited talk (AUD1, Chair: Fedor Fomin)
Noga Alon. Color Coding, Balanced Hashing and Approximate Counting
15.00‑16.15 IWPEC Session 7
AUD1, Chair: Hans Bodlaender
WAOA Session 7
AUD2, Chair: Klaus Jansen
15.00‑15.25 G. Gutin, E. J. Kim, S. Szeider, and A. Yeo. Probabilistic Approach to Problems Parameterized Above Tight Lower Bound Marcin Bienkowski. Price Fluctuations: To Buy or to Rent
15.25‑15.50 P. Damaschke. Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover Reza Dorrigiv, Martin R. Ehmsen and Alejandro Lopez-Ortiz. Parameterized Analysis of Paging and List Update Algorithms
15.50‑16.15 D. Marx and I. Schlotter. Stable Assignment with Couples: Parameterized Complexity and Local Search Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee and Hing-Fung Ting. Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window
16.15‑16.35 Coffee
16.35‑17.50 IWPEC Session 8
AUD1, Chair: Stefan Szeider
16.35‑17.00 N. Simjour. Improved Parameterized Algorithms for the Kemeny Aggregation Problem
17.00‑17.25 G. Gutin, D. Karapetyan, and I. Razgon. FPT Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs
17.25‑17.50 S. Böcker, F. Hüffner, A. Truss, and M. Wahlström. A faster fixed-parameter approach to drawing binary tanglegrams