Rico Zenklusen

STOC Conference 2024 Conference Paper

Ghost Value Augmentation for k-Edge-Connectivity

• D. Ellis Hershkowitz
• Nathan Klein
• Rico Zenklusen

We give a poly-time algorithm for the k -edge-connected spanning subgraph ( k -ECSS) problem that returns a solution of cost no greater than the cheapest ( k +10)-ECSS on the same graph. Our approach enhances the iterative relaxation framework with a new ingredient, which we call ghost values, that allows for high sparsity in intermediate problems. Our guarantees improve upon the best-known approximation factor of 2 for k -ECSS whenever the optimal value of ( k +10)-ECSS is close to that of k -ECSS. This is a property that holds for the closely related problem k -edge-connected spanning multi-subgraph ( k -ECSM), which is identical to k -ECSS except edges can be selected multiple times at the same cost. As a consequence, we obtain a 1+ O (1/ k )-approximation algorithm for k -ECSM, which resolves a conjecture of Pritchard and improves upon a recent 1+ O (1/√ k )-approximation algorithm of Karlin, Klein, Oveis Gharan, and Zhang. Moreover, we present a matching lower bound for k -ECSM, showing that our approximation ratio is tight up to the constant factor in O (1/ k ), unless P=NP.

SODA Conference 2024 Conference Paper

Single-Source Unsplittable Flows in Planar Graphs

• Vera Traub
• Laura Vargas Koch
• Rico Zenklusen

STOC Conference 2023 Conference Paper

