German Speakers | Title and Abstract |
Marc Goerigk | Title: A Bicriteria Approach to Robust Optimization |
Abstract: The classic approach in robust optimization is to optimize the solution with respect to the worst case scenario. This pessimistic approach yields solutions that perform best if the worst scenario happens, but also usually perform bad on average. A solution that optimizes the average performance on the other hand lacks in worst-case performance guarantee. In practice it is important to find a good compromise between these two solutions. We propose to deal with this problem by considering it from a bicriteria perspective. The Pareto curve of the bicriteria problem visualizes how costly it is to ensure robustness and helps to choose the solution with the best balance between expected and guaranteed performance. Building upon a theoretical observation on the structure of Pareto solutions for problems with polyhedral feasible sets, we present a column generation approach that requires no direct solution of the computationally expensive worst-case problem. We demonstrate the effectivity of both the proposed algorithm, and the bicriteria perspective in general. | |
Click for .pdf | |
Martin Hoefer | Title: Dynamic Matching under Preferences |
Abstract: This talk surveys our recent work on dynamic aspects of matching problems with preferences. On the one hand, we consider dynamics in variants of stable matching where agents repeatedly deviate to blocking pairs. We present some answers to natural questions for convergence - can convergence to stable matchings can be guaranteed? Are paths to stability short, and can they be found efficiently? On the other hand, we consider dynamic matching scenarios, where agents arrive and depart iteratively over time. The goal here is to maintain in each round a matching that is (to some extent) preferred by the agents using a small amortized number changes over time. We consider approximate versions of stable and popular matchings and quantify the tension between approximation and number of changes. | |
Click for .pdf | |
Lasse Kliemann | Title: Algorithms for Graph Streaming |
Abstract: A brief introduction to the graph streaming model, which is used
to model situations where the input graph is too large for random
access. We look at how to solve some fundamental optimization problems
in this model. Then we spend some time with the graph matching problem
and a family of combinatorial streaming algorithms to find approximate
solutions. We conclude with recent experimental results on longest path
heuristics for graph streaming. [Joint work with Sebastian Eggert, Peter Munstermann, Christian Schielke, and Anand Srivastav (all Kiel University)] | |
Click for .pdf | |
Ulrich Meyer | Title: Algorithms for Big Data Research Topics in the Big Data Priority Program SPP1736 |
Abstract: The Senate of the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) has established a new Priority Programme entitled “Algorithms for Big Data” (SPP 1736). The programme will run for six years (two funding periods of 3 years each). In 2014 about 15 projects started. In the first part of my talk I will provide an overview of the the topics covered in these projects. In the second part I will give some more details on my on project in the area of parallel-external graph algorithms. | |
Click for .pdf | |
Rolf Möhring | Title: Coping with Uncertainty in Project Scheduling: New Developments and Applications |
Abstract: Combinatorial optimizers have recently become more aware about the
influence of uncertainty and randomness in solving combinatorial
optimization problems. Deterministic models for project scheduling and
control suffer from the fact that they assume complete information and
neglect random influences that occur during project execution. A
typical consequence is the underestimation of the expected project
duration and cost frequently observed in practice.
To cope with these phenomena, we consider scheduling models with random processing times. Scheduling is then done by policies which consist of an an online process of decisions that are based on the observed past and the a priori knowledge of the distribution of processing times. I will first report on recent results for this model, including risk measures for the makespan distribution and approximation algorithms for policies in machine scheduling. I will then then continue with an application to turnaround scheduling. This concerns large-scale maintenance in industrial plants and requires the shutdown of entire production units for disassembly, comprehensive inspection and renewal. It is an important process that causes high out-of-service cost. Therefore a good schedule for a shutdown and and an analysis of possible associated risks are crucial for the manufacturer. We have developed algorithms for this task that work in two phases. The first phase supports the manager in finding a good makespan for the shutdown. It computes an approximate project time cost tradeoff curve together with a stochastic evaluation of the risk for meeting a particular makespan t. Our risk measures are the expected tardiness at time t and the probability of completing the shutdown within time t. In the second, detailed planning phase, we solve the actual scheduling optimization problem for the makespan chosen in the first phase heuristically and compute a detailed schedule that respects all side constraints. Again, we complement this by computing upper bounds for the same two risk measures, but now for the detailed schedule. | |
Click for .pdf | |
Günter Rudolph | Title: Algorithmic Aspects in Finding Evenly Spaced Approximations of Pareto Frontiers |
Abstract: Evenly spaced approximations of Pareto frontiers are required in the context of online control problems. We shall introduce the base algorithm to find such an approximation for bicriteria problems with continuous decision space and some theoretical results regarding the optimality of the approximations obtained in this manner. Subsequently, we describe a sequence of algorithmic modifications of the base algorithm that do not affect its solution quality but significantly improve its runtime behavior. These improvments cleared the way for an extension of the approach to problems with more than two objectives. | |
Click for .pdf | |
Anita Schöbel | Title: Optimization in public transportation |
Abstract: In this talk, an overview on line planning, timetabling, and delay management
is provided. Given an existing public transportation network with its stops (or stations) and
direct connections, the first step in the strategic planning of a transport system is to define
lines and their frequencies. If the lines have been found, the next step is to design a timetable.
There are two different
models: Periodic timetables which are repeated on e.g. an hourly basis and aperiodic timetables.
The usual aim is to minimize the traveling time for the passengers.
Coming to the operational phase, we deal with the question of how to react
in case of delays. This concerns the decision if a punctual bus or train should wait for a
delayed feeder bus or train or if it
should better depart on time. In railway traffic also the limited capacity of the tracks has to
be taken into account. In the second part of the talk we discuss recent research directions aiming at making the approaches work in practice. A challenging problem concerns the route choice of the passengers. In many papers it is assumed that it is already known how the passengers travel, i.e. a passenger's weight is assumed to be known for every edge or activity in the system. This is an unrealistic assumption since the route choice of the passengers depends on the lines, the timetable, and on the delay management strategy. We will discuss how the passengers' decisions may be integrated into the optimization process. Another issue is robustness. It is not helpful to have an exact optimal solution that might get meaningless if a small disturbance occurs. Hence, the aim should be to have a robust transportation system which performs well even if the scenario or the input data changes. We exemplary illustrate different concepts on how to develop robust timetables. The third research question concerns an integration of the subsequent planning steps. First approaches for computing integrated solutions will be shown. | |
Click for .pdf | |
Christian Schulz | Title:Parallel Graph Partitioning for Complex Networks |
Abstract: Processing large complex networks like social networks or web graphs has recently attracted considerable interest. To do this in parallel, we need to partition them into pieces of about equal size. Unfortunately, previous parallel graph partitioners originally developed for more regular mesh-like networks do not work well for these networks. This paper addresses this problem by parallelizing and adapting the label propagation technique originally developed for graph clustering. By introducing size constraints, label propagation becomes applicable for both the coarsening and the refinement phase of multilevel graph partitioning. We obtain very high quality by applying a highly parallel evolutionary algorithm to the coarsest graph. The resulting system is both more scalable and achieves higher quality than state-of-the-art systems like ParMetis or PT-Scotch. For large complex networks the performance differences are very big. As an example, our algorithm partitions a web graph with 3.3 G edges in 16 seconds using 512 cores of a high-performance cluster while producing a high quality partition -- none of the competing systems can handle this graph on our system. | |
Click for .pdf | |
Anand Srivastav | Title: Derandomized Algorithms for Discrete Packing and Covering Problems - Engineering and Analysis - |
Abstract: In this talk I will give a short introduction to the different derandomization methods,
like the method of conditional probabilities and the method of limited independence.
The talk focuses on open problems regarding the derandomization of hybride algorithms,
consiting of different subroutines such as randomized rounding and greedy algorithms
for packing/macthing and set covering problems in hypergraphs. This is a very typical situation
in the design of randomized algorithms.
The derandomization of such algorithms
is challenging as we have to care about dependencies among the random variables.
Invoking martingale based concentration bounds, like the Azuma inequality,
the analysis of the randomized algorithm can be carried out. Derandomization is now concerned to derive a algorithmic or derandomized form of the Azuma inequality, and to state a deterministic polynomial-time algorithm achieving almost the same performamce guarantee as the randomized counterpart. At the end of the talk, I shall report on the first steps towards algorithm engineering for derandomization. | |
Click for .pdf | |
Dorothea Wagner | Title:Algorithm Engineering for Route Planning in Transportation |
Abstract:
Nowadays, route planning systems belong to the most frequently used
information systems. The algorithmic core problem of such systems,
is the classical shortest paths problem that can be solved by Dijkstra's
algorithm which, however, is too slow for practical scenarios. Algorithms for route planning in transportation networks have recently undergone a rapid development, leading to methods that are up to several million times faster than Dijkstra’s algorithm. For example, for continent-sized road networks, newly-developed algorithms can answer queries in a few hundred nanoseconds; others can incorporate current traffic information in under a second on a commodity server; and many new applications can now be dealt with efficiently. Accordingly, route planning has become a showpiece of Algorithm Engineering demonstrating the engineering cycle that consists of design, analysis, implementation and experimental evaluation of practicable algorithms. Rcently, new aspects like multimodal route planning, personalized journey planning with respect to multiple criteria or energy-aware route planning for electric vehicles come up. This talk provides a condensed survey of recent advances in algorithms for route planning in transportation networks. In particular, we will discuss a scenario where schedule-based transportation modes like buses and trains, and unrestricted modes like walking and driving, are combined. | |
Click for .pdf | |
Andreas Wiese | Title: Approximation Schemes for Maximum Weight Independent Set of Geometric Objects |
Abstract: In the Maximum Weight Independent Set of Rectangles (MWISR) problem we
are given a set of n axis-parallel rectangles in the 2D-plane, and the
goal is to select a maximum
weight subset of pairwise non-overlapping rectangles. Due to many
applications, e.g., in data mining, map labeling and admission
control, the problem has received a lot of attention by various
research communities. We present the first (1+ε) approximation
algorithm for the MWISR problem with quasi-polynomial running time
2^poly(log n/ε). In contrast, the best known polynomial time
approximation algorithms for the problem achieve superconstant
approximation ratios of O(loglogn) (unweighted case) and
O(logn/loglogn) (weighted case). Key to our result is a new geometric
dynamic program which recursively subdivides the plane into polygons
of bounded complexity. We provide the technical tools that are needed
to analyze its performance. Finally, I will give an overview of recent
follow-up work, in particular a generalization of the above result to
arbitrary polygons. [Joint work with Anna Adamaszek] | |
Contact Author for slides | |
Alexander Wolff | Title: i) An Introduction to and Recent Results in Graph Drawing |
Abstract: We will give a short introduction into Graph Drawing, motivating the field with real-world examples. Then, we will sketch a few general-purpose approaches. Finally, we will discuss current trends and mention some open questions in Graph Drawing. | |
Click for .pdf | |
Title: ii) Box Contact Representations of Graphs | |
Abstract: We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, in which realizing each desired adjacency yields a certain profit. We show that the optimization problem is APX-complete even on bipartite graphs of bounded maximum degree. We present the first constant-factor approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. | |
Click for .pdf |
Indian Speakers | Title and Abstract |
Antar Bandyopadhyay | Title: De-Preferential Attachment Random Graphs |
Abstract: In this talk we will introduce a new model of a growing sequence of random
graphs where a new vertex is less likely to join to an existing vertex with high
1degree and more likely to join to a vertex with low degree. In contrast to the well
studied model of preferential attachment random graphs where higher degree
vertices are preferred, we will call our model de-preferential attachment random
graph model. We will consider two types of de-preferential attachment models,
namely, inverse de-preferential, where the attachment probabilities are inversely
proportional to the degree and linear de-preferential, where the attachment
probabilities are proportional to c−degree, where c > 0 is a constant. We
will give asymptotic degree distribution for both the model and show that the
limiting degree distribution has very thin tail. We will also show that for a fixed
vertex v, the degree grows as √log n for the inverse de-preferential case and as
log n for the linear case. Some of the results will also be generalized when each
new vertex joins to m > 1 existing vertices. [Joint work with Subhabrata Sen, Stanford University] | |
Click for .pdf | |
Ansuman Banerjee | Title: Ranking verification counterexamples: An invariant guided approach |
Abstract: Unit testing and verification constitute an important step in the validation life cycle of large and complex multi-component designs. Many unit validation methods often suffer from the problem of false negatives, when they analyze a component in isolation and look for errors. It often turns out that some of the reported unit failures are infeasible, i.e. the valuations of the component input parameters that trigger the failure scenarios, though feasible on the unit in isolation, cannot occur in practice considering the integrated design, in which the unit-under-test is instantiated. In this work, we consider this problem in the context of a multi-component RTL design, with a set of unit failures reported on a specific unit. We present an automated two-stage failure scenario classification and prioritization strategy that can filter out false negatives and cluster them accordingly. The use of classical AI and program analysis techniques in conjunction with formal verification helps in developing new frameworks for reasoning and deduction, which appear promising for a wide variety of problems. In particular, we discuss the results of using this technique in the context of a few RTL benchmarks. | |
Click for .pdf | |
Arijit Bishnu | Title: Uniformity of point samples in metric spaces using gap ratio |
Abstract: Teramoto et al. (Teramoto et al., Inserting points uniformly at every in-
stance, IEICE Transactions, 89-D(8):2348–2356, 2006) defined a new measure
called the gap ratio that measures the spatial uniformity of a finite point set
sampled from S, a bounded subset of ℜ². We attempt to generalize the definition of this measure over all metric spaces. The generalized definition is
basically a ratio between the covering radius and the packing radius of n points
in the given metric space. A uniform distribution of points would give a thin
covering and a tight packing, i.e., low gap ratio. This gives rise to the question
of sampling points while minimising the gap ratio. We solve optimization related questions about selecting uniform point samples from metric spaces, which
maybe continuous or discrete. While there is no general lower bound for gap
ratio, we show the lower bound when the metric space is a unit square in ℜ²,
a path connected space or a graph. We show that the minimising the gap ratio
is hard when the space is a graph or a path connected space. In fact, we show
that the problem is hard to approximate within a factor of 2 in general, and
within a factor of 3/2 on a graph. We also show that the farthest point insertion
method of Gonzalez provides a general approximation framework for the gap
ratio problem. A (1+ε)-approximation algorithm for a metric space which is a
set of points in a Euclidean space is also proposed. [Joint work with Sameer Desai, Arijit Ghosh, Mayank Goswami and Subhabrata Paul] | |
Click for .pdf | |
Anirban Dasgupta | Title: Estimating Network Parameters |
Abstract: Large networks are ubiquitous, and yet, estimating the key parameters
of large networks is not an easy problem due to various constraints:
either because of their size, or because of the fact that they are not
available in their entirety and can only be accessed through some
restricted interface (e.g. a rate-limited API). In this talk, we
outline sampling based algorithms to estimate a couple of key network
properties e.g. the average degree and the size of a sub-population. [Joint work with Ravi Kumar, Tamas Sarlos and D. Sivakumar] | |
Click for .pdf | |
Supratik Chakraborty | Title: Distribution-aware sampling and weighted model counting for propositional formulas |
Abstract: Given a CNF formula and a weight for each assignment of values to
variables, two natural
problems are weighted model counting and distribution-aware sampling
of satisfying assignments.
Both problems have a wide variety of important applications. Due to
the inherent complexity of
the exact versions of the problems, interest has focused on solving
them approximately. Early
approaches to these problems yielded algorithms that either had strong
theoretical guaranteed
but scaled only to small problems in practice, or scaled to large
problems without providing strong
theoretical guarantees. Recently, Ermon, Gomes, Sabharwal and Selman
presented an algorithm
that tries to bridge these extremes by using most probable explanation
(MPE) oracle and by
exploiting prior knowledge of a factored representation of the weight
distribution. We present
a different approach that works with a black-box oracle for weights of
assignments and requires
only an NP-oracle (in practice, a SAT-solver) to solve both the
counting and sampling problems.
Our approach works under mild assumptions on the distribution of
weights of satisfying
assignments, provides strong theoretical guarantees, and scales to
problems involving several
thousand variables. We also show that the assumptions can be
significantly relaxed while improving
computational efficiency if a factored representation of the weights is known. [Joint work with Kuldeep Meel, Moshe Vardi, Daniel Fremont and Sanjit Seshia, based on our paper in AAAI 2014] | |
Click for .pdf | |
Sandip Das | Title: Geometric center problems |
Abstract: Given a set of points distributed on two dimensional plane, we are looking for placement of facilities on that plane in order to optimize some set of constraints. Distance between two points in the plane may be measured by Euclidean metric. Study of those objective functions in geometric domain is important for generating efficient algorithms for facility location problem. We will discuss some interesting characterizations that produce nice algorithms starting from Megiddo’s linear time solution for 1-center problem and extend our discussion to constrained and dynamic versions of the problem. | |
Click for .pdf | |
Subir Ghosh | Title: Old and new algorithms for guarding polygons |
Abstract: A polygon is said to be guarded by a set of chosen guards if every point of the polygon is visible from some guard of the guard set. In this lecture, we first present O(logn)-approximation algorithms for guarding polygons with or without holes. Then we present a 6-approximation algorithm for guarding a special class of simple polygons. Finally, we present an algorithm for guarding simple polygons using O(logn) colors for a guard set. These algorithms have natural applications in surveillance, landmark-based navigation and wireless networks. | |
Click for .pdf | |
Sasthi C Ghosh | Title: Generalized graph coloring for spectrum efficient frequency assignment in cellular network. |
Abstract: In this talk, we will discuss some efficient techniques for solving the channel
assignment problem (CAP ) in cellular networks. The CAP can be characterized
1by the triplet (X, W, C) where (1) X = {0, 1, 2, · · · n − 1} is the set of n cells,
(2) W = (w_{i}), 0 ≤ i ≤ n − 1, is the demand vector (w i represents the number of
channels required for cell i), and (3) C = (c_{ij}), 0 ≤ i, j ≤ n − 1, is the frequency
separation matrix (c_{ij} represents the minimum frequency separation required
between a call in cell i and a call in cell j). The CAP deals with the problem
of assigning frequency channels to the cells satisfying the frequency separation
constraints while using as small bandwidth as possible. It is straightforward to
see the CAP in the form of a generalized graph coloring problem. Thus the
approaches that we will be discussing can be considered as generalized graph
coloring techniques too. Considering the application scenario, the approaches
are developed based on the fact that fast assignment is of primary importance
though a marginal deviation from the optimality may be tolerated. In the first approach, we map a given CAP P to a modified coalesced CAP P^{′} on a smaller subset of cells of the network, which appreciably reduces the search space. This helps to solve P ′ by applying approximate algorithms very efficiently, reducing the computing time drastically. This solution to P^{′} is then used to solve the given CAP P. In the second approach, the CAP with non-homogeneous demand is first partitioned into a sequence of smaller subproblems, each of which has a homo- geneous demand from a subset of the nodes of the network. Solution to such a subproblem constitutes an assignment phase where multiple homogeneous de- mands are assigned to the nodes corresponding to the subproblem, satisfying all the frequency separation constraints. The whole assignment process for the original network consists of a succession of multiple homogeneous assignments for all the subproblems. In the third approach, we begin with a given ordering of the vertices and apply frequency exhaustive strategy to assign frequencies to them. During the assignment, when frequency of a vertex exceeds the maximum frequency of previously allocated vertices, we apply a forced assignment phase to reduce the so far obtained span. Finally we propose an iterative compression phase to further reduce the span obtained from applying the frequency exhaustive strategy with forced assignment phase. | |
Click for .pdf | |
Sathish Govindarajan | Title: Independent set and hitting sets of geometric objects |
Abstract: Let P be a set of n points in the plane and S be a set of m geometric objects
of same type (ex. squares, disks, rectangles...). The hitting set problem asks
to select a subset of points of P of minimum cardinality such that every object
in S contains at least one of the selected points (the objects in S are “hit”).
The discrete independent set problem asks to select a subset of objects in S of
maximum cardinality such that any points in P is contained in at most one of
the selected objects (the selected objects are “independent”). The algorithmic problem of computing hitting sets and independent sets is NP- hard, even for simple objects like unit squares. In this talk, we will look at approximation algorithms for these problems. We will also consider a combina- torial problem of bounding the hitting set size as a function of the independence number. The combinatorial bounds could be used to design approximation al- gorithms for hitting set and independent set problems. | |
Click for .pdf | |
Arobinda Gupta | Title: Heterogeneous Distributed Algorithms |
Abstract: Traditional distributed algorithms are mostly homogeneous, where a single algorithm runs on the entire system to achieve some task. However, this may be inefficient in systems where different parts of the network may exhibit different characteristics, making some protocols more suitable than others in each part. In this talk, we explore the design of distributed algorithms for a problem where the network is broken up into zones, and (possibly) different algorithms for the problem are run on each zone. We name such algorithms heterogeneous distributed algorithms. We illustrate this approach by considering the design of algorithms for global token passing in a distributed system with the possibility of running different local token passing algorithms in different non-overlapping zones, for some simple topologies. | |
Click for .pdf | |
Krishnendu Mukhopadhyaya | Title: Algorithms for Distributed Swarm Robots |
Abstract: In this talk we focus on a group of robots called 'swarm robots', which function in a distributed fashion. All robots are identical in their configurations and appearances, and independent in their computations and actions. They can sense their surroundings through some devices. Each robot possesses a minimal capability in terms of its storage and communication power. We discuss some coordination problems and their solutions, based on cooperative behavior. An important objective is to identify minimal sets of capabilities to solve certain problems. | |
Click for .pdf | |
Partha Mukhopadhyay | Title: Erdős- Rényi Sequences and Deterministic construction of Expanding Cayley Graphs |
Abstract: Let G be a finite group given as input by its multiplication table. We design a
deterministic polynomial-time algorithm that constructs a directed O(log |G|)
degree Cayley expander for the group G. More precisely, this O(log |G|) degree
Cayley graph has a rapid mixing property that guarantees constant spectral
expansion.
By refining our approach we also give a new deterministic polynomial-time algorithm that computes an O(log |G|) degree undirected Cayley expander for the
group G. This gives a combinatorial derandomization of the Alon-Roichman
randomized construction of an O(log |G|) size expanding generator set for G. [Joint work with V. Arvind and Prajakta Nimbhorkar] | |
Click for .pdf | |
Subhas C. Nandy | Title: Facility location problems in the read-only memory with constant work-space |
Abstract: Facility location problems are captivating both from theoretical and practical
point of view. We study some fundamental facility location problems from the
space-efficient perspective. Here the input is considered to be given in a read-
only memory and only constant amount of work-space is available during the
computation. This constant-work-space model is well-motivated for handling
big-data as well as for computing in smart portable devices with small amount
of extra-space. First, we propose a strategy to implement prune-and-search in this model. As a warm up, we illustrate this technique for finding the Euclidean 1-center constrained on a line for a set of points in ℜ² . Using this we show how to compute the Euclidean 1-center of a set of points in ℜ² . The running time of this algorithms are O(npoly(log n)). While this result gives a positive answer to an open question asked by Asano, Mulzer, Rote and Wang in 2011, the technique used can be applied to other problems which admits solutions by prune-and-search paradigm. For example, we can apply the technique to solve two and three dimensional linear programming in O(npoly(log n)) time in this model. To the best of our knowledge, these are the first sub-quadratic time algorithms for the above mentioned problems in the constant work space model. | |
Click for .pdf | |
Venkatesh Raman | Title: Selection under model restrictions |
Abstract: The complexity of selection (of finding the median or the k-th smallest element for any integer k) is a very well studied problem in computer science. By a clever divide and conquer technique, this has a classical linear time algorithm. This talk will survey some results on the complexity of this problem when the model of computation is severely restricted. In particular, we study this problem
In all cases we provide interesting algorithms, lower bounds and open problems. | |
Click for .pdf | |
Bimal K Roy | Title: Analytics for crowd sourced data |
Abstract: Crowd source data are the ones generated from voluntary participation in a study; not evolved from a suitably designed scientific study. Two case studies are presented: counting tigers from pugmarks & evaluating reliability of a public domain software. Suitable statistical models are explored to handle these situations. Findings will be presented. | |
Click for .pdf | |
Sandeep Sen | Title: New techniques for randomized rounding |
Abstract: We present new techniques for rounding of Packing Integer Linear Programming problems. For sparse random instances we obtain significant improvements over the classical randomized rounding results | |
Click for .pdf |