Indo-German Workshop
on
Algorithms


9th to 13th March, 2015
Hosted By: Indian Statistical Institute, Kolkata,India
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 = (wi), 0 ≤ i ≤ n − 1, is the demand vector (w i represents the number of channels required for cell i), and (3) C = (cij), 0 ≤ i, j ≤ n − 1, is the frequency separation matrix (cij 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 read-only memory where input elements are not allowed to be moved within; the complexity then boils down to interesting time-space tradeoffs;
  • in `restore' model where input elements can be moved within, but at the end of the computation, the input permutation has to be restored;
  • when the input numbers are integers in read-only memory, and standard word RAM operations can be performed;
  • when the elements are not from a totally ordered set, and hence only equality comparisons can be performed (and the goal is to find the frequency of each element)
  • when the comparison outcomes can not be trusted when the elements are too close to each other.

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