ALGO 2014 Schedule
- Each regular presentation is alloted a slot of 25 minutes. Usually, the last 5 minutes should be reserved for questions and discussion. Each invited talk is allotted a slot of 60 minutes.
- The conferences will take place in four rooms: GE (Great Eastern, doors 25, 27 & 121), GW (Great Western, doors 12, 13 & 116), SE (Small Eastern, door 119), SW (Small Western, door 118).
- Each room has a beamer with VGA and HDMI connectors, capable of displaying the resolution of at least 1024 x 768. No overhead projectors are available. We expect the speakers to bring their own laptops (or other presenting devices).
- For invited talks and tutorials, click on the title to see the abstract.
- "SC" stands for Session Chair.
- The schedule is also available in the conference booklet. A printed version will be handed out to the participants.
Monday, September 8th
| ESA 1 | ESA 2 | WABI | |
| 08:55-09:00 | Welcome, Room GE | ||
| 09:00-10:00 | Invited talk (ESA): Thomas Rothvoß (University of Washington): Lower bounds on the size of linear programs, Room GE | ||
| 10:00-10:20 | Coffee break | ||
| Fixed Parameter Tractability. SC: Alexander Wolff, Room GE | Data Structures. SC: Piotr Sankowski, Room GW | Phylogenetics. SC: Sagi Snir, Room SE | |
| 10:20-10:45 | Fedor Fomin, Daniel Lokshtanov, Fahad Panolan and Saket Saurabh: Representative Sets of Product Families | Bryan T. Wilkinson: Amortized Bounds for Dynamic Orthogonal Range Searching | Sagi Snir: Pacemaker Partition Identification |
| 10:45-11:10 | Hadas Shachnai and Meirav Zehavi: Representative Families: A Unified Tradeoff-Based Approach | Daniel Larkin and Robert Tarjan: Nested Set Union | Luis Cunha, Luis Kowada, Rodrigo Hausen and Celina Figueiredo: A Faster 1.375-Approximation Algorithm for Sorting by Transpositions |
| 11:10-11:35 | Bart M. P. Jansen: Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes | Moshe Lewenstein, Ian Munro, Patrick K. Nicholson and Venkatesh Raman: Improved Explicit Data Structures in the Bitprobe Model | Burkhard Morgenstern, Binyao Zhu, Sebastian Horwege and Chris-Andre Leimeister: Estimating evolutionary distances from spaced-word matches |
| 11:35-12:00 | Petr Golovach, Marcin Kamiński, Spyridon Maniatis and Dimitrios Thilikos: The Parameterized Complexity of Graph Cyclability | Umut Acar, Arthur Chargueraud and Mike Rainey. Theory and Practice of Chunked Sequences | |
| 12:00-13:30 | Lunch & coffee | ||
| ESA Best Paper and Best Student Paper Award Session. SC: Dorothea Wagner, Room GE | Laboratory techniques #1. SC: Paolo Bonizzoni, Room SE | ||
| 13:30-13:55 | Eiwen Yang and Tao Jiang: GDNorm: An Improved Poisson Regression Model for Reducing Biases in Hi-C Data | ||
| 13:55-14:20 | Best Paper: Pooya Davoodi, Jeremy Fineman, John Iacono and Ozgur Ozkan: Cache-Oblivious Persistence, Room GE | Gustavo Sacomoto, Blerina Sinaimeri, Camille Marchet, Vincent Miele, Marie-France Sagot and Vincent Lacroix: Navigating in a sea of repeats in RNA-seq without drowning | |
| 14:20-14:45 | Best Paper: Joshua Wang: Space-Efficient Randomized Algorithms for K-SUM, Room GE | Yu-Ting Huang and Marek Chrobak: An LP-Rounding Algorithm for Degenerate Primer Design | |
| 14:45-15:05 | Coffee break | ||
| Online Algorithms. SC: Giuseppe Italiano, Room GE | Graph Algorithms I. SC: Ignaz Rutter, Room GW | Genome assembly. SC: Brona Brejova, Room SE | |
| 15:05-15:30 | Moses Charikar, Monika Henzinger and Huy Nguyen: Online Bipartite Matching with Decomposable Weights | Zdenek Dvorak and Matthias Mnich: Large Independent Sets in Triangle-Free Planar Graphs | Vladimír Boža, Broňa Brejová and Tomáš Vinař: GAML: Genome Assembly by Maximum Likelihood |
| 15:30-15:55 | Anupam Gupta and Marco Molinaro: How Experts Can Solve LPs Online | Rui Ferreira, Roberto Grossi, Romeo Rizzi, Gustavo Sacomoto and Marie-France Sagot: Amortized Õ(|V|)-Delay Algorithm for Listing Chordless Cycles in Undirected Graphs | Matteo Comin, Andrea Leoni and Michele Schimd: QCluster: Extending Alignment-free Measures with Quality Values for Reads Clustering |
| 15:55-16:20 | Niv Buchbinder, Shahar Chen and Seffi Naor: Competitive Algorithms for Restricted Caching and Matroid Caching | Zdenek Dvorak, Martin Kupec and Vojtech Tuma: A dynamic data structure for MSO properties in graphs with bounded tree-depth | Yu Lin and Pavel Pevzner: Manifold de Bruijn graphs |
| 16:20-16:40 | Coffee break | ||
| Computational Algebra. SC: Dorothea Wagner, Room GE | Graph Algorithms II. SC: Uli Meyer, Room GW | WABI business meeting, Room SE | |
| 16:40-17:05 | Clément Maria and Jean-Daniel Boissonnat: Computing Persistent Homology with Various Coefficient Fields in a Single Pass | Pavol Hell, Bojan Mohar and Arash Rafiey: Ordering without forbidden patterns | |
| 17:05-17:30 | Arnab Bhattacharyya: Polynomial decompositions in polynomial time | Guy Even, Moti Medina and Dana Ron: Deterministic Stateless Local Centralized Algorithms for Bounded Degree Graphs | |
| 17:30-17:55 | Andreas Björklund, Petteri Kaski and Łukasz Kowalik: Fast Witness Extraction Using a Decision Oracle | Florian Merz and Peter Sanders: PReaCH: A Fast Lightweight Reachability Index using Pruning and Contraction Hierarchies | |
| 17:55-18:05 | |||
| 18:05-19:30 | ESA business meeting, Room GE | ||
| 19:30-20:00 | Welcome drink (ground floor) | ||
Tuesday, September 9th
| ESA 1 | ESA 2 | WABI | |
| 09:00-10:00 | Invited talk (ESA): Marc van Kreveld (Utrecht University): Trajectory Data Analysis, Room GE | ||
| 10:00-10:20 | Coffee break | ||
| Approximation Algorithms I. SC: Aleksander Mądry, Room GE | Time-Space Tradeoff. SC: Rossano Venturini, Room GW | Mass spectrometry and proteomics. SC: Sebastian Böcker, Room SE | |
| 10:20-10:45 | Harald Räcke and Chintan Shah: Improved Guarantees for Tree Cut Sparsifiers | Tomasz Kociumaka, Tatiana Starikovskaya and Hjalte Wedel Vildhøj: Sublinear Space Algorithms for the Longest Common Substring Problem | Dominik Kopczynski and Sven Rahmann: An Online Peak Extraction Algorithm for Ion Mobility Spectrometry Data |
| 10:45-11:10 | Venkatesan Chakaravarthy, Anamitra Roy Choudhury, Shalmoli Gupta, Sambuddha Roy and Yogish Sabharwal: Improved Algorithms for Resource Allocation Under Varying Capacity | Paweł Gawrychowski, Moshe Lewenstein and Patrick K. Nicholson: Weighted ancestors in suffix trees | Kerstin Scheubert, Franziska Hufsky and Sebastian Böcker: Multiple Mass Spectrometry Fragmentation Trees Revisited: Boosting Performance and Quality |
| 11:10-11:35 | Alantha Newman: The traveling salesman problem on subquartic graphs | Andrew McGregor, Eric Price and Sofya Vorotnikova: Trace Reconstruction Revisited | Sharon Bruckner, Falk Hüffner and Christian Komusiewicz: A Graph Modification Approach for Finding Core–Periphery Structures in Protein Interaction Networks |
| 11:35-12:00 | Jianer Chen, Wenjun Li and Jianxin Wang: Deeper Local Search for better Approximation on Maximum Internal Spanning Trees | Omar Darwish and Amr Elmasry: Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem | |
| 12:00-13:30 | Lunch & coffee | ||
| Packing, Scheduling and Self-Assembly. SC: Bettina Speckmann, Room GE | Structural Results. SC: Christos Zaroliagis, Room GW | Genome rearrangement and the DCJ operation. SC: Max Alekseyev, Room SE | |
| 13:30-13:55 | Fidaa Abed, Jose Correa and Chien-Chung Huang: Optimal Coordination Mechanisms for Multi-Job Scheduling Games | Michael A. Bender, Martin Farach-Colton, Mayank Goswami, Dzejla Medjedovic, Pablo Montes and Meng-Tsung Tsai: The Batched Predecessor Problem in External Memory | Fábio Henrique Viduani Martinez, Pedro Feijão, Marília Braga and Jens Stoye: On the family-free DCJ distance |
| 13:55-14:20 | Caleb Malchik and Andrew Winslow: Tight Bounds for Active Self-Assembly Using an Insertion Primitive | Zhewei Wei and Ke Yi: Equivalence between Priority Queues and Sorting in External Memory | Shuai Jiang and Max Alekseyev: Linearization of Median Genomes under DCJ |
| 14:20-14:45 | Flavio K. Miyazawa, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Maxim Sviridenko and Yoshiko Wakabayashi: Polynomial-Time Approximation Schemes for Circle Packing Problems | Stacey Jeffery, Frederic Magniez and Ronald de Wolf: Optimal parallel quantum query algorithms | Phillip Compeau: A Generalized Cost Model for DCJ-Indel Sorting |
| 14:45-15:05 | Coffee break | ||
| Approximate Counting and Sampling. SC: Aleksander Mądry, Room GE | FPT Algorithms. SC: Alexander Wolff, Room GW | Laboratory techniques #2. SC: Gene Myers, Room SE | |
| 15:05-15:30 | Charilaos Efthymiou: Switching colouring of G(n,d/n) for sampling up to Gibbs Uniqueness Threshold | Gregory Gutin, Mark Jones and Bin Sheng: Parameterized Complexity of the k-Arc Chinese Postman Problem | Adrin Jalali and Nico Pfeifer: Interpretable per Case Weighted Ensemble Method for Cancer Associations |
| 15:30-15:55 | Romeo Rizzi and Alexandru I. Tomescu: Faster FPTASes for counting and random generation of Knapsack solutions | Ivan Bliznets, Fedor Fomin, Marcin Pilipczuk and Michał Pilipczuk: A subexponential parameterized algorithm for Proper Interval Completion | Chen Gu, Leonidas Guibas and Michael Kerber: Topology-driven Trajectory Synthesis with an Example on Retinal Cell Motions |
| 15:55-16:20 | Jingcheng Liu, Pinyan Lu and Chihao Zhang: FPTAS of Counting Weighted Edge Covers | Amir Abboud, Kevin Lewi and Ryan Williams: Losing Weight by Gaining Edges | Iman Hajirasouliha and Benjamin Raphael: Reconstructing mutational history in multiply sampled tumors using perfect phylogeny mixtures |
| 16:20-16:40 | Coffee break | ||
| Data Structures and Compression. SC: Kevin Buchin, Room GE | Computational Complexity. SC: Riko Jacob, Room GW | WABI poster session | |
| 16:40-17:05 | Timothy M. Chan, Meng He, J. Ian Munro and Gelin Zhou: Succinct Indices for Path Minimum, with Applications to Path Reporting | Daniel Lokshtanov, Saket Saurabh and Ondrej Suchy: Solving Multicut Faster than 2^n | |
| 17:05-17:30 | Andrea Farruggia, Paolo Ferragina and Rossano Venturini: Bicriteria data compression: efficient and usable | Rasmus Pagh and Morten Stöckel: The Input/Output Complexity of Sparse Matrix Multiplication | |
| 17:30-17:55 | Gonzalo Navarro, Simon J. Puglisi and Jouni Sirén: Document Retrieval on Repetitive Collections | Dominique Attali, Olivier Devillers, Marc Glisse and Sylvain Lazard: Recognizing shrinkable complexes is NP-complete | |
| 17:55-18:00 | |||
| 18:00-19:30 | Excursion (including boat trip) to conference dinner site | ||
| 19:30-22:00 | Conference dinner | ||
Wednesday, September 10th
| ESA 1 | ESA 2 | WABI | IPEC | |
| 09:00-10:00 | Invited talk (WABI): Hélène Touzet, (University of Lille): Some algorithms for RNA analysis, Room GE | |||
| 10:00-10:20 | Coffee break | |||
| Shortest Paths. SC: Dorothea Wagner, Room GE | Computational Geometry I. SC: Marc van Kreveld, Room GW | Sequence alignment. SC: Matteo Comin, Room SE | Kernelization. SC: Marek Cygan, Room SW | |
| 10:20-10:45 | Daniel Delling, Andrew Goldberg, Thomas Pajor and Renato Werneck: Robust Distance Queries on Massive Networks | Michael Hoffmann, Vincent Kusters and Tillmann Miltzow: Halving Balls in Deterministic Linear Time | Sebastian Will and Peter F. Stadler: A Common Framework for Linear and Cyclic Multiple Sequence Alignment Problem | Marthe Bonamy and Łukasz Kowalik: A 14k-kernel for Planar Feedback Vertex Set via Region Decomposition |
| 10:45-11:10 | Davide Bilò, Luciano Gualà, Stefano Leucci and Guido Proietti: Fault-Tolerant Approximate Shortest-Path Trees | Matt Gibson, Kasturi Varadarajan and Xiaodong Wu: Computing Regions Decomposable into m Stars | Nicolas Boria, Adam Kurpisz, Samuli Leppänen and Monaldo Mastrolilli: Improved Approximation for the Maximum Duo-Preservation String Mapping Problem | Gregory Gutin, Stefan Kratsch and Magnus Wahlström: Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem |
| 11:10-11:35 | Rachit Agarwal: The Space-Stretch-Time Tradeoff in Distance Oracles | Rinat Ben-Avraham, Matthias Henze, Rafel Jaume, Balazs Keszegh, Orit E. Raz, Micha Sharir and Igor Tubis: Minimum Partial Matching and Hausdorff RMS-Distance Under Translation: Combinatorics and Algorithms | Laxmi Parida, Cinzia Pizzi and Simona E. Rombo: Entropic profiles, maximal motifs and the discovery of significant repetitions in genomic sequences | N.R. Aravind, R.B. Sandeep and Naveen Sivadasan: On Polynomial Kernelization of H-free Edge Deletion |
| 11:35-12:00 | Alexandros Efentakis and Dieter Pfoser: GRASP. Extending Graph Separators for the single-source shortest-path problem | Sariel Har-Peled and Subhro Roy: Approximating the Maximum Overlap of Polygons under Translation | Eugene Myers: Efficient Alignment Discovery amongst Noisy Long Reads | Vuong Anh Quyen and Stefan Kratsch: On kernels for covering and packing ILPs with small coefficients |
| 12:00-13:15 | Lunch & coffee | |||
| 13:15-13:30 | NOKIA (ALGO sponsor): For a World in Motion, Room GW | |||
| 13:30-13:45 | ||||
| 13:45-14:45 | Invited talk (IPEC): Hans Bodlaender (Utrecht University): Lowerbounds for Kernelization, Room GE | |||
| 14:45-15:05 | Coffee break | |||
| Approximation Algorithms II. SC: Marek Cygan, Room GE | Convex Hulls, LPs, and Branch & Price. SC: Guido Proietti, Room GW | Systems programming issues. SC: Tomas Vinar, Room SE | Degrees in graphs. SC: Pinar Heggernes, Room SW | |
| 15:05-15:30 | Alina Ene and Huy Nguyen: From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route? | Pankaj K. Agarwal, Sariel Har-Peled, Subhash Suri, Hakan Yıldız and Wuzhou Zhang: Convex Hulls under Uncertainty | Paola Bonizzoni, Gianluca Della Vedova, Yuri Pirola, Marco Previtali and Raffaella Rizzi: Constructing String Graphs in External Memory | Jannis Bulian and Anuj Dawar: Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree |
| 15:30-15:55 | Parinya Chalermsook, Sandy Heydrich, Eugenia Holm and Andreas Karrenbauer: Nearly Tight Approximability Results for Minimum Biclique Cover and Partition | Martin Grohe, Kristian Kersting, Martin Mladenov and Aziz Erkal Selman: Dimension Reduction via Colour Refinement | Tomas Flouri, Alexandros Stamatakis, Kassian Kobert and Andre Aberer: The divisible load balance problem and its application to phylogenetic inference | Petr Golovach: Editing to a Graph of Given Degrees |
| 15:55-16:20 | Samuel Fiorini, R. Krithika, N.S. Narayanaswamy and Venkatesh Raman: LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs | Martijn van Brink and Ruben van der Zwaan: A branch and price procedure for the container premarshalling problem | Martin Muggli, Simon J. Puglisi and Christina Boucher: Efficient Indexed Alignment of Contigs to Optical Maps | Cristina Bazgan and André Nichterlein: Parameterized Inapproximability of Degree Anonymization |
| 16:20-16:40 | Coffee break | |||
| Dealing with Large Structures. SC: Renato Werneck, Room GE | Computational Geometry II. SC: Kevin Buchin, Room GW | Population genetics. SC: Laxmi Parida, Room SE | Lower bounds. SC: Martin Grohe, Room SW | |
| 16:40-17:05 | Mina Ghashami, Amey Desai and Jeff Phillips: Improved Practical Matrix Sketching with Guarantees | Siu-Wing Cheng, Liam Mencel and Antoine Vigneron: A Faster Algorithm for Computing Straight Skeletons | Niina Haiminen, Claude Lebreton and Laxmi Parida: Best-Fit in Linear Time for Non-generative Population Simulation | Igor Razgon: No small nondeterministic read-once branching programs for CNFs of bounded treewidth |
| 17:05-17:30 | Brian Dean, Rommel Jalasutram and Chad Waters: Lightweight Approximate Selection | Thomas Bläsius, Ignaz Rutter and Guido Brückner: Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model | Constantinos Tsirogiannis, Brody Sandel and Adrija Kalvisa: New Algorithms for Computing Phylogenetic Biodiversity | Holger Dell: AND-compression of NP-complete problems: Streamlined proof and minor observations |
| 17:30-17:55 | Karl Bringmann, Tobias Friedrich and Anton Krohmer: De-anonymization of Heterogeneous Random Graphs in Quasilinear Time | Michael Bekos, Thomas C. Van Dijk, Martin Fink, Philipp Kindermann, Stephen Kobourov, Sergey Pupyrev, Joachim Spoerhase and Alexander Wolff: Improved Approximation Algorithms for Box Contact Representations | Patrick Traxler: The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments | |
| 17:55-18:20 | Sander Alewijnse, Quirijn Bouts and Alex Ten Brink: Distribution-Sensitive Construction of the Greedy Spanner | |||
Thursday, September 11th
| ATMOS | MASSIVE | WAOA | IPEC | |
| 09:00-10:00 | Invited talk (ATMOS): Renato Werneck (Microsoft Research): Building a Real-World Routing Engine, Room GE | |||
| 10:00-10:20 | Coffee break | |||
| Session #1. SC: Matúš Mihalák, Room SW | I/O and cache-oblivious algorithms. SC: Deepak Ajwani, Room SE | Session #1, Room GW | Structural parameterization, treewidth. SC: Hans Bodlaender, Room GE | |
| 10:20-10:45 | Julian Dibbelt, Ben Strasser and Dorothea Wagner: Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time | Lars Arge and Mikkel Thorup: RAM Efficient external memory algorithms | Marie G. Christ, Lene Favrholdt and Kim S. Larsen: Online Multi-Coloring with Advice | Zoltán Király: Shortest Paths in Nearly Conservative Digraphs |
| 10:45-11:10 | Tim Nonner and Marco Laumanns: Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments | Peyman Afshani and Nodari Sitchinava: I/O-efficient range minima queries | Martin Böhm, Jiří Sgall and Pavel Veselý: Online Colored Bin Packing | Janka Chlebikova and Morgan Chopin: The Firefighter Problem: A Structural Analysis |
| 11:10-11:35 | Alessio Cionini, Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Kalliopi Giannakopoulou, Andreas Paraskevopoulos and Christos Zaroliagis: Engineering Graph-Based Models for Dynamic Timetable Information Systems | Francesco Silvestri: Subgraph enumeration in massive graphs | Martin Böhm, Jiří Sgall, Rob van Stee and Pavel Veselý: Better Algorithms for Online Bin Stretching | Jan Obdrzalek, Jakub Gajarský, Felix Reidl, Peter Rossmanith, Fernando Sanchez Villaamil, Somnath Sikdar and Sebastian Ordyniak: Finite Integer Index of Pathwidth and Treewidth |
| 11:35-12:00 | Martin Lemnian, Ralf Rückert, Steffen Rechner, Christoph Blendinger and Matthias Müller-Hannemann: Timing of Train Disposition: Towards Early Passenger Rerouting in Case of Delays | Pooya Davoodi, Jeremy Fineman, John Iacono and Ozgur Ozkan: Cache-oblivious persistence | Brian Brubach: Online square-into-square packing with fixed and variable height shelves | Julien Baste and Ignasi Sau: The role of planarity in connectivity problems parameterized by treewidth |
| 12:00-13:15 | Lunch & coffee | |||
| 13:15-13:30 | Neurosoft (ALGO sponsor): Looking for the meaning of data — big data applications in Intelligent Transportation Systems, Room GW | |||
| 13:30-13:45 | ||||
| 13:45-14:45 | Invited talk (WAOA): Aleksander Mądry (EPFL): From Graphs to Matrices, and Back: Bridging the Combinatorial and the Continuous, Room GE | |||
| 14:45-15:05 | Coffee break. IPEC poster session | |||
| Session #2. SC: Stefan Funke, Room SW | Parallel and distributed algorithms. SC: Gerth Stølting Brodal, Room SE | Session #2, Room GW | Invited Tutorial. SC: Pinar Heggernes, Room GE | |
| 15:05-15:30 | Vianney Boeuf and Frédéric Meunier: Online Train Shunting | Erika Duriakova, Neil Hurley, Deepak Ajwani and Alessandra Sala: Balancing Synchronization and Consistency: Engineering Semi-synchronous Community Finding Algorithms | Vincent Cohen-Addad, Zhentao Li, Claire Mathieu and Ioannis Milis: Energy-efficient algorithms for non-preemptive speed-scaling | Stefan Szeider: Backdoors, Satisfiability, and Problems Beyond NP |
| 15:30-15:55 | Markus Reuther, Ralf Borndoerfer and Thomas Schlechte: A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem | Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic and Qin Zhang: Communication Complexity of Distributed Computation of Approximate Maximum Matching | Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan and Jaroslav Opatrny: Optimal online and offline algorithms for robot-assisted restoration of barrier coverage | |
| 15:55-16:20 | Ward Passchyn, Dirk Briskorn and Frits C. R. Spieksma: Mathematical programming models for scheduling locks in sequence | Dominik Köppl: Dynamic Skyline computation with the skyline breaker algorithm | Martina Eikel, Christian Scheideler and Alexander Setzer: Minimum Linear Arrangement of Series-Parallel Graphs | |
| 16:20-16:40 | Coffee break. IPEC poster session | |||
| Session #3. SC: Matthias Müller-Hannemann, Room SW | Data structures and streaming. SC: Nodari Sitchinava, Room SE | Session #3, Room GW | Languages, automata and logic. SC: Holger Dell, Room GE | |
| 16:40-17:05 | Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor and Dorothea Wagner: Speed-Consumption Tradeoff for Electric Vehicle Route Planning | Mina Ghashami, Jeff M. Phillips and Feifei Li: Continuous matrix approximation on distributed data | Rudolf Scheifele: Steiner Trees with Bounded RC-Delay | Tatsuya Akutsu, Jesper Jansson, Atsuhiro Takasu and Takeyuki Tamura: On the Parameterized Complexity of Associative and Commutative Unification |
| 17:05-17:30 | Esther Arkin, Paz Carmi, Matthew Katz, Joseph Mitchell and Michael Segal: Locating Battery Charging Stations to Facilitate Almost Shortest Paths | Zhewei Wei and Ke Yi: On range summary queries | Nachshon Cohen and Zeev Nutov: Approximating {0,1,2}-Survivable Networks with Minimum Number of Steiner Points | Simone Bova, Robert Ganian and Stefan Szeider: Quantified Conjunctive Queries on Partially Ordered Sets |
| 17:30-17:55 | Markus Reuther: Local Search for the Resource Constrained Assignment Problem | MASSIVE business meeting, Room SE | Sin-Shuen Cheung: The submodular facility location problem and the submodular joint replenishment problem | Ran Ben-Basat, Ariel Gabizon and Meirav Zehavi: The k-Distinct Language: Parameterized Automata Constructions |
| 17:55-18:00 | Alicia De-Los-Santos, Gilbert Laporte, Juan A. Mesa and Federico Perea: Simultaneous frequency and capacity setting for rapid transit systems with a competing mode and capacity constraints | |||
| Session #4, Room GW | IPEC business meeting, Room GE | |||
| 18:00-18:20 | Ojas Parekh and David Pritchard: Generalized Hypergraph Matching via Iterated Packing and Local Ratio | |||
| 18:20-18:25 | ||||
| 18:25-18:50 | Guilherme D. Da Fonseca, Vinícius G. Pereira de Sá and Celina M. H. de Figueiredo: Linear-Time Approximation Algorithms for Unit Disk Graphs | |||
| 18:50-19:15 | ||||
| 19:15-22:00 | Barbecue in botanic garden | |||
Friday, September 12th
| ALGOSENSORS | WAOA | IPEC | |
| 09:00-10:00 | Invited talk (ALGOSENSORS): Phillip Gibbons (Intel Labs Pittsburgh): Algorithmic Challenges in M2M, Room GE | ||
| 10:00-10:20 | Coffee break | ||
| Robot Planning. SC: Mayank Goswami, Room SE | Session #5, Room GW | FPT and exact algorithms. SC: Hans Bodlaender, Room GE | |
| 10:20-10:45 | Jurek Czyzowicz, Leszek Gąsieniec, Konstantinos Georgiou, Evangelos Kranakis and Fraser MacQuarrie: The Multi-source Beachcombers' Problem | Andreas Wierz, Britta Peis and Tom Mccormick: Primal-Dual Algorithms for Precedence Constrained Covering Problems | Vikraman Arvind and Gaurav Rattan: The Parameterized Complexity of Geometric Graph Isomorphism |
| 10:45-11:10 | Eric Aaron, Danny Krizanc and Elliot Meyerson: Multi-Robot Foremost Coverage of Time-varying Graphs | Jaroslaw Byrka and Bartosz Rybicki: Improved approximation algorithm for Fault-Tolerant Facility Placement | Henry Perret Du Cray and Ignasi Sau: Improved FPT algorithms for weighted independent set in bull-free graphs |
| 11:10-11:35 | Christian Ortolf and Christian Schindelhauer: Strategies for Parallel Unaware Cleaners | Yann Disser, Stefan Kratsch and Manuel Sorge: The Minimum Feasible Tileset problem | Ron Y. Pinter, Hadas Shachnai and Meirav Zehavi: Improved Parameterized Algorithms for Network Query Problems |
| 11:35-12:00 | Serafino Cicerone, Gabriele Di Stefano and Alfredo Navarra: Gathering of Oblivious Robots over Fixed Points | Alexander Ageev and Alexander Kononov: Improved Approximations for the Max k-Colored Clustering Problem | Mathieu Chapelle, Manfred Cochefert, Dieter Kratsch, Romain Letourneur and Mathieu Liedloff: Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size |
| 12:00-13:30 | Lunch & coffee | ||
| Algorithms & Data Structures on Graphs. SC: Chris Gniady, Room SE | Invited Tutorial, Room GW | Parameterized study. SC: Holger Dell, Room GE | |
| 13:30-13:55 | Avery Miller and Andrzej Pelc: Fast Rendezvous with Advice | Monaldo Mastrolilli: The Lasserre/Sum-of-Squares Hierarchy: a gentle introduction | Sebastian Ordyniak and Alexandru Popa: A Parameterized Study of Maximum Generalized Pattern Matching Problems |
| 13:55-14:20 | Emmanuel Godard and Dorian Mazauric: Computing the Dynamic Diameter of Non-Deterministic Dynamic Networks is Hard | Rajesh Chitnis, Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz and Saeedreza Seddighin: A Tight Algorithm for Strongly Connected Steiner Subgraph On Two Terminals With Demands | |
| 14:20-14:45 | Stefan Dobrev and Milan Plžík: Improved Spanners in Networks with Symmetric Directional Antennas | V. Arvind, Johannes Köbler, Sebastian Kuhnert and Jacobo Torán: Solving Linear Equations Parameterized by Hamming Weight | |
| 14:45-15:05 | Coffee break | ||
| Wireless Networks. SC: Jie Gao, Room SE | Session #6, Room GW | Reconfiguration problems. SC: Marek Cygan, Room GE | |
| 15:05-15:30 | Rom Aschner, Gui Citovsky and Matthew Katz: Exploiting Geometry in the SINRk Model | Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs and Michele Scquizzato: A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line | Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel and Daniel Paulusma: Finding Shortest Paths between Graph Colourings |
| 15:30-15:55 | Yves Brise, Kevin Buchin, Dustin Eversmann, Michael Hoffmann and Wolfgang Mulzer: Interference Minimization in Asymmetric Sensor Networks | Lene Favrholdt and Jesper With Mikkelsen: Online Dual Edge Coloring of Paths and Trees | Amer Mouawad, Naomi Nishimura, Venkatesh Raman and Marcin Wrochna: Reconfiguration over tree decompositions |
| 15:55-16:20 | Jonathan Gagnon and Lata Narayanan: Minimum Latency Aggregation Scheduling in Wireless Sensor Networks | Jiří Sgall and Gerhard J. Woeginger: Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms | Paul Bonsma, Amer Mouawad, Naomi Nishimura and Venkatesh Raman: The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration |
| 16:20-16:40 | Coffee break | ||
| Session #7, Room GW | |||
| 16:40-17:05 | Wolfgang Dvořák and Monika Henzinger: Online Ad Assignment with an Ad Exchange | ||
| 17:05-17:30 | Tomasz Jurdziński, Dariusz Kowalski and Krzysztof Loryś: Online Packet Scheduling under Adversarial Jamming | ||
| 17:30-17:55 | Martijn van Ee and Rene Sitters: Routing under Uncertainty: the a priori Traveling Repairman Problem | ||
