We describe a new rounding procedure that optimally combines the benefits of both iterated rounding and randomized rounding. A nice feature of this procedure that it can be applied easily and in a black-box way to any problem where iterated rounding works with a "small slack". We will show how this leads to new results for several classic problems such as degree-bounded spanning trees, rounding column sparse LPs  and load-balancing on unrelated machines.

Recorded Talk

Finding the exact integrality gap for the LP relaxation of the metric Travelling Salesman Problem (TSP) has been an open problem for over thirty years with little progress made. It is known that its value lies between  4/3 and 3/2, and a famous conjecture states that it equals 4/3.  For this problem, essentially two "fundamental'" classes of instances have been proposed.  This  fundamental property means that in order to show that the integrality gap is at most some value p for all instances of the metric TSP, it is sufficient to show it only for the instances in the fundamental class.  In this paper we successfully improve the upper bound for the integrality gap from 3/2 to 10/7 for the half-integer points for one of these fundamental classes.  Our methods involve some innovative applications of tools from combinatorial optimization which have the potential to be more broadly applied, and will be emphasized in the talk.

Joint work with András Sebő.

Recorded talk

We study the F-center problem with outliers: given a metric space (X,d), a general down-closed family F of subsets of X, and a parameter m, we need to locate a subset S∈F of centers such that the maximum distance among the closest m points in X to S is minimized. Our main result is a dichotomy theorem. Colloquially, we prove that there is an efficient 3-approximation for the F-center problem with outliers if and only if we can efficiently optimize a poly-bounded linear function over F subject to a partition constraint. One concrete upshot of our result is a polynomial time 3-approximation for the knapsack center problem with outliers for which no (true) approximation algorithm was known.

Recorded Talk

We consider the integer points in a box B, ordered by a lexicographic rule. To each integer point x in B we associate a cutting plane (lex-cut) that eliminates the integer points in B that are lexicographically smaller than x and is satisfied by the others. The family of lex-cuts contains the Chvátal-Gomory cuts, but does not contain and is contained in the family of split cuts.We give finite cutting plane method based on lex-cuts to solve the integer program min{cx: x ∈ S ∩ Zⁿ}, where S ⊂ Rⁿ is a compact set and c ∈ Zⁿ. We analyze the worst-case behavior of our algorithm and propose some variants. 

Joint work with Marianna De Santis, Marco Di Summa and Francesco Rinaldi.

Recorded Talk

Abstract siehe https://arxiv.org/abs/1711.05667

Recorded Talk 

Among many families of cutting planes for (mixed) integer programming proposed in the literature, Gomory mixed-integer cuts seem to stand out for at least two reasons: (i) they can be derived via a simple closed formula from the optimal tableau of the continuous relaxation; (ii) in practice, they tend to perform better than other types of general-purpose cutting planes. However, a formal justification for this behavior has not been given up to now. We give a rigorous theoretical explanation for the empirical superiority of Gomory mixed-integer cuts by working in the context of the pure integer infinite group relaxation proposed by Gomory and Johnson, which is an infinite-dimensional model that encompasses all possible integer programming problems at the same time. We show that for this model, Gomory mixed-integer cuts are the valid inequalities that cut off the maximum volume from the nonnegative orthant, and therefore can be seen as the optimal cutting planes if the volume cut off is chosen as a criterion to measure the strength of a cutting plane.

Joint work with A. Basu. M. Conforti, G. Zambelli.

Recorded talk

