Version of September 10, 17:10Monday 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
|
|
|