Institute for Computational and Experimental Research in Mathematics (ICERM)

Abstract

Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the classical simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound O(2^n n^{1.5} log n) for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations.

The number of iterations of our algorithm is at most O(n^{1.5} log n) times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the ‘max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of n shadow vertex simplex paths.

This is joint work with Xavier Allamigeon (INRIA / Ecole Polytechnique), Georg Loho (U. Twente), Bento Natura (LSE), Laszlo Vegh (LSE).

Abstract

In submodular k-partitioning problems, the input is a submodular set function (given via an evaluation oracle) along with a fixed positive integer k (e.g., k = 2, 3, 4, …) and the goal is to partition the ground set into k non-empty parts so as to minimize certain natural objectives of interest. Submodular k-partitioning generalizes partitioning problems over several interesting structures including graphs and hypergraphs. The case of 2-partitioning corresponds to the classic and well-studied submodular minimization problem which is polynomial-time solvable. In this talk, I will outline recent progress towards polynomial-time solvability of submodular k-partitioning for fixed constant integers k >= 3.

Abstract

A graphical design is a quadrature rule for a graph inspired by classical numerical integration on the sphere. Broadly speaking, that means a graphical design is a relatively small subset of graph vertices chosen to capture the global behavior of functions from the vertex set to the real numbers. We first motivate and define graphical designs for graphs with positive edge weights. Through Gale duality, we exhibit a combinatorial bijection between graphical designs and the faces of certain polytopes associated to a graph, called eigenpolytopes. This polytope connection has a variety of beautiful consequences, including a proof of existence, an upper bound on the cardinality of a graphical design, methods to compute, optimize, and organize graphical designs, the existence of random walks with improved convergence rates, and complexity results for associated computational problems. This talk is based on work with Rekha Thomas, Stefan Steinerberger and David Shiroma.

Abstract

In the set covering problem we are given a set system, and we want to find a subcollection with few sets whose union is the entire universe. This problem is NP-hard to approximate to better than (ln n). Moreover we know matching algorithms which are achieved by both greedy and relax-and-round based algorithms. In this talk I will give two more algorithms which achieve the same guarantee (asymptotically), one based on local search, and another based on a learning-based framework (which also works in an online setting with random arrivals). These results are based on joint works with Greg Kehne, Euiwoong Lee, Roie Levin, and Jason Li.

Abstract

In 1933 von Neumann proved a beautiful result that one can compute a point in the intersection of two convex sets (under suitable assumptions) by alternating projections, i.e., successively projecting on one set and then the other. This algorithm assumes that one has access to projection operators for both sets. Here we consider the much weaker setup where we have only access to linear minimization oracles over the convex sets and present an algorithm to find a point in the intersection of two convex sets. Moreover, we provide a modification of the algorithm to minimize a linear function over the intersection and discuss further extensions.

Abstract

Optimization algorithms such as projected Newton's method, FISTA, mirror descent and its variants enjoy near-optimal regret bounds and convergence rates, but suffer from a computational bottleneck of computing projections"" in potentially each iteration (e.g., O(T^{0.5}) regret of online mirror descent). On the other hand, conditional gradient variants solve a linear optimization in each iteration, but result in suboptimal rates (e.g., OT^{0.75}) regret of online Frank-Wolfe). Motivated by this trade-off in runtime v/s convergence rates, we consider iterative projections of close-by points over widely-prevalent submodular base polytopes B(f). We develop a toolkit to speed up the computation of projections using both discrete and continuous perspectives. We subsequently adapt the away-step Frank-Wolfe algorithm to use this information and enable early termination.

Abstract

In this talk, we explore the concept of combinatorial disjunctive constraints (CDC) and their properties. In particular, we examine when one can build small ideal mixed-integer programming (MIP) formulations using CDCs and their linkages to clique trees. We also show that generalized special ordered sets (SOS k) can be modeled by CDCs with ties to clique trees.

Abstract