Borradaile et al. (2017) called an orientation of an undirected graph egalitarian if the sequence of in-degrees, when arranged in a decreasing order, is lexicographically minimal. That is, the largest in-degree is as small as possible, within this, the next largest in-degree is as small as possible, and so on. We prefer to call such a sequence decreasingly minimal (=dec-min) to avoid confusion with other egalitarian-felt orientations.Borradaile et al. proved that an orientation is dec-min if and only if there is no dipath from s to t with in-degrees ρ(t) ≥ ρ(s)+2. They conjectured that an analogous statement holds for strongly connected dec-min orientations, as well. We prove anextension of their conjecture concerning k-edge-connected orientations. In fact, we characterize dec-min elements of an M-convex set (which is nothing but the set of integral points of an integral base-polyhedron), and rely on a result (1980, 1984) stating that the in-degree vectors of k-edge-connected orientations are the integral points of a base-polyhedron. The approach also gives rise to a generalization of a result of Levin and Onn (2016) on 'shifted'  matroid optimization, to a solution of the discrete counter-part of Megiddo's 'lexicographically' optimal network flow problem (1974, 1977), and finds applications in resource allocation.

Joint work with Kazuo Murota.

Recorded Talk

The Tree Augmentation Problem (TAP) is a fundamental network design problem in which we are given a tree and a set of additional edges, also called links. The task is to find a set of links, of minimum size, whose addition to the tree leads to a 2-edge-connected graph. A long line of results on TAP culminated in the previously best known approximation guarantee of 1.5 achieved by a combinatorial approach due to Kortsarz and Nutov [ACM Transactions on Algorithms 2016], and also by an SDP-based approach by Cheriyan and Gao [Algorithmica 2017]. Moreover, an elegant LP-based (1.5+ε)-approximation has also been found very recently by Fiorini, Gross, Koenemann, and Sanità [SODA 2018]. In this talk, we show that an approximation factor below 1.5 can be achieved, by presenting a 1.458-approximation that is based on several new techniques.

Joint work with Christos Kalaitzis and Rico Zenklusen.

Recorded Talk

When delivering items to a set of destinations, one can save time and cost by passing a subset to a sub-contractor at any point en route. We consider a model where a set of items are initially loaded in one vehicle and should be distributed before a given deadline Δ. In addition to travel time and time for deliveries, we assume that there is a fixed delay for handing over an item from one vehicle to another. We will show that it is easy to decide whether an instance is feasible, i.e., whether it is possible to deliver all items before the deadline Δ. We then consider computing a feasible tour of minimum cost, where we incur a cost per unit distance traveled by the vehicles, and a setup cost for every used vehicle. Our problem arises in practical applications and generalizes classical problems such as shallow-light trees and the bounded-latency problem. Our main result is a polynomial-time algorithm that, for any given ε>0 and any feasible instance, computes a solution that delivers all items before time (1+ε)Δ and has cost O(1+1/ε) OPT, where OPT is the minimum cost of any feasible solution. We show that our result is best possible in the sense that any improvement would lead to progress on 25-year-old questions on shallow-light trees.

Joint work with Jochen Könemann and Jens Vygen.

Recorded Talk

The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Nevertheless, Lovasz (1980) showed that this problem admits a min-max formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem. We present a combinatorial, deterministic, polynomial-time algorithm for the weighted linear matroid parity problem. The algorithm builds on a polynomial matrix formulation using Pfaffian and adopts a primal-dual approach based on the augmenting path algorithm of Gabow and Stallmann (1986) for the unweighted problem.

Recorded Talk

We investigate the minimum-cost perfect matching problem in metric spaces with two stages. In the first stage, an algorithm is confronted with a set of points from a metric space and it needs to find a perfect matching among them. Subsequently, an adversary can announce new points after which the algorithm has to give a perfect matching on the extended set. However, for every arrived point, the algorithm can only do a constant number of reallocations with respect to the old matching. We call an algorithm for this problem (two-stage) robust if the costs of each matching are within a constant factor of the costs induced by a minimum-cost matching.For general metric spaces, we present an algorithm that is robust to the arrival of k new points, where k must be specified before the construction of the first matching. For the special case where the metric space is the real line together with the Euclidean distance, we can find a matching which is robust against the arrival of any (unknown) number of points. Our results can be seen as a first step towards solving the online version of the problem.

