ALGO 2015 Detailed Program
- Each regular presentation is alloted a slot of 25 minutes. Usually, the last 4-5 minutes are reserved for questions and discussion.
- Each plenary talk is allotted a slot of 45 minutes. The last 5 minutes are reserved for questions and discussion.
- "SC" stands for Session Chair.
Monday, 14 September 2015
| ESA 1 | ESA 2 | ALGOCLOUD | |
| 08:00 | Registration | ||
| 08:55-09:00 | Opening & Welcome | ||
| 09:00-09:45 |
Plenary Talk 1: Paul Spirakis
(University of Liverpool, UK; CTI & University of Patras, GR) On the Discrete Dynamics of Probabilistic (Finite) Population Protocols SC: Nikhil Bansal |
||
| 09:45-10:00 | BREAK | ||
| Session1A: Streaming and Dynamic Graphs. SC: Cynthia Phillips: | Session1B: Fixed Parameter Algorithms. SC: Hans Bodlaender | Session1C: Algorithmic Aspects of Large-Scale Data Stores I. SC: Spyros Sioutas | |
| 10:00-10:25 | Marc Bury and Chris Schwiegelshohn. Sublinear Estimation of Weighted Matchings in Dynamic Data Streams |
Pål Grønås Drange, Markus Sortland Dregi, Daniel Lokshtanov and Blair D. Sullivan. On the Threshold of Intractability |
Shlomi Dolev and Yin Li. Secret Shared Random Access Machine |
| 10:25-10:50 | Christian Konrad. Maximum Matching in Turnstile Streams |
Gregory Gutin, Mark Jones and Magnus Wahlström. Structural Parameterizations of the Mixed Chinese Postman Problem |
Ikbel Belaid and Lionel Eyraud-Dubois. Column Generation Integer Programming for Allocating Jobs with Periodic Demand Variations |
| 10:50-11:15 | Elisabetta Bergamini and Henning Meyerhenke. Fully-Dynamic Approximation of Betweenness Centrality |
Ariel Gabizon, Daniel Lokshtanov and Michał Pilipczuk. Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints |
Hillel Avni, Shlomi Dolev, Niv Gilboa and Ximing Li. SSSDB: Database with Private Information Search |
| 11:15-11:30 | BREAK | ||
| Session2A: Geometric Algorithms. SC: Peyman Afshani | Session2B: Algorithmic Game Theory. SC: Christoph Durr | Session2C: Algorithmic Aspects of Large-Scale Data Stores II. SC: Evaggelia Pitoura | |
| 11:30-11:55 | Alon Baram, Efi Fogel, Dan Halperin, Michael Hemmer and Sebastian Morr. Exact Minkowski Sums of Polygons With Holes |
George Christodoulou, Alkmini Sgouritsa and Bo Tang. On the Efficiency of All-Pay Mechanisms |
Marios Kendea, Vassiliki Gkantouna, Angeliki Rapti, Spyros Sioutas, Giannis Tzimas and Dimitrios Tsolis. Graph DBs vs Column-Oriented Stores: A Pure Performance Comparison |
| 11:55-12:20 | Adam Bohn, Yuri Faenza, Samuel Fiorini, Vissarion Fisikopoulos, Marco Macchia and Kanstantsin Pashkovich. Enumeration of 2-Level Polytopes |
Anthony Kim. Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems |
Panagiotis Antonellis, Christos Makris and Georgios Pispirigos. Distributed XML Filtering Using HADOOP Framework |
| 12:20-12:45 | Kevin Buchin, Tim Ophelders and Bettina Speckmann. Computing the Similarity Between Moving Curves |
Mohammadhossein Bateni, Sina Dehghani, Mohammadtaghi Hajiaghayi and Saeed Seddighin. Revenue Maximization for Selling Multiple Correlated Items |
Shahin Kamali. Efficient Bin Packing Algorithms for Resource Provisioning in the Cloud |
| 12:45-14:00 | LUNCH | ||
| Session3A: Strings and Data structures. SC: Riko Jacob | Session3B: Online Secretary and Prophets. SC: Nikhil Bansal | Session3C: Tutorial 1 SC: Anastasios Gounaris |
|
| 14:00-14:25 | Ian Munro and Yakov Nekrich. Compressed Data Structures for Dynamic Sequences |
Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Vahid Liaghat and Morteza Monemizadeh. Prophet Secretary |
Peter Triantafillou. Performance and Scalability of Indexed Subgraph Query Processing Methods |
| 14:25-14:50 | Djamal Belazzougui, Patrick Hagge Cording, Simon J. Puglisi and Yasuo Tabei. Access, Rank, and Select in Grammar-Compressed Strings |
Paul Duetting and Robert Kleinberg. Polymatroid Prophet Inequalities |
|
| 14:50-15:15 | Johannes Fischer, Travis Gagie, Pawel Gawrychowski and Tomasz Kociumaka. Approximating LZ77 via Small-Space Multiple-Pattern Matching Raphael Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach and Tatiana Starikovskaya. Dictionary Matching in a Stream |
Ilia Gorelik, Amos Fiat, Haim Kaplan and Slava Novgorodov. The Temp Secretary Problem |
|
| 15:15-15:30 | BREAK | ||
| Session4A: Fixed Parameter and Exact Algorithms. SC: Michal Pilipczuk | Session4B: Combinatorics. SC: Monaldo Mastrolilli | Session4C: Tutorial 2 SC: Spyros Sioutas |
|
| 15:30-15:55 | Hans L. Bodlaender and Jesper Nederlof. Subexponential Time Algorithms for Finding Small Tree and Path Decompositions |
Michael Dinitz, Michael Schapira and Asaf Valadarsky. Explicit Expanding Expanders |
Vassilios Verykios.Distributed Privacy Preserving Record-Linkage |
| 15:55-16:20 | Éric Colin de Verdière. Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals |
Friedrich Eisenbrand, Shay Moran, Rom Pinchasi and Martin Skutella. Node-balancing by Edge-Increments |
|
| 16:20-16:45 | Arnaud De Mesmay and Vincent Viallat Cohen Addad. A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface |
Torsten Mütze and Jerri Nummenpalo. Efficient Computation of Middle Levels Gray Codes |
|
| 16:45-16:55 | BREAK | ||
| Session5A: Geometric Approximation Algorithms. SC: Anastasios Sidiropoulos | Session5B: Scheduling and Packing. SC: Christoph Durr | 16:55-17:20 | Sariel Har-Peled and Kent Quanrud. Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs |
Spyros Angelopoulos, Giorgio Lucarelli and Kim Thang Nguyen. Primal-dual and Dual-Fitting Analysis of Online Scheduling Algorithms for Generalized Flow Time Problems |
| 17:20-17:45 | Helmut Alt, Mark de Berg and Christian Knauer. Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons |
Davaatseren Baatar, Mohan Krishnamoorthy and Andreas Ernst. A Triplet-Based Branch-and-Bound Algorithm for the Shift Mininisation Personnel Task Scheduling Problem |
|
| 17:45-18:10 | Michael Etscheid and Heiko Röglin. Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem |
Yossi Azar and Oren Gilon. Buffer Management for Packets with Processing Times |
|
| 18:10-18:35 | Nabil Mustafa, Saurabh Ray and Norbert Bus. Geometric Hitting Sets for Disks: Theory and Practice |
Leah Epstein and Elena Kleiman. Selfish Vector Packing |
|
| 18:35-18:40 | Short BREAK | ||
| 18:40-20:00 | ESA Business Meeting | ||
| 20:00 | Welcome Reception | ||
Tuesday, 15 September 2015
| ESA 1 | ESA 2 | ALGOCLOUD | |
| 08:30 | Registration | ||
| 09:00-09:45 |
Plenary Talk 2:
Rasmus Pagh
(IT University of Copenhagen, DK) Correlated Locality-Sensitive Hashing SC: Irene Finocchi |
||
| 09:45-10:00 | BREAK | ||
| Session6A: Spanners and Connectivity. SC: Cynthia Phillips | Session6B: Sorting and Searching. SC: Riko Jacob | Session6C: Software Tools and Distributed Architectures for Cloud-based Data Management I. SC: Anastasios Gounaris | |
| 10:00-10:25 | Loukas Georgiadis, Giuseppe F. Italiano, Charis Papadopoulos and Nikos Parotsidis. Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs |
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma, Kurt Mehlhorn and Thatchaphol Saranurak. Self-Adjusting Binary Search Trees: What Makes Them Tick? |
Georgia Koloniari and Evaggelia Pitoura. Transaction Management for Cloud-Based Graph Databases |
| 10:25-10:50 | Kyle Genova and David Williamson. An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem |
Peyman Afshani and Nodari Sitchinava. Sorting and Permuting without Bank Conflicts on GPUs |
Nikolaos Nodarakis, Spyros Sioutas, Panagiotis Gerolymatos, Athanasios Tsakalidis and Giannis Tzimas. Convex Polygon Planar Range Queries on the Cloud: Grid vs Angle-based Partitioning |
| 10:50-11:15 | Davide Bilò, Fabrizio Grandoni, Luciano Gualà, Stefano Leucci and Guido Proietti. Improved Purely Additive Fault-Tolerant Spanners |
Mathias Bæk Tejs Knudsen and Morten Stöckel. Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence |
Spyros Sioutas, Efrosini Sourla, Kostas Tsichlas and Christos Zaroliagis. ART+: A Fault-tolerant Decentralized Tree Structure with Ultimate Sub-logarithmic Efficiency |
| 11:15-11:40 | Chandra Chekuri, Thapanapong Rukkanchanunt and Chao Xu. On Element-Connectivity Preserving Graph Simplification |
Spyros Sioutas, Efrosini Sourla, Kostas Tsichlas and Christos Zaroliagis. D3-Tree: A Dynamic Deterministic Decentralized Structure |
George Seriatos, George Kousiouris, Andreas Menychtas, Dimosthenis Kyriazis and Dora Varvarigou. Comparison of Database and Workload Types Performance in Cloud Environments |
| 11:40-11:55 | BREAK | ||
| Session7A: Dynamic/Parallel Graph Algorithms. SC: Pino Italiano | Session7B: Fixed Parameter Algorithms. SC: Hans Bodlaender | Session7C: Software Tools and Distributed Architectures for Cloud-based Data Management II. SC: Peter Triantafillou | |
| 11:55-12:20 | Jacob Holm, Eva Rotenberg and Christian Wulff-Nilsen. Faster Fully-Dynamic Minimum Spanning Forest |
Pål Grønås Drange and Michał Pilipczuk. A polynomial kernel for Trivially Perfect Editing |
Athanasios Naskos, Anastasios Gounaris and Spyros Sioutas. Cloud Elasticity: A Survey |
| 12:20-12:45 | Andrew Goldberg, Sagi Hed, Haim Kaplan, Pushmeet Kohli, Robert Tarjan and Renato Werneck. Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search |
Dániel Marx and Michał Pilipczuk. Optimal Parameterized Algorithms for Planar Facility Location Problems using Voronoi Diagrams |
Christos Tselios and George Tsolis. A Survey on Software Tools and Architectures for Deploying Multimedia-aware Cloud Applications |
| 12:45-13:10 | Niklas Baumstark, Guy Blelloch and Julian Shun. Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm |
Hadas Shachnai and Meirav Zehavi. A Multivariate Framework for Weighted FPT Algorithms |
Andreas Kosmatopoulos, Kalliopi Giannakopoulou, Apostolos N.Papadopoulos, Kostas Tsichlas. An Overview of Methods for Handling Evolving Graph Sequences |
| 13:10-14:30 | LUNCH | ||
| Session8A: Graph Algorithms. SC: Francesco Silvestri | Session8B: Optimization with Uncertainty. SC: Monaldo Mastrolilli | ||
| 14:30-14:55 | Daniel Graf. How to Sort by Walking on a Tree |
Oliver Göbel, Thomas Kesselheim and Andreas Tönnis. Online Appointment Scheduling in the Random Order Model |
Paper Title
|
| 14:55-15:20 | Ulrik Brandes, Michael Hamann, Ben Strasser and Dorothea Wagner. Fast Quasi-Threshold Editing |
Nicole Megow, Julie Meißner and Martin Skutella. Randomization Helps Computing a Minimum Spanning Tree under Uncertainty |
|
| 15:20-15:45 | Michele Borassi, David Coudert, Pierluigi Crescenzi and Andrea Marino. On Computing the Hyperbolicity of Real-World Graphs |
Yuval Emek, Tobias Langner and Roger Wattenhofer. The Price of Matching with Metric Preferences |
|
| 15:45-16:00 | BREAK | ||
| Session9A: Algorithms for Matching Problems. SC: Jochen Koenemann | Session9B: Hardness of Approximation. SC: Nikhil Bansal | ||
| 16:00-16:25 | Ashish Chiplunkar, Sumedh Tirodkar and Sundar Vishwanathan. On Randomized Algorithms for Matching in the Online Preemptive Model |
Sreyash Kenkre, Vinayaka Pandit, Manish Purohit and Rishi Saket. On the Approximability of Digraph Ordering |
|
| 16:25-16:50 | Jara Uitto and Roger Wattenhofer. Ignorant vs. Anonymous Recommendations |
Abbas Bazzi and Ashkan Norouzi-Fard. Towards Tight Lower Bounds for Scheduling Problems |
|
| 16:50-17:15 | Marek Adamczyk, Fabrizio Grandoni and Joydeep Mukherjee. Improved Approximation Algorithms for Stochastic Matching |
Adam Kurpisz, Monaldo Mastrolilli and Samuli Leppänen. A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem |
|
| 17:15-17:30 | BREAK | ||
| Session10A: Combinatorial Geometry. SC: Anastasios Sidiropoulos | Session10B: Approximation Algorithms. SC: Moran Feldman | ||
| 17:30-17:55 | Micha Sharir, Adam Sheffer and Noam Solomon. Incidences with Curves in R^d |
George Rabanca, Amotz Bar-Noy, David Peleg and Ivo Vigan. Improved Approximation Algorithms for Weighted 2-path Partitions |
|
| 17:55-18:20 | Gill Barequet, Günter Rote and Mira Shalah. Lambda > 4 |
Anna Großwendt and Heiko Röglin. Improved Analysis of Complete-Linkage Clustering |
|
| 18:20-18:45 | Arijit Ghosh, Jean-Daniel Boissonnat and Ramsay Dyer. A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations |
Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Jochen Koenemann, Hamid Mahini, David Malec and Laura Sanita. Approximate Deadline-Scheduling with Precedence Constraints |
19:00 | Social Event |
| 20:30 | Dinner | ||
Wednesday, 16 September 2015
| ESA 1 | ESA 2 | IPEC | ||
| 08:30 | Registration | |||
| 09:00-09:45 |
Plenary Talk 3:
Dimitrios Thilikos
(University of Athens, GR & CNRS, LIRMM, FR) Bidimensionality and Parameterized Algorithms SC: Jan Arne Telle |
|||
| 09:45-10:00 | BREAK | |||
| Session11A: Approximation Algorithms. SC: Jochen Koenemann | Session11B: Planar Graphs. SC: Parinya Chalermsook | Session11C: Kernels I. SC: Michael Fellows | ||
| 10:00-10:25 | Mohammadtaghi Hajiaghayi, Guy Kortsarz, Robert MacDavid, Manish Purohit and Kanthi Sarpatwar. Approximation Algorithms for Connected Maximum Cut and Related Problems |
Michael Bekos, Till Bruckdorfer, Michael Kaufmann and Chrysanthi Raftopoulou. 1-Planar Graphs have Constant Book Thickness |
Eduard Eiben, Robert Ganian and Stefan Szeider. Meta-Kernelization using Well-Structured Modulators |
|
| 10:25-10:50 | Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Joachim Spoerhase, Aravind Srinivasan and Khoa Trinh. An Improved Approximation Algorithm for Knapsack Median using Sparsification |
Xin He and Dayu He. Monotone Drawings of 3-Connected Plane Graphs |
Mamadou Kanté, Eun Jung Kim, O-Joung Kwon and Christophe Paul. An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth One Vertex Deletion |
|
| 10:50-11:15 | Moran Feldman. Maximizing Symmetric Submodular Functions |
Glencora Borradaile, Amir Nayyeri and Farzad Zafarani. Towards Shortest Vertex-Disjoint Paths in Undirected Planar Graphs |
Danny Hermelin, Moshe Kaspi, Christian Komusiewicz and Barak Navon. Parameterized Complexity of Critical Node Cuts |
|
| 11:15-11:30 | BREAK | |||
| Session12A: Output Sensitive Algorithms. SC: Irene Finocchi | Session12B: Routing Protocols. SC: Parinya Chalermsook | Session12C: Kernels II. SC: Dimitrios Thilikos | ||
| 11:30-11:55 | Riko Jacob and Morten Stöckel. Fast Output-Sensitive Matrix Multiplication |
Colin White. Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms |
Ondrej Suchy. Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices |
|
| 11:55-12:20 | Rasmus Pagh, Ninh Pham, Francesco Silvestri and Morten Stöckel. I/O-Efficient Similarity Join |
Jie Gao and Mayank Goswami. Medial Axis Based Routing has Constant Load Balancing Factor |
Bart M. P. Jansen and Astrid Pieterse. Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT |
|
| 12:20-12:45 | Fritz
Bökler and Petra Mutzel. Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems |
Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Ljubomir Perkovic and André van Renssen. Upper and Lower Bounds for Online Routing on Delaunay Triangulations |
Stefan Kratsch and Manuel Sorge. On Kernelization and Approximation for the Vector Connectivity Problem |
|
| 12:45-14:00 | LUNCH | |||
| Session13A: Treewidth. SC: Virginia V. Williams | Session13B: Geometry. SC: Francesco Silvestri | Session13C: FPT Algorithms I. SC: Stefan Szeider | ||
| 14:00-14:25 | Bart M. P. Jansen and Stefan Kratsch. A structural approach to kernels for ILPs: Treewidth and Total Unimodularity |
Iffat Chowdhury and Matt Gibson. A Characterization of Consistent Digital Line Segments in Two Dimensions |
Petr Golovach, Clément Requileé and Dimitrios Thilikos. Variants of Plane Diameter Completion |
|
| 14:25-14:50 | Kenta Kitsunai, Yasuaki Kobayashi and Hisao Tamaki. On the Pathwidth of Almost Semicomplete Digraphs |
Matt Gibson, Erik Krohn and Qing Wang. A Characterization of Visibility Graphs for Pseudo-Polygons |
Archontia Giannopoulou, George Mertzios and Rolf Niedermeier. Polynomial Fixed-Parameter Algorithms: A Case Study for Longest Path on Interval Graphs |
|
| 14:50-15:15 | Yoichi Iwata and Yuichi Yoshida. On the Equivalence among Problems of Bounded Width |
Dan Halperin, Michael Kerber and Doron Shaharabani. The Offset Filtration of Convex Objects |
Eun Jung Kim, Christophe Paul, Ignasi Sau and Dimitrios Thilikos. Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism |
|
| 15:15-15:30 | BREAK | |||
| ESA 2015 Best Paper Awards SC: Nikhil Bansal and Irene Finocchi |
||||
| 15:30-15:55 |
ESA 2015 Best Paper Award Christina Boucher, Christine Lo and Daniel Lokshtanov. Consensus Patterns (Probably) has no EPTAS |
|||
| 15:55-16:20 |
ESA 2015 Best Student Paper Award 1 Meirav Zehavi. Mixing Color Coding-Related Techniques |
|||
| 16:20-16:45 |
ESA 2015 Best Student Paper Award 2 Sascha Witt. Trip-Based Public Transit Routing |
|||
| 16:45-17:00 | BREAK | |||
|
ALGO 2015 Special Event Honoring Paul Spirakis for his Contributions to Computer Science
SC: Christos Zaroliagis |
||||
| 17:00-17:15 | Opening Addresses | |||
| 17:15-17:35 | Christos Zaroliagis. A Glimpse at Paul Spirakis | |||
| 17:35-18:05 | Keynote Talk 1:
Shlomi Dolev (Ben-Gurion University, IL) Communication-less Secure-Multiparty-Computation |
|||
| 18:05-18:35 | Keynote Talk 2: Burkhard Monien (University of Paderborn, DE) The Complexity of Equilibria for Risk-Modeling Valuations |
|||
| 18:35-19:05 | Keynote Talk 3:
Kurt Mehlhorn (Max Planck Institute for Informatics, DE) Computing Equilibrium Prices in Linear Arrow-Debreu Markets | |||
| 19:05-19:30 | Epilogue | |||
| 19:30 | Cocktail | |||
Thursday, 17 September 2015
| IPEC | WAOA | ALGOSENSORS | ATMOS | MASSIVE | ||
| 08:30 | Registration | |||||
| 09:00-09:45 |
Plenary Talk 4:
Ralf Borndoerfer
(Zuse-Institute Berlin, DE) Hypergraphs in Traffic Optimization SC: Marie Schmidt |
|||||
| 09:45-10:00 | BREAK | |||||
| Session14A: FPT Algorithms II. SC: Hans Bodlaender | Session14B: Approximation Algorithms for Network Design. SC: Martin Skutella | Session14D: Routing and Tour Planning. SC: Pino Italiano | Session14E: Dimensionality Reduction and Streaming. SC: Nodari Sitchinava | |||
| 10:00-10:25 | Jannis Bulian and Anuj Dawar. Fixed-Parameter Tractable Distances to Sparse Graph Classes |
Bodo Manthey and Marten Waanders. Approximation Algorithms for k-Connected Graph Factors |
Simeon Andreev, Julian Dibbelt, Martin Nöllenburg, Thomas Pajor and Dorothea Wagner. Towards Realistic Pedestrian Route Planning |
Ioannis Emiris and Ioannis Psarros. Poor Man's Dimension Reduction and High-dimensional Approximate Nearest Neighbor |
||
| 10:25-10:50 | Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan and Saket Saurabh. Quick but Odd Growth of Cacti |
Fabrizio Grandoni, Salvatore Ingala and Sumedha Uniyal. Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows |
Jan Hrncir, Pavol Zilecky, Qing Song and Michal Jakob. Speedups for Multi-Criteria Urban Bicycle Routing |
Kasper Green Larsen, Jelani Nelson. The Johnson-Lindenstrauss Lemma is Optimal for Linear Dimensionality Reduction |
||
| 10:50-11:15 | Hanna Sumita, Naonori Kakimura and Kazuhisa Makino. Parameterized Complexity of Sparse Linear Complementarity Problems |
Katarzyna Paluch. Maximum ATSP with Weights Zero and One via Half-Edges |
Sören Merting, Christian Schwan and Martin Strehler. Routing of Electric Vehicles: Constrained Shortest Path Problems with Resource Recovering Nodes |
Kasper Green Larsen, Jelani Nelson and Huy L. Nguyen. Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms |
||
| 11:15-11:40 | Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil and Somnath Sikdar. Fast Biclustering by Dual Parameterization |
Eun Jung Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau and Dimitrios Thilikos. An FPT 2-Approximation for Tree-Cut Decomposition |
Niklas Paulsen, Florian Diedrich and Klaus Jansen. Heuristic Approaches to Minimize Tour Duration for the TSP with Multiple Time Windows |
Benjamin Sach, Søren Vind and Markus Jalsenius. Compressed Pattern Matching in the Annotated Streaming Mode |
||
| 11:40-11:55 | BREAK | |||||
| Session15A: Kernels III. SC: Stefan Kratsch | Session15B: Online Algorithms. SC: Martin Skutella | Session15D: Routing in rail and road networks. SC: Dorothea Wagner | Session15E: Massive Terrain Data. SC: Peyman Afshani | |||
| 11:55-12:20 | Eun Jung Kim and O-Joung Kwon. A Polynomial Kernel for Block Graph Deletion |
Nikhil Bansal, Marek Elias, Lukasz Jez, Grigorios Koumoutsos and Kirk
Pruhs. Tight bounds for Double Coverage Against Weak Adversaries |
Tadao Takaoka. Passenger Routing Algorithm for a Railway Network |
Lars Arge, Mathias Rav, Sarfraz Raza and Morten Revsbæk. I/O-Efficient Event Based Depression Flood Risk |
||
| 12:20-12:45 | Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk and Arkadiusz Socała. Linear Kernels for Outbranching Problems in Sparse Digraphs |
Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski and Anna Zych. Shortest Augmenting Paths for Online Matchings on Trees |
Katerina Bohmova, Matúš Mihalák, Peggy Neubert, Tobias Pröger and Peter Widmayer. Robust Routing in Urban Public Transportation: Evaluating Strategies that Learn From the Past |
Cici Alexander, Lars Arge, Peder Klith Bøcher, Morten Revsbæk, Brody
Sandel, Jens-Christian Svenning, Constantinos Tsirogiannis and Jungwoo
Yang. Computing River Floods Using Massive Terrain Data |
||
| 12:45-13:10 | R.B. Sandeep and Naveen Sivadasan. Parameterized lower bound and improved kernel for Diamond-free Edge Deletion |
Shun Fukuda, Akiyoshi Shioura and Takeshi Tokuyama. Nonlinear Buyback Problem with Discrete Concave Valuation Functions |
Sandro Montanari and Matúš Mihalák. Bi-directional Search for Robust Routes in Time-dependent Bi-criteria Road Networks |
Mark De Berg, Constantinos Tsirogiannis and Bryan T. Wilkinson. Fast Computation of Categorical Richness on Raster Data Sets and Related Problems |
||
| 13:10-14:30 | LUNCH | |||||
| 14:30-15:15 |
Plenary Talk 5:
Virginia Vassilevska Williams
(Stanford University, USA) The Strong Exponential Time Hypothesis and Hardness for Easy Problems SC: Thore Husfeldt |
|||||
| 15:15-15:30 | BREAK | |||||
| Session16A: Exponential-Time Algorithms. SC: Thore Husfeldt | Session16B: Approximation Algorithms on Graphs. SC: Martin Skutella | Session16C: Exponential-Time Algorithms. SC: Mark de Berg | Session16D: Railway optimization problems. SC: Marie Schmidt | Session16E: Parallel and External Memory Algorithms. SC: Pino Italiano | ||
| 15:30-15:55 | Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki and Junichi Teruyama. Improved Exact Algorithms for Mildly Sparse Instances of Max SAT |
Eleni C. Akrida, Leszek Gasieniec, George Mertzios and Paul Spirakis. On Temporally Connected Graphs of Small Cost |
Ahmad Biniaz, Evangelos Kranakis, Anil Maheshwari and Michiel Smid. Plane and Planarity Thresholds for Random Geometric Graphs |
Gabriel Gutiérrez-Jarpa, Gilbert Laporte, Vladimir Marianov and Luigi Moccia. A Mixed Integer Linear Program for the Rapid Transit Network Design Problem with Static Modal Competition |
Foto Afrati, Nikos Stasinopoulos, Jeffrey Ullman and Angelos
Vasilakopoulos. Handling Skew in Multiway Joins in MapReduce |
|
| 15:55-16:20 | Navid Talebanfard and Ilario Bonacina. Strong ETH and Resolution via Games and the Multiplicity of Strategies |
Shay Mozes and Eyal Skop. Efficient Vertex-Label Distance Oracles for Planar Graphs |
Joffroy Beauquier, Blanchard Peva, Janna Burman and Shay Kutten. The Weakest Oracle for Symmetric Consensus in Population Protocols |
Frank Fischer. Ordering Constraints in Time Expanded Networks for Train Timetabling Problems |
Michael A. Bender, Samuel McCauley, Andrew McGregor, Shikha Singh and
Hoa T. Vu. Run Generation Revisited: What Goes Up May or May Not Come Down |
|
| 16:20-16:45 | Petr Golovach, Pinar Heggernes and Dieter Kratsch. Enumerating Minimal Connected Dominating Sets in Graphs of Bounded Chordality |
Yishay Mansour, Boaz Patt-Shamir and Shai Vardi. Constant-Time Local Computation Algorithms |
Eleni C. Akrida and Paul Spirakis. On Verifying and Maintaining Connectivity of Interval Temporal Networks |
Markus Reuther and Ralf Borndörfer. Regional Search for the Resource Constrained Assignment Problem |
Riko Jacob, Tobias Lieber and Nodari Sitchinava. On the Complexity of List Ranking in the Parallel External Memory Model |
|
| 16:45-17:00 | BREAK | |||||
| Session17A: Exponential-Time and FPT Algorithms SC: Daniel Lokshtanov | Session17C. SC: Leszek Gasieniec | Session17D: ATMOS Best Paper Award. SC: Christos Zaroliagis | ||||
| 17:00-17:25 | Jisu Jeong, Sigve Hortemo Sæther and Jan Arne Telle. MaximumMatching Width: New Characterizations and a Fast Algorithm for Dominating Set |
Samir Elouasbi and Andrzej Pelc. Deterministic Rendezvous with Detection using Beeps |
René Van Bevern, Christian Komusiewicz and Manuel Sorge. Approximation algorithms for mixed, windy, and capacitated arc routing problems |
|||
| 17:25-17:50 | Chiel ten Brinke, Frank van Houten and Hans Bodlaender. Practical Algorithms for Linear Boolean-width |
Serafino Cicerone, Gabriele Di Stefano and Alfredo Navarra. Gathering of Robots on Meeting-Points |
ATMOS Business Meeting | |||
| 17:50-18:15 | Fahad Panolan, Geevarghese Philip and Saket Saurabh. b-Chromatic Number: beyond NP-hardness |
Shantanu Das, Flaminia L. Luccio and Euripides Markou. Mobile Agents Rendezvous in Spite of a Malicious Agent |
||||
| 18:15-18:20 | Short BREAK | |||||
| 18:20-19:30 | IPEC Business Meeting | |||||
Friday, 18 September 2015
| IPEC | WAOA | ALGOSENSORS | |
| 08:30 | Registration | ||
| 09:00-09:45 |
Plenary Talk 6:
Jochen Koenemann
(University of Waterloo, CA) Recent News for an Old Steiner Tree Formulation SC: Martin Skutella | ||
| 09:45-10:00 | BREAK | ||
| Session18A: Parameterized Complexity and Logic SC: Iyad Kanj | Session18B: Approximation Algorithms for Covering and Packing. SC: Martin Skutella | Session18C. SC: Jean-Lou Carufel | |
| 10:00-10:25 | Lars Jaffke and Hans L. Bodlaender. Definability Equals Recognizability for k-outerplanar Graphs |
Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau and Dimitrios
Thilikos. An O(log OPT)-approximation for Covering/Packing Minor Models of θ_r |
Gui Citovsky, Jie Gao, Joseph Mitchell and Jiemin Zeng. Exact and Approximation Algorithms for Data Mule Scheduling in a Sensor Network |
| 10:25-10:50 | Tom van der Zanden. Parameterized Complexity of Graph Constraint Logic |
Corinna Gottschalk and Britta Peis. Submodular Function Maximization on the Bounded Integer Lattice |
Evangelos Bampas, Jurek Czyzowicz, David Ilcinkas and Ralf Klasing. Beachcombing on Strips and Islands |
| 10:50-11:15 | Holger Dell, Eunjung Kim, Michael Lampis, Valia Mitsou and Tobias Mömke. Complexity and Approximability for Parameterized CSPs |
Sándor Fekete, Kan Huang, Joseph Mitchell, Ojas Parekh and Cynthia
Phillips. Geometric Hitting Set for Segments of Few Orientations |
Evangelos Kranakis, Danny Krizanc, Flaminia Luccio and Brett Smith. Maintaining Intruder Detection Capability in a Rectangular Domain with Sensors |
| 11:15-11:40 | Hubie Chen. Parameter Compilation |
Marin Bougeret, Stephane Bessy, Daniel Gonçalves and Christophe Paul. OnIindependent Set on B1-EPG Graphs |
Robert Benkoczi, Zachary Friggstad, Daya Gaur and Mark Thom. Minimizing Total Sensor Movement for Barrier Coverage by Non-Uniform Sensors on a Line |
| 11:40-11:55 | BREAK | ||
| Session19A: FPT Algorithms for Scheduling. SC: Frances Rosamond | Session19B: Online Algorithms and Scheduling. SC: Martin Skutella | Session19C. SC: Cristina Pinotti | |
| 11:55-12:20 | Florian Barbero, Gregory Gutin, Mark Jones and Bin Sheng. Parameterized and Approximation Algorithms for the Load Coloring Problem |
Jan Reineke and Alejandro Salinger. On the Smoothness of Paging Algorithms |
Gokarna Sharma, Costas Busch and Supratik Mukhopadhyay. Mutual Visibility with Optimal Colors |
| 12:20-12:45 | Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay, Nimrod Talmon and Gerhard Woeginger. Scheduling Two Competing Agents When One Agent has Significantly Fewer Jobs |
Roozbeh Ebrahimi, Samuel McCauley and Benjamin Moseley. Scheduling Parallel Jobs Online with Convex and Concave Parallelizability |
Stanley Fung. Maximizing Throughput in Energy-Harvesting Sensor Nodes |
| 12:45-13:10 | Jason Crampton, Gregory Gutin, Andrei Gagarin and Mark Jones. On the Workflow Satisfiability Problem with Class-Independent Constraints |
Veerle Timmermans and Tjark Vredeveld. Scheduling with State-Dependent Machine Speed |
Oscar Garcia-Morchon, Ronald Rietman, Sahil Sharma, Ludo Tolhuizen and
Jose Luis Torre Arce. A Comprehensive and Lightweight Security Architecture to Secure the IoT throughout the Lifecycle of a Device Based on HIMMO |
| 13:10-14:30 | LUNCH | ||
| 14:30-15:15 |
Plenary Talk 7:
Thomas Kesselheim (Max Planck Institute for Informatics, DE) Online Packing Beyond the Worst Case SC: Roger Wattenhofer |
||
| 15:15-15:30 | BREAK | ||
| Session20A: FPT Algorithms III. SC: Gregory Gutin | Session20C. SC: Flaminia Luccio | ||
| 15:30-15:55 | Max Bannach, Christoph Stockhusen and Till Tantau. Fast Parallel Fixed-Parameter Algorithms via Color Coding |
Magnus M. Halldorsson and Tigran Tonoyan. Limitations of Current Wireless Scheduling Algorithms |
|
| 15:55-16:20 | Edouard Bonnet and Florian Sikora. The Graph Motif Problem Parameterized by the Structure of the Input Graph |
Amitabha Bagchi, Francesco Betti Sorbelli, Cristina Maria Pinotti and
Vinay Ribeiro. Connectivity of a Dense Mesh of Randomly Oriented Directional Antennas under a Realistic Fading Model |
|
| 16:20-16:45 | Diptapriyo Majumdar, Venkatesh Raman and Saket Saurabh. Kernels for Structural Parameterizations of Vertex Cover - Case of Small Degree Modulators |
Rajiv Gandhi, Magnus M. Halldorsson, Christian Konrad, Guy Kortsarz and
Hoon Oh. Radio Aggregation Scheduling |
|
| 16:45-16:50 | ALGO 2015 - Epilogue | ||
