ALGO 2015
14 -18 September, Patras, Greece

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

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

Paper Title
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
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

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

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

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