Joint work with Ulrike Schmidt-Kraepelin and José Verschae.

Recorded talk

In several applications it is important to understand the transient behavior of "overloaded bipartite queues" over time in order to understand the allocation of scarce resources (sources) to classes of customers (sinks) under allocation rules that increase customers' chances of being served when they have been waiting longer. Exactly solving such problems is very difficult, but we show that a fluid flow approximation very closely tracks the exact behavior.  We then show that the fluid flow model can be solved with the help of parametric min cuts.

Recorded Talk

Explorable uncertainty refers to settings where parts of the input data are initially unknown, but can be obtained at a certain cost using queries. An algorithm can make queries one by one until it has obtained sufficient information to solve a  given problem. The challenge lies in balancing the cost for querying and the impact on the solution quality. In this talk, we give a short overview on recent work on explorable uncertainty for combinatorial optimization problems and then focus on a particular scheduling problem.

The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number kc of times. Travel costs may not be symmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families. The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984). It runs in time nO(n)+O(n3log∑ckc)and requires nΩ(n) space. The interesting feature of the Cosmadakis-Papadimitriou algorithm is its logarithmic dependence on the total length ∑ckc of the tour, allowing the algorithm to handle instances with very long tours, beyond what is tractable in the standard TSP setting. However, the superexponential dependence on the number of cities in both its time and space complexity renders the algorithm impractical for all but the narrowest range of this parameter. We significantly improve on the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in single-exponential time with output-linear space. More precisely, we obtain the running time 2O(n)+O(n3log∑ckc), with O(n2log∑ckc) space. Assuming the Exponential-time Hypothesis (ETH), both the time and space requirements of our algorithm are optimal. Our algorithm is deterministic, and arguably both simpler and easier to analyse than the original approach of Cosmadakis and Papadimitriou.

Recorded talk

We consider the unrelated machine scheduling problem when job processing-times are stochastic. We provide the first constant factor approximation algorithm for the setting where one wants a fixed assignment of jobs to machines so as to minimize the expected makespan. The identical machines special case has been well-understood for several years, but the problem was previously open even in the case of related machines. The main technical contribution is an efficiently computable lower bound via an exponential-sized LP, and its rounding.

Joint work with A. Gupta, A. Kumar and X. Shen.

Recorded Talk

The 3-coloring exponential graph on G is the graph whose vertex set corresponds to 3-colorings of G.  We denote this graph by K₃^G. Two vertices corresponding to colorings f and h of G are connected by an edge in K₃^G if f(i) ≠ h(j) and f(j) ≠ h(i) for all ij ∈ E.  El-Zahar and Sauer (1985) showed that when G is 4-chromatic, K₃^G is 3-colorable.  Based on this work, Tardif (2006) gave an algorithm to 3-color K₃^G.  The complexity of this algorithm is polynomial in the size of K₃^G.  Tardif asked if there is an algorithm in which the complexity of assigning a color to a vertex of K₃^G is polynomial in the size of G.  In this talk, we will present such an algorithm, answering Tardif's question affirmatively.

Joint work with Adrien Argento.

In the prize collecting Steiner forest problem, the goal is to choose a subgraph of a given graph so that the sum of the cost of these edges and penalties associated with specified terminal pairs that are not connected, is minimized. It was widely believed that the integrality gap of the natural LP formulation for this problem is 2. We dispel this belief by showing that the integrality gap is at least 9/4 (even for planar graphs). Some other negative results will also be discussed.

Joint work with Jochen Könemann, Kanstantsin Pashkovich, R. Ravi, Chaitanya Swamy and Jens Vygen.

Recorded talk

The "nucleolus" is one of the ways to distribute the common profit among all participating players in some common business fairly. The first mention of this notion of fair distribution goes as far back as the Talmud. In this talk, we will speak about ways to compute nucleolus for weighted voting games and weighted matching games.

Recorded Talk