Standard mixed-integer programming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give an explicit family of stable set polytopes of n-node graphs for which every polynomial-size formulation requires Ω(n / log^2 n) integer variables. By a polyhedral reduction we obtain an analogous result for n-item knapsack polytopes. This improves the previously known bounds of Ω(√n / log n) by Cevallos, Weltge & Zenklusen (SODA 2018). To this end, we extend a result of Göös, Jain & Watson (FOCS 2016, SIAM J. Comput. 2018) showing that the linear extension complexity of stable set polytopes of some n-node graphs is 2^(Ω(n / log n)). We show that the same bound holds for ɛ/n-approximations of these polytopes, for some constant ɛ > 0. On this way, we simplify several of their original arguments to obtain a proof that is accessible to a broader community. For instance, our proof does not require reductions to certain CSP problems or the notion of Karchmer-Wigderson games. This is joint work with Jamico Schade and Makrand Sinha.

Abstract

Given a digraph D, and an integer k>=1, a k-arc-connected flip is an arc subset whose reversal makes the digraph (strongly) k-arc-connected. The main result of this work introduces a sufficient condition for the existence of a k-arc-connected flip that is also a submodular flow for a crossing submodular function. The main result has several applications to graph orientations and combinatorial optimization. For instance, if the underlying graph of D is t-edge-connected for some integer t>=2, there exists a decomposition of the arc set into a k-arc-connected flip and a (t-k)-dijoin, for any integer k such that 1<=k<=t/2. This extends Nash-Williams’ weak orientation theorem, as well as proves a weaker variant of Woodall’s conjecture on such digraphs. The main result follows from a surprising sufficient condition for the existence of capacitated integral solutions to the intersection of two submodular flow systems. This result in turn has some applications for submodular optimization. For instance, in a weakly connected digraph, the intersection of two submodular flow systems defines an integral polyhedron. Joint work with Gerard Cornuejols and Giacomo Zambelli.

Abstract

Explaining why the simplex method is fast in practice, despite it taking exponential time in the theoretical worst case, continues to be a challenge. Smoothed analysis is a paradigm for addressing this question. During my talk I will present recent progress in the smoothed complexity of the simplex method, discussing both upper and lower bounds.

• Slides

Abstract

I will suggest several open problems on optimization over degree sequences of graphs and hypergraphs and over line sums of matrices; describe several recent partial results such as for convex functions, complete graphs, complete bipartite graphs and monotone matrices, and bounded tree width or depth; and outline some proof techniques, including our recent powerful theory of sparse integer programming in high dimensions, which will be explained.

Abstract

The simplex and interior point methods are currently the most computationally successful algorithms for linear optimization. While simplex methods follow an edge path, interior point methods follow the central path. The complexity of these methods is closely related to the combinatorial and geometric structures of the feasible region. Focusing on the analysis of worst-case constructions leading to computationally challenging instances, recently obtained lower bounds on the largest possible diameter of lattice polytopes will be presented. These bounds, via lattice zonotopes, are established using tools from combinatorics and number theory. This talk is based on joint work with Antoine Deza.

Abstract

Given a graph with edges colored red or blue and an integer k, the exact perfect matching problem asks if there exists a perfect matching with exactly k red edges. There exists a randomized polylogarithmic-time parallel algorithm to solve this problem, dating back to the eighties, but no deterministic polynomial-time algorithm is known, even for bipartite graphs. In this talk, we discuss known approaches and their limitations. In particular, we show that there is no sub-exponential-sized linear program that can describe the convex hull of exact matchings in bipartite graphs. In fact, we prove something stronger, that there is no sub-exponential-sized linear program to describe the convex hull of perfect matchings with an odd number of red edges. To prove our result, we devise an exponential set of valid constraints that we believe are interesting in their own right. In particular, we leave as an open problem whether they define the convex hull of perfect matchings with an odd number of red edges.

This is joint work with Xinrui Jia and Weiqiang Yuan

Abstract