A (1. 5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation

• Vera Traub
• Rico Zenklusen

Connectivity augmentation problems are among the most elementary questions in Network Design. Many of these problems admit natural 2-approximation algorithms, often through various classic techniques, whereas it remains open whether approximation factors below 2 can be achieved. One of the most basic examples thereof is the Weighted Connectivity Augmentation Problem (WCAP). In WCAP, one is given an undirected graph together with a set of additional weighted candidate edges, and the task is to find a cheapest set of candidate edges whose addition to the graph increases its edge-connectivity. We present a (1.5+ε)-approximation algorithm for WCAP, showing for the first time that factors below 2 are achievable. On a high level, we design a well-chosen local search algorithm, inspired by recent advances for Weighted Tree Augmentation. To measure progress, we consider a directed weakening of WCAP and show that it has highly structured planar solutions. Interpreting a solution of the original problem as one of this directed weakening allows us to describe local exchange steps in a clean and algorithmically amenable way. Leveraging these insights, we show that we can efficiently search for good exchange steps within a component class of link sets that is closely related to bounded treewidth subgraphs of circle graphs. Moreover, we prove that an optimum solution can be decomposed into smaller components, at least one of which leads to a good local search step as long as we did not yet achieve the claimed approximation guarantee.

SODA Conference 2022 Conference Paper

Congruency-Constrained TU Problems Beyond the Bimodular Case

• Martin Nägele
• Richard Santiago
• Rico Zenklusen

A long-standing open question in Integer Programming is whether integer programs with constraint matrices with bounded subdeterminants are efficiently solvable. An important special case thereof are congruency-constrained integer programs min{ c T x: Tx ≤ b, γ T x ≡ r (mod m ), x ∊ ℤ n } with a totally unimodular constraint matrix T. Such problems have been shown to be polynomial-time solvable for m = 2, which led to an efficient algorithm for integer programs with bimodular constraint matrices, i. e. , full-rank matrices whose n × n subdeterminants are bounded by two in absolute value. Whereas these advances heavily relied on existing results on well-known combinatorial problems with parity constraints, new approaches are needed beyond the bimodular case, i. e. , for m > 2. We make first progress in this direction through several new techniques. In particular, we show how to efficiently decide feasibility of congruency-constrained integer programs with a totally unimodular constraint matrix for m = 3. Furthermore, for general m, our techniques also allow for identifying flat directions of infeasible problems, and deducing bounds on the proximity between solutions of the problem and its relaxation.

ICML Conference 2022 Conference Paper

Fair and Fast k-Center Clustering for Data Summarization

• Haris Angelidakis
• Adam Kurpisz
• Leon Sering
• Rico Zenklusen

We consider two key issues faced by many clustering methods when used for data summarization, namely (a) an unfair representation of "demographic groups” and (b) distorted summarizations, where data points in the summary represent subsets of the original data of vastly different sizes. Previous work made important steps towards handling separately each of these two issues in the context of the fundamental k-Center clustering objective through the study of fast algorithms for natural models that address them. We show that it is possible to effectively address both (a) and (b) simultaneously by presenting a clustering procedure that works for a canonical combined model and (i) is fast, both in theory and practice, (ii) exhibits a worst-case constant-factor guarantee, and (iii) gives promising computational results showing that there can be significant benefits in addressing both issues together instead of sequentially.

SODA Conference 2022 Conference Paper

Local Search for Weighted Tree Augmentation and Steiner Tree

• Vera Traub
• Rico Zenklusen

We present a technique that allows for improving on some relative greedy procedures by well-chosen (non-oblivious) local search algorithms. Relative greedy procedures are a particular type of greedy algorithm that start with a simple, though weak, solution, and iteratively replace parts of this starting solution by stronger components. Some well-known applications of relative greedy algorithms include approximation algorithms for Steiner Tree and, more recently, for connectivity augmentation problems. The main application of our technique leads to a (1. 5 + ∊ )-approximation for Weighted Tree Augmentation, improving on a recent relative greedy based method with approximation factor 1 + ln 2 + ∊ ≈ 1. 69. Furthermore, we show how our local search technique can be applied to Steiner Tree, leading to an alternative way to obtain the currently best known approximation factor of ln 4 + ∊. Contrary to prior methods, our approach is purely combinatorial without the need to solve an LP. Nevertheless, the solution value can still be bounded in terms of the well-known hypergraphic LP, leading to an alternative, and arguably simpler, technique to bound its integrality gap by ln 4.

FOCS Conference 2021 Conference Paper

A Better-Than-2 Approximation for Weighted Tree Augmentation

• Vera Traub
• Rico Zenklusen

We present an approximation algorithm for Weighted Tree Augmentation with approximation factor 1 + $\ln 2+\varepsilon < 1. 7$. This is the first algorithm beating the longstanding factor of 2, which can be achieved through many standard techniques. −

STOC Conference 2021 Conference Paper

Bridging the gap between tree and connectivity augmentation: unified and stronger approaches

• Federica Cecchetto
• Vera Traub
• Rico Zenklusen

We consider the Connectivity Augmentation Problem (CAP), a classical problem in the area of Survivable Network Design. It is about increasing the edge-connectivity of a graph by one unit in the cheapest possible way. More precisely, given a k -edge-connected graph G =( V , E ) and a set of extra edges, the task is to find a minimum cardinality subset of extra edges whose addition to G makes the graph ( k +1)-edge-connected. If k is odd, the problem is known to reduce to the Tree Augmentation Problem (TAP)—i.e., G is a spanning tree—for which significant progress has been achieved recently, leading to approximation factors below 1.5 (the currently best factor is 1.458). However, advances on TAP did not carry over to CAP so far. Indeed, only very recently, Byrka, Grandoni, and Ameli (STOC 2020) managed to obtain the first approximation factor below 2 for CAP by presenting a 1.91-approximation algorithm based on a method that is disjoint from recent advances for TAP. We first bridge the gap between TAP and CAP, by presenting techniques that allow for leveraging insights and methods from TAP to approach CAP. We then introduce a new way to get approximation factors below 1.5, based on a new analysis technique. Through these ingredients, we obtain a -approximation algorithm for CAP, and therefore also TAP. This leads to the currently best approximation result for both problems in a unified way, by significantly improving on the above-mentioned 1.91-approximation for CAP and also the previously best approximation factor of 1.458 for TAP by Grandoni, Kalaitzis, and Zenklusen (STOC 2018). Additionally, a feature we inherit from recent TAP advances is that our approach can deal with the weighted setting when the ratio between the largest to smallest cost on extra links is bounded, in which case we obtain approximation factors below 1.5.

STOC Conference 2020 Conference Paper

Reducing path TSP to TSP

• Vera Traub
• Jens Vygen
• Rico Zenklusen

We present a black-box reduction from the path version of the Traveling Salesman Problem (Path TSP) to the classical tour version (TSP). More precisely, we show that given an α-approximation algorithm for TSP, then, for any ε >0, there is an (α+ε)-approximation algorithm for the more general Path TSP. This reduction implies that the approximability of Path TSP is the same as for TSP, up to an arbitrarily small error. This avoids future discrepancies between the best known approximation factors achievable for these two problems, as they have existed until very recently. A well-studied special case of TSP, Graph TSP, asks for tours in unit-weight graphs. Our reduction shows that any α-approximation algorithm for Graph TSP implies an (α+ε)-approximation algorithm for its path version. By applying our reduction to the 1.4-approximation algorithm for Graph TSP by Sebő and Vygen, we obtain a polynomial-time (1.4+ε)-approximation algorithm for Graph Path TSP, improving on a recent 1.497-approximation algorithm of Traub and Vygen. We obtain our results through a variety of new techniques, including a novel way to set up a recursive dynamic program to guess significant parts of an optimal solution. At the core of our dynamic program we deal with instances of a new generalization of (Path) TSP which combines parity constraints with certain connectivity requirements. This problem, which we call Φ-TSP, has a constant-factor approximation algorithm and can be reduced to TSP in certain cases when the dynamic program would not make sufficient progress.

STOC Conference 2020 Conference Paper

The one-way communication complexity of submodular maximization with applications to streaming and robustness

• Moran Feldman
• Ashkan Norouzi-Fard
• Ola Svensson
• Rico Zenklusen

We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model that lies between the offline and streaming model, and study it under the aspect of one-way communication complexity. Our model captures the streaming setting (by considering a large number of players), and, in addition, two player approximation results for it translate into the robust setting. We present tight one-way communication complexity results for our model, which, due to the above-mentioned connections, have multiple implications in the data stream and robust setting.

SODA Conference 2019 Conference Paper

A 1. 5-Approximation for Path TSP

• Rico Zenklusen

We 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 narrow cuts with respect to a Held-Karp solution form a chain. We significantly deviate from these approaches by showing the benefit of dealing with larger s-t cuts, even though they are much less structured. More precisely, we show 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. This avoids a recursive application of dynamic programming as used by Traub and Vygen, and leads to a considerably simpler algorithm avoiding an additional error term in the approximation guarantee. We match 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 for TSP.

SODA Conference 2019 Conference Paper

A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond

• Martin Nägele
• Rico Zenklusen

Short spanning trees subject to additional constraints are important building blocks in various approximation algorithms, and, moreover, they capture interesting problem settings on their own. Especially in the context of the Traveling Salesman Problem (TSP), new techniques for finding spanning trees with well-defined properties have been crucial in recent progress. We consider the problem of finding a spanning tree subject to constraints on the edges in a family of cuts forming a laminar family of small width. Our main contribution is a new dynamic programming approach where the value of a table entry does not only depend on the values of previous table entries, as it is usually the case, but also on a specific representative solution saved together with each table entry. This allows for handling a broad range of constraint types. In combination with other techniques—including negatively correlated rounding and a polyhedral approach that, in the problems we consider, allows for avoiding potential losses in the objective through the randomized rounding—we obtain several new results. We first present a quasi-polynomial time algorithm for the Minimum Chain-Constrained Spanning Tree Problem with an essentially optimal guarantee. More precisely, each chain constraint is violated by a factor of at most 1 + ε, and the cost is no larger than that of an optimal solution not violating any chain constraint. The best previous procedure is a bicriteria approximation violating each chain constraint by up to a constant factor and losing another factor in the objective. Moreover, our approach can naturally handle lower bounds on the chain constraints, and it can be extended to constraints on cuts forming a laminar family of constant width. Furthermore, we show how our approach can also handle parity constraints as used in the context of (path) TSP and a generalization thereof, and discuss implications in this context.

SODA Conference 2018 Conference Paper

A Framework for the Secretary Problem on the Intersection of Matroids

• Moran Feldman
• Ola Svensson
• Rico Zenklusen

The secretary problem became one of the most prominent online selection problems due to its numerous applications in online mechanism design. The task is to select a maximum weight subset of elements subject to given constraints, where elements arrive one-by-one in random order, revealing a weight upon arrival. The decision whether to select an element has to be taken immediately after its arrival. The different applications that map to the secretary problem ask for different constraint families to be handled. The most prominent ones are matroid constraints, which both capture many relevant settings and admit strongly competitive secretary algorithms. However, dealing with more involved constraints proved to be much more difficult, and strong algorithms are known only for a few specific settings. In this paper, we present a general framework for dealing with the secretary problem over the intersection of several matroids. This framework allows us to combine and exploit the large set of matroid secretary algorithms known in the literature. As one consequence, we get constant-competitive secretary algorithms over the intersection of any constant number of matroids whose corresponding (single-)matroid secretary problems are currently known to have a constant-competitive algorithm. Moreover, we show that our results extend to submodular objectives.

STOC Conference 2018 Conference Paper

Improved approximation for tree augmentation: saving by rewiring

• Fabrizio Grandoni 0001
• Christos Kalaitzis
• Rico Zenklusen

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, Groß, K'onemann, and Sanitá [SODA 2018]. In this paper, 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. By extending prior results of Adjiashvili [SODA 2017], we first present a black-box reduction to a very structured type of instance, which played a crucial role in recent development on the problem, and which we call k -wide. Our main contribution is a new approximation algorithm for O (1)-wide tree instances with approximation guarantee strictly below 1.458, based on one of their fundamental properties: wide trees naturally decompose into smaller subtrees with a constant number of leaves. Previous approaches in similar settings rounded each subtree independently and simply combined the obtained solutions. We show that additionally, when starting with a well-chosen LP, the combined solution can be improved through a new “rewiring” technique, showing that one can replace some pairs of used links by a single link. We can rephrase the rewiring problem as a stochastic version of a matching problem, which may be of independent interest. By showing that large matchings can be obtained in this problem, we obtain that a significant number of rewirings are possible, thus leading to an approximation factor below 1.5.

SODA Conference 2018 Conference Paper

Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting

• Alfonso Cevallos
• Stefan Weltge
• Rico Zenklusen

Mixed-integer mathematical programs are among the most commonly used models for a wide set of problems in Operations Research and related fields. However, there is still very little known about what can be expressed by small mixed-integer programs. In particular, prior to this work, it was open whether some classical problems, like the minimum odd-cut problem, can be expressed by a compact mixed-integer program with few (even constantly many) integer variables. This is in stark contrast to linear formulations, where recent breakthroughs in the field of extended formulations have shown that many polytopes associated to classical combinatorial optimization problems do not even admit approximate extended formulations of sub-exponential size. We provide a general framework for lifting inapproximability results of extended formulations to the setting of mixed-integer extended formulations, and obtain almost tight lower bounds on the number of integer variables needed to describe a variety of classical combinatorial optimization problems. Among the implications we obtain, we show that any mixed-integer extended formulation of sub-exponential size for the matching polytope, cut polytope, travelling salesman polytope or dominant of the odd-cut polytope, needs Ω( n / log n ) many integer variables, where n is the number of vertices of the underlying graph. Conversely, the above-mentioned polyhedra admit polynomial-size mixed-integer formulations with only O ( n ) or O ( n log n ) (for the traveling salesman polytope) many integer variables. Our results build upon a new decomposition technique that, for any convex set C, allows for approximating any mixed-integer description of C by the intersection of C with the union of a small number of affine subspaces.

SODA Conference 2018 Conference Paper

Submodular Minimization Under Congruency Constraints

• Martin Nägele
• Benny Sudakov
• Rico Zenklusen

STOC Conference 2017 Conference Paper

A strongly polynomial algorithm for bimodular integer linear programming

• Stephan Artmann
• Robert Weismantel
• Rico Zenklusen

We present a strongly polynomial algorithm to solve integer programs of the form max{ c T x : Ax ≤ b , x εℤ n }, for A εℤ m X n with rank ( A )= n , b ε≤ m , c ε≤ n , and where all determinants of ( n X n )-sub-matrices of A are bounded by 2 in absolute value. In particular, this implies that integer programs max{ c T x : Q x ≤ b , x εℤ ≥0 n }, where Q ε ℤ m X n has the property that all subdeterminants are bounded by 2 in absolute value, can be solved in strongly polynomial time. We thus obtain an extension of the well-known result that integer programs with constraint matrices that are totally unimodular are solvable in strongly polynomial time.

SODA Conference 2017 Conference Paper

Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations

• Robert Hildebrand
• Robert Weismantel
• Rico Zenklusen

We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on n vertices, with a polynomial number of constraints, requires many integer variables. By known reductions, this result extends to the traveling salesman polytope. This lower bound has various implications regarding the existence of small mixed-integer mathematical formulations of common problems in operations research. In particular, it shows that for many classic vehicle routing problems and problems involving matchings, any compact mixed-integer linear description of such a problem requires a large number of integer variables. This provides a first nontrivial lower bound on the number of integer variables needed in such settings.

SODA Conference 2017 Conference Paper

Firefighting on Trees Beyond Integrality Gaps

• David Adjiashvili
• Andrea Baggio
• Rico Zenklusen

The Firefighter problem and a variant of it, known as Resource Minimization for Fire Containment (RMFC), are natural models for optimal inhibition of harmful spreading processes. Despite considerable progress on several fronts, the approximability of these problems is still badly understood. This is the case even when the underlying graph is a tree, which is one of the most- studied graph structures in this context and the focus of this paper. In their simplest version, a fire spreads from one fixed vertex step by step from burning to adjacent non-burning vertices, and at each time step B many non-burning vertices can be protected from catching fire. The Firefighter problem asks, for a given B, to maximize the number of vertices that will not catch fire, whereas RMFC (on a tree) asks to find the smallest B that allows for saving all leaves of the tree. Prior to this work, the best known approximation ratios were an O (1)-approximation for the Firefighter problem and an O (log * n )-approximation for RMFC, both being LP-based and essentially matching the integrality gaps of two natural LP relaxations. We improve on both approximations by presenting a PTAS for the Firefighter problem and an O (1)-approximation for RMFC, both qualitatively matching the known hardness results. Our results are obtained through a combination of the known LPs with several new techniques, which allow for efficiently enumerating over super-constant size sets of constraints to strengthen the natural LPs.

SODA Conference 2017 Conference Paper

Local Search for Max-Sum Diversification

• Alfonso Cevallos
• Friedrich Eisenbrand
• Rico Zenklusen

We provide simple and fast polynomial-time approximation schemes (PTASs) for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given n points p 1, …, p n ∊ ℝ q and an integer k, select k points such that the average Euclidean distance between these points is maximized. This problem is commonly applied in web search and information retrieval in order to select a diverse set of representative points from the input. In this context, it has recently received a lot of attention. We present new techniques to analyze natural local- search algorithms. This leads to a for distances of negative type, even subject to a general matroid constraint of rank k, in time O ( nk 2 log k ), when assuming that distance evaluations and calls to the independence oracle are constant time. Negative-type distances include as special cases Euclidean and Manhattan distances, among other natural distances. Our result easily transforms into a PTAS. It improves on the only previously known PTAS for this setting, which relies on convex optimization techniques in an n -dimensional space and is impractical for large data sets. In contrast, our procedure has an (optimal) linear dependence on n. Using generalized exchange properties of matroid intersection, we show that a PTAS can be obtained for matroid- intersection constraints as well. Moreover, our techniques, being based on local search, are conceptually simple and allow for various extensions. In particular, we get asymptotically optimal O (1)-approximations when combining the classic dispersion function with a monotone submodular objective, which is a very common class of functions to measure diversity and relevance. This result leverages recent advances on local-search techniques based on proxy functions to obtain optimal approximations for monotone submodular function maximization subject to a matroid constraint.

SODA Conference 2016 Conference Paper

Online Contention Resolution Schemes

• Moran Feldman
• Ola Svensson
• Rico Zenklusen

We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call online contention resolution schemes (OCRSs), is applicable to many online selection problems, including Bayesian online selection, oblivious posted pricing mechanisms, and stochastic probing models. It allows for handling a wide set of constraints, and shares many strong properties of offline contention resolution schemes. In particular, OCRSs for different constraint families can be combined to obtain an OCRS for their intersection. Moreover, we can approximately maximize submodular functions in the online settings we consider. We, thus, get a broadly applicable framework for several online selection problems, which improves on previous approaches in terms of the types of constraints that can be handled, the objective functions that can be dealt with, and the assumptions on the strength of the adversary. Furthermore, we resolve two open problems from the literature; namely, we present the first constant-factor constrained oblivious posted price mechanism for matroid constraints, and the first constant-factor algorithm for weighted stochastic probing with deadlines.

SODA Conference 2015 Conference Paper

A Simple O (log log(rank))-Competitive Algorithm for the Matroid Secretary Problem

• Moran Feldman
• Ola Svensson
• Rico Zenklusen

Only recently progress has been made in obtaining o (log(rank))-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a -competitive procedure, and Lachish (2014) recently presented a O (log log(rank))-competitive algorithm. Both algorithms are involved with complex analyses. Using different tools, we present a considerably simpler O (log log(rank))-competitive algorithm. Our algorithm can be interpreted as a distribution over a simple type of matroid secretary algorithms which are easy to analyze. We are also able to vastly improve on the hidden constant in the competitive ratio.

FOCS Conference 2015 Conference Paper

An O(1)-Approximation for Minimum Spanning Tree Interdiction

• Rico Zenklusen

Network interdiction problems are a natural way to study the sensitivity of a network optimization problem with respect to the removal of a limited set of edges or vertices. One of the oldest and best-studied interdiction problems is minimum spanning tree (MST) interdiction. Here, an undirected multigraph with nonnegative edge weights and positive interdiction costs on its edges is given, together with a positive budget B. The goal is to find a subset of edges R, whose total interdiction cost does not exceed B, such that removing R leads to a graph where the weight of an MST is as large as possible. Frederickson and Solis-Oba (SODA 1996) presented an O(log m)-approximation for MST interdiction, where m is the number of edges. Since then, no further progress has been made regarding approximations, and the question whether MST interdiction admits an O(1)-approximation remained open. We answer this question in the affirmative, by presenting a 14-approximation that overcomes two main hurdles that hindered further progress so far. Moreover, based on a well-known 2-approximation for the metric traveling salesman problem (TSP), we show that our O(1)-approximation for MST interdiction implies an O(1)-approximation for a natural interdiction version of metric TSP.

FOCS Conference 2015 Conference Paper

The Submodular Secretary Problem Goes Linear

• Moran Feldman
• Rico Zenklusen

During the last decade, the matroid secretary problem (MSP) became one of the most prominent classes of online selection problems. The interest in MSP is twofold: on the one hand, there are many interesting applications of MSP, and on the other hand, there is strong hope that MSP admits O(1)-competitive algorithms, which is the claim of the well-known matroid secretary conjecture. Partially linked to its numerous applications in mechanism design, substantial interest arose also in the study of nonlinear versions of MSP, with a focus on the sub modular matroid secretary problem (SMSP). The fact that sub modularity captures the property of diminishing returns, a very natural property for valuation functions, is a key reason for the interest in SMSP. So far, O(1)-competitive algorithms have been obtained for SMSP over some basic matroid classes. This created some hope that, analogously to the matroid secretary conjecture, one may even obtain O(1)-competitive algorithms for SMSP over any matroid. However, up to now, most questions related to SMSP remained open, including whether SMSP may be substantially more difficult than MSP, and more generally, to what extend MSP and SMSP are related. Our goal is to address these points by presenting general black-box reductions from SMSP to MSP. In particular, we show that any O(1)-competitive algorithm for MSP, even restricted to a particular matroid class, can be transformed in a black-box way to an O(1)-competitive algorithm for SMSP over the same matroid class. This implies that the matroid secretary conjecture is equivalent to the same conjecture for SMSP. Hence, in this sense SMSP is not harder than MSP. Also, to find O(1)-competitive algorithms for SMSP over a particular matroid class, it suffices to consider MSP over the same matroid class. Using our reductions we obtain many first and improved O(1)-competitive algorithms for SMSP over various matroid classes by leveraging known algorithms for MSP. Moreover, our reductions imply an O(log log(rank))-competitive algorithm for SMSP, thus, matching the currently best asymptotic algorithm for MSP, and substantially improving on the previously best O(log(rank))-competitive algorithm for SMSP.

SODA Conference 2012 Conference Paper

Matroidal degree-bounded minimum spanning trees

• Rico Zenklusen

We consider the minimum spanning tree (MST) problem under the restriction that for every vertex v, the edges of the tree that are adjacent to v satisfy a given family of constraints. A famous example thereof is the classical degree-bounded MST problem, where for every vertex v, a simple upper bound on the degree is imposed. Iterative rounding/relaxation algorithms became the tool of choice for degree-constrained network design problems. A cornerstone for this development was the work of Singh and Lau [19], who showed that for the degree-bounded MST problem, one can find a spanning tree violating each degree bound by at most one unit and with cost at most the cost of an optimal solution that respects the degree bounds. However, current iterative rounding approaches face several limits when dealing with more general degree constraints, where several linear constraints are imposed on the edges adjacent to a vertex v. For example, when a partition of the edges adjacent to v is given and only a fixed number of elements can be chosen out of each set of the partition, current approaches might violate each of the constraints at v by a constant, instead of violating the whole family of constraints at v by at most a constant number of edges. Furthermore, previous iterative rounding approaches are not suited for degree constraints where some edges are in a super-constant number of constraints. We extend iterative rounding/relaxation approaches, both conceptually as well as in their analysis, to address these limitations. Based on these extensions, we present an algorithm for the degree-constrained MST problem where for every vertex v, the edges adjacent to v have to be independent in a given matroid. The algorithm returns a spanning tree of cost at most OPT, such that for every vertex v, it suffices to remove at most 8 edges from the spanning tree to satisfy the matroidal degree constraint at v.

STOC Conference 2012 Conference Paper

Matroids and integrality gaps for hypergraphic steiner tree relaxations

• Michel X. Goemans
• Neil Olver
• Thomas Rothvoss
• Rico Zenklusen

Until recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. In particular, no (efficiently solvable) Steiner tree relaxation was known to have an integrality gap bounded away from 2, before Byrka et al. [3] showed an upper bound of ~1.55 of a hypergraphic LP relaxation and presented a ln(4)+ε ~1.39 approximation based on this relaxation. Interestingly, even though their approach is LP based, they do not compare the solution produced against the LP value. We take a fresh look at hypergraphic LP relaxations for the Steiner tree problem---one that heavily exploits methods and results from the theory of matroids and submodular functions---which leads to stronger integrality gaps, faster algorithms, and a variety of structural insights of independent interest. More precisely, along the lines of the algorithm of Byrka et al.[3], we present a deterministic ln(4)+ε approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap of hypergraphic relaxations.

SODA Conference 2011 Conference Paper

Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding

• Chandra Chekuri
• Jan Vondrák
• Rico Zenklusen

Motivated by multi-budgeted optimization and other applications, we consider the problem of randomly rounding a fractional solution x in the (non-bipartite graph) matching and matroid intersection polytopes. We show that for any fixed δ > 0, a given point x can be rounded to a random solution R such that E [1 R ] = (1 − δ)x and any linear function of x satisfies dimension-free Chernoff-Hoeffding concentration bounds (the bounds depend on S and the expectation μ). We build on and adapt the swap rounding scheme in our recent work [9] to achieve this result. Our main contribution is a non-trivial martingale based analysis framework to prove the desired concentration bounds. In this paper we describe two applications. We give a randomized PTAS for matroid intersection and matchings with any fixed number of budget constraints. We also give a deterministic PTAS for the case of matchings. The concentration bounds also yield related results when the number of budget constraints is not fixed. As a second application we obtain an algorithm to compute in polynomial time an ε-approximate Pareto-optimal set for the multi-objective variants of these problems, when the number of objectives is a fixed constant. We rely on a result of Papadimitriou and Yannakakis [26].

STOC Conference 2011 Conference Paper

Submodular function maximization via the multilinear relaxation and contention resolution schemes

• Jan Vondrák
• Chandra Chekuri
• Rico Zenklusen

FOCS Conference 2010 Conference Paper

Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures

• Chandra Chekuri
• Jan Vondrák
• Rico Zenklusen

We consider the problem of randomly rounding a fractional solution x in an integer polytope P ⊆ [0, 1] n to a vertex X of P, so that E[X] = x. Our goal is to achieve concentration properties for linear and submodular functions of the rounded solution. Such dependent rounding techniques, with concentration bounds for linear functions, have been developed in the past for two poly topes: the assignment poly tope (that is, bipartite matchings and 6-matchings) [32], [19], [23], and more recently for the spanning tree poly tope [2]. These schemes have led to a number of new algorithmic results. In this paper we describe a new swap rounding technique which can be applied in a variety of settings including matroids and matroid intersection, while providing Chernoff-type concentration bounds for linear and submodular functions of the rounded solution. In addition to existing techniques based on negative correlation, we use a martingale argument to obtain an exponential tail estimate for monotone submodular functions. The rounding scheme explicitly exploits exchange properties of the underlying combinatorial structures, and highlights these properties as the basis for concentration bounds. Matroids and matroid intersection provide a unifying framework for several known applications [19], [23], [7], [22], [2] as well as new ones, and their generality allows a richer set of constraints to be incorporated easily. We give some illustrative examples, with a more comprehensive discussion deferred to a later version of the paper.