We propose and discuss a combinatorial algorithm to solve the recoverable robust matroid basis problem under integral uncertainties. The problem can be formulated as follows: given a matroid on ground set E, some integer k, and two linear cost functions c and w on the ground set, determine two bases X and Y of minimal cost c(X)+w(Y) under the constraint that X and Y have at least k elements in common. Joint work in progress with Björn Tauer and Stefan Lendl.

The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. We show that games of rank 1 can be solved very fast: in polynomial time to find one Nash equilibrium, and all equilibria are found by path-following (which finds one equilibrium of a bimatrix game). However, rank-1 games may have exponentially many equilibria, and we conjecture that uniqueness of Nash equilibrium is co-NP-complete.

Joint work with Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni.

Recorded talk

Edmonds characterized digraphs having a packing of k spanning arborescences in terms of connectivity and later in terms of matroid intersection. Durand de Gevigney, Nguyen, and Szigeti characterized digraphs having a packing of (not necessarily spanning) arborescences with some matroid constraint and gave an algorithm for the weighted case using submodular function minimization. Kamiyama, Katoh, and Takizawa characterized digraphs that have a packing of reachability arborescences. Cs. Király provided a common generalization of these results and an algorithm for the cardinality case. Bérczi, T. Király, and Kobayashi showed, using bi-set functions, that the weighted case of Cs. Király's problem can be solved with submodular flows.We show in this talk that this weighted problem can be solved with the weighted matroid intersection algorithm of Edmonds. In the reduction we show a construction of matroids from intersecting submodular bi-set functions.

Joint work with Cs. Király and S. Tanigawa

Recorded Talk

The rigidity of polyhedra in 3-space is one of the centralsubject in rigidity theory whose history goes back to Cauchy’s work. Cauchy’s theorem states that the 1-skeleton of a simplicial convex polyhedron has a unique convex realization in 3-space.  In this talk I will show that the convexity assumption can be dropped if a simplicial polyhedron is generic, 4-connected, and has at least one braced edge. The proof is done by exploiting a technique from Colin de Verdiere-type graph parameters. I will explain this connection.

Joint work with Tibor Jordan.

Recorded Talk

Among various variants of the traveling salesman problem, the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this paper, we go below this threshold: we devise a polynomial-time algorithm for the s-t-path graph TSP with approximation ratio 1.497. Our algorithm can be viewed as a refinement of the 3/2-approximation algorithm by Sebö and Vygen [2014], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics).

Joint work with Jens Vygen.

Recorded talk

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.

Recorded Talks:
Part I
Part II

I will present a 1.5-approximation for the Metric Path Traveling Salesman Problem (path TSP). All recent improvements on path TSP crucially exploit a structural property shown by An, Kleinberg, and Shmoys [Journal of the ACM, 2015], namely that cuts with a value strictly below 2 with respect to any Held-Karp solution form a chain. Such narrow cuts are the obstacle why Christofides' celebrated 1.5-approximation for TSP does not easily extend to the more general path version of TSP. The approach I introduce significantly deviates from prior techniques in this point, by showing the benefit of not only focussing on narrow cuts, but instead dealing with larger s-t cuts even though they are much less structured. More precisely, we will see that a variation of the dynamic programming idea recently introduced by Traub and Vygen [SODA, 2018] is versatile enough to deal with larger size cuts, by exploiting a seminal result of Karger on the number of near-minimum cuts. Through this technique, we obtain a well-structured point in the Held-Karp relaxation from which we derive the 1.5-approximation. This allows us to avoid a recursive application of dynamic programming as used by Traub and Vygen in their recent (1+epsilon)-approximation, and we obtain a considerably simpler algorithm avoiding an additional error term in the approximation guarantee. The obtained approach matches the still unbeaten 1.5-approximation guarantee of Christofides' algorithm for TSP. Hence, any further progress on the approximability of path TSP will also lead to an improvement over Christofides' 1.5-approximation for TSP.

Recorded Talk