The Weighted Connectivity Augmentation Problem (WCAP) asks to augment the edge-connectivity of a graph by adding a min cost edge set among given candidate edges. It is among the most elementary network design problems for which no better-than-2 approximation has been known, whereas 2-approximations can easily be obtained through a variety of well-known techniques. In this talk, I will discuss an approach showing that approximation factors below 2 are achievable for WCAP, ultimately leading to a (1.5+epsilon)-approximation. Our approach is based on a highly structured directed simplification of WCAP with planar optimal solutions. We show how one can successively improve solutions of this directed simplification by moving to mixed solutions, consisting of both directed and undirected edges. These insights can be leveraged in local search and relative greedy strategies, inspired by recent advances on the Weighted Tree Augmentation Problem, to obtain a (1.5+epsilon)-approximation. This is joint work with Vera Traub.

Abstract

Given n points in the plane, how many pairs among these points can have distance exactly 1? More formally, what is the maximum possible number of unit distances among a set of n points in the plane? This problem is a very famous and still largely open problem, called the Erdos unit distance problem. One can also study this problem for other norms on R^2 (or more generally on R^d for any dimension d) that are different from the Euclidean norm. This direction has been suggested in the 1980s by Ulam and Erdos and attracted a lot of attention over the years. We give an almost tight answer to this question for almost all norms on R^d (for any given d). Furthermore, for almost all norms on R^d, we prove an asymptotically tight bound for a related problem, the so-called Erdos distinct distances problem. Our proofs rely in part on arguments from polyhedral geometry (and some tools from matroid theory are also relevant). Joint work with Noga Alon and Matija Bucic.

Abstract

Graphs are ubiquitous in modern applications---including some very large graphs. This leads one to wonder, "How can we understand such large graphs?" One prevalent idea is to observe them locally: to count how many times certain substructures appear. If one knows something about the number of some particular substructures in a graph, what can one say about the number of other substructures or about global properties of the graph in general? Such problems are at the heart of extremal graph theory. In this talk, we will discuss successes and challenges in proving inequalities involving these substructures. We will also encounter graph profiles, complicated objects that allow us to understand all polynomial inequalities involving some fixed set of substructures. This is joint work with Greg Blekherman, Mohit Singh, Rekha Thomas and Fan Wei.

Abstract

The structure of the set of global minimum cuts of a graph is well understood and is captured by a cactus, as proved by Dinitz, Karzanov, and Lomonosov in the 70s. However, even for small epsilon, the set of (1+epsilon) near minimum cuts has a significantly more complex structure. Benczúr and Goemans studied near minimum cuts starting in the late 90s and showed that they admit a so-called polygon representation. In this talk I will show new algorithmically useful properties of this representation and demonstrate two applications in approximating network design problems.

Abstract

Approximate integer programming is the following: For a given convex body K, either determine whether K is lattice-point free, or find an integer point in K scaled by 2 from its center of gravity. Approximate integer programming can be solved in time roughly 2^n while the fastest known methods for exact integer programming run in time roughly n^n. So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point in K can be found in time roughly 2^n, provided that the remainders of each component x_i mod 5(n+1) are given. The algorithm is based on a cutting-plane technique, iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a n^n algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (2012) that is considerably more involved. Our algorithm also relies on a new asymmetric approximate Caratheodory theorem that might be of interest on its own. Our second method concerns integer programming problems in equation-standard form with capacities u. We show that such a problem can be reduced to the solution of log(u_max)^n approximate integer programming problems.

Abstract

The Quickest Transshipment Problem is to route flow as quickly as possible from sources with supplies to sinks with demands in a network with capacities and transit times on the arcs. It is of fundamental importance for numerous applications in areas such as logistics, traffic, evacuation, and finance. More than 25 years ago, Hoppe and Tardos presented the first (strongly) polynomial-time algorithm for this problem. Their approach, as well as subsequently derived algorithms with strongly polynomial running time, is hardly practical as it relies on parametric submodular function minimization via Megiddo's parametric search. We present considerably faster algorithms for the Quickest Transshipment Problem that instead employ a subtle extension of the Discrete Newton Method. This improves the previously best known running time of $\tilde{O}(m^4k^{14})$ to $\tilde O(m^2k^5+m^3k^3+m^3n)$, where $n$ is the number of nodes, $m$ the number of arcs, and $k$ the number of source and sink nodes. Furthermore, we show how to compute integral quickest transshipments in $\tilde O(m^2k^6+m^3k^4+m^3n)$ time.

