Invited plenary talks
ESA
Marc van Kreveld (Utrecht University, the Netherlands)
Trajectory Data Analysis
Abstract: Tracking devices have become more and more widespread, which has led to large collections of movement data. The moving objects can be vehicles, animals, sports players, and people in general, and the collected data consists of trajectories: sequences of points with a time stamp. In geographic information science the analysis of these collections has become a highly important topic of research. Clustering, similarity analysis, prediction, and flock detection are examples of the analysis of trajectories. All of these analyses requires efficient geometric algorithms.
After giving an introduction into trajectory analysis we will discuss several algorithms that operate on trajectories, including trajectory segmentation and grouping analysis.
Thomas Rothvoß (University of Washington, Seattle, USA)
Lower bounds on the size of linear programs
Abstract: One of most powerful problems that admits polynomial time algorithms is linear programming. Just in the last few years we have been able to better understand its power and its limitations. In this talk, we will give a survey on recent results which show that NP-hard problems like TSP cannot be solved with a single linear program and even the matching polytope cannot be represented by a polynomial size LP.
ALGOSENSORS
Phillip Gibbons (Intel Labs Pittsburgh)
Algorithmic Challenges in M2M
Abstract: The Internet of Things promises a world of billions to trillions of smart objects/devices, communicating machine-to-machine (M2M) and providing us valuable information and services. This talk highlights our recent work addressing several key algorithmic challenges that arise in this setting. Specifically, we focus on problems arising in aggregation, similarity search, and machine learning on M2M’s massively distributed network. After surveying these results, we present in greater detail upper and lower bounds demonstrating the cost of fault tolerance in such networks. These bounds show that across a communication-time trade-off curve, aggregation algorithms that tolerate crash failures incur an exponential cost in communication relative to non-fault-tolerant algorithms.
ATMOS
Renato Werneck (Microsoft Research, USA)
Building a Real-World Routing Engine
Abstract: Computing driving directions in road networks is a fundamental problem with numerous applications. Although standard graph-search algorithms can solve it in almost linear time, this is not fast enough to enable interactive queries on continental road networks. Modern algorithms thus work in two stages: an offline preprocessing routine first computes some auxiliary data, which is then used to answer exact queries interactively. In a true success story, the past decade has seen the development of a diverse set of techniques providing various trade-offs between preprocessing effort, query time, space usage, extensibility, and simplicity. I will survey these techniques and discuss how they address the requirements of real-world routing engines, with emphasis on the the algorithm behind the system currently in use by Microsoft's Bing Maps.
IPEC
Hans Bodlaender (Utrecht University, the Netherlands)
Lowerbounds for Kernelization
Abstract: Kernelization is the process of transforming the input of a combinatorial problem to an equivalent input whose size is bounded by a function of the parameter; the analysis of kernelization tells what we can achieve with polynomial time preprocessing for combinatorial problems, and is a recent active field in algorithm research. In this talk, a survey is given of a number of recent techniques to show (under complexity theoretic assumptions) lower bounds for the size of kernels. In particular, it is discussed how the notion of compositionality can show that certain (parameterized) problems do not have kernels of polynomial size.
WABI
Hélène Touzet (University of Lille, France)
Some algorithms for RNA analysis
Abstract: Ribonucleic acid (RNA) is one of the three major macromolecules, along with DNA and proteins, that are essential for all forms of life. RNAs are now recognized to play an active role in cells by catalyzing biological reactions and controlling gene expression, and have attracted a lot of interest in molecular biology and in computational biology recently.
Like DNA, RNA is made up of a chain of nucleotides. But a main difference is that RNAs are single stranded and fold into a three-dimensional structure. Due to this spatial structure, RNAs are modeled by complex combinatorial models, such as ordered trees or graphs. In this talk, I will present several basic problems raised by the analysis of RNA (alignment, structure inference) and introduce a universal framework to design dynamic programming algorithms that is especially well-suited for RNA analysis.
WAOA
Aleksander Mądry (EPFL, Switzerland)
From Graphs to Matrices, and Back: Bridging the Combinatorial and the Continuous
Abstract: Graphs are ubiquitous in all modern sciences. This motivates a need for algorithmic tools that are capable of analyzing and computing on graphs in an efficient manner. A need that is even more pressing now that the graphs we are dealing with tend to be massive, rendering traditional methods no longer adequate.
In this talk, I will discuss a recent progress on the maximum flow problem and use it as an illustration of a broader emerging theme in graph algorithms that employs optimization methods as an algorithmic bridge between our combinatorial and spectral understanding of graphs.
I will also briefly outline how this line of work brings a new perspective on some of the core continuous optimization primitives — most notably, interior-point methods.
Invited tutorials
IPEC
Stefan Szeider (Vienna University of Technology, Austria)
Backdoors, Satisfiability, and Problems Beyond NP
Abstract: A backdoor is a small set of variables that represents a shortcut through the search space. In this tutorial we will provide a survey of fixed-parameter algorithms and parameterized complexity results for problems related to finding and using backdoors, mainly focusing on the propositional satisfiability problems (SAT) and its counting version (#SAT). In addition we will discuss recent results on using backdoors to break through complexity barriers between higher levels of the Polynomial Hierarchy. We will explain how this approach can be used to extend the power of fixed-parameter algorithms for problems beyond NP and sketch new hardness tools for establishing its limits.
WAOA
Monaldo Mastrolilli (IDSIA, Switzerland)
The Lasserre/Sum-of-Squares Hierarchy: a gentle introduction
Abstract: The Lasserre/Sum-of-Squares hierarchy is a systematic procedure to strengthen LP relaxations by constructing a sequence of increasingly tight formulations. For a wide variety of optimization problems, this approach captures the convex relaxations used in the best available approximation algorithms.
The goal of this tutorial is to introduce the non-expert to this technique by giving the essential intuition behind the definition and key properties. We discuss some simple examples, applications and limitations.