This is joint work with Miriam Schlöter and Khai Van Tran.

Abstract

In 1978, Mader discovered a min-max theorem on the number of openly disjoint paths between terminals. Sadli and Sebo (2000) showed that the set of integer vectors in that appear as degree sequences of openly disjoint paths forms a jump system. In this talk, we describe an alternative proof of this fact by using a reduction to matroid matching, which was originally observed by Lovasz (1980). In addition, we show that a function on this jump system determined by the minimum total length of openly disjoint paths enjoys the M-convexity introduced by Murota (2006).

Abstract

In the strong form of the thin tree conjecture, formulated by Goddyn in 2004, we are given a k-edge-connected graph and wish to find a tree containing at most an O(1/k) fraction of the edges across every cut. This conjecture, if true, has a variety of implications in a number of areas such as graph theory and approximation algorithms. A natural relaxation of this problem is to find a tree with at most O(1/k) edges across a fixed collection of cuts, instead of all cuts. Via a simple reduction technique followed by iterative relaxation, we show that the thin tree conjecture is true for laminar families of cuts, resolving an open question of Olver and Zenklusen from 2013. Joint work with Nathan Klein.

Abstract

Maximizing a monotone k-submodular function subject to cardinality constraints is a general model for several applications ranging from influence maximization with multiple products to sensor placement with multiple sensor types and online ad allocation. Due to the large problem scale in many applications and the online nature of ad allocation, a need arises for algorithms that process elements in a streaming fashion and possibly make online decisions. In this talk, we present a streaming algorithm for maximizing a monotone k-submodular function subject to a per-coordinate cardinality constraint attaining an approximation guarantee close to the state of the art guarantee in the offline setting. We also give a variant of the algorithm that is able to leverage machine learning predictions.

Abstract

We consider the matroid prophet inequality problem. This problem has been extensively studied in the case of adaptive mechanisms. In particular, there is a tight 2-competitive mechanism for all matroids. However, it is not known what classes of matroids admit non-adaptive mechanisms with constant guarantee. Recently, it was shown that there are constant-competitive non-adaptive mechanisms for graphic matroids. In this talk, we show that various known classes of matroids admit constant-competitive non-adaptive mechanisms.

Abstract

The Nash social welfare (NSW) problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents’ valuations. This is a common objective for fair division, representing a balanced tradeoff between the often conflicting requirements of fairness and efficiency. The problem is NP-complete already for additive valuation functions. We present a simple, deterministic 4-approximation algorithm for the Nash Social Welfare problem under the general class submodular valuation functions. The previous best approximation factor was 380 via a randomized algorithm. We also consider the asymmetric variant of the problem where the objective is to maximize the weighted geometric mean of agents’ valuations, and give a (α+2)e-approximation, where α is the ratio between largest weight and the average weight. This is joint work with Jugal Garg, Edin Husić, Wenzheng Li, and Jan Vondrák.

Abstract

The increase of electric vehicle (EV) adoption in recent years has correspondingly increased the importance of providing adequate charging infrastructure for EV users. For a charging service provider, the fundamental question is to determine the optimal location and sizing of charging stations with respect to a given objective and subject to budget and other practical constraints. One possible objective is to maximize EV adoption as part of a public policy on electric transportation. Alternatively, the objective may be to maximize the profit gained from providing this service, in which case the price of charging is also to be optimized. These problems are fundamentally combinatorial and frequently formulated using mixed-integer linear optimization. In this talk, the focus will be on the use of bilevel optimization in this area, in particular to more accurately capture the interactions between the charging service provider and the EV users.