Combinatorics and Optimization
Institute for Computational and Experimental Research in Mathematics (ICERM)
March 27, 2023  March 31, 2023
Your device timezone is . Do you want to view schedules in or choose a custom timezone?
Monday, March 27, 2023

8:30  8:50 am EDTCheck In11th Floor Collaborative Space

8:50  9:00 am EDTWelcome11th Floor Lecture Hall
 Brendan Hassett, ICERM/Brown University

9:00  9:45 am EDTInterior point methods are not worse than Simplex11th Floor Lecture Hall
 Speaker
 Daniel Dadush, Centrum Wiskunde & Informatica
 Session Chair
 Jesús De Loera, University of California, Davis
Abstract
Whereas interior point methods provide polynomialtime linear programming algorithms, the running time bounds depend on bitcomplexity 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 polynomialtime pathfollowing interior point method where the number of iterations also admits a combinatorial upper bound O(2^n n^{1.5} log n) for an nvariable 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 pathfollowing 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 piecewiselinear 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). 
10:00  10:30 am EDTCoffee Break11th Floor Collaborative Space

10:30  11:15 am EDTPartitioning over submodular structures11th Floor Lecture Hall
 Speaker
 Karthekeyan Chandrasekaran, University of Illinois UrbanaChampaign
 Session Chair
 Jesús De Loera, University of California, Davis
Abstract
In submodular kpartitioning 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 nonempty parts so as to minimize certain natural objectives of interest. Submodular kpartitioning generalizes partitioning problems over several interesting structures including graphs and hypergraphs. The case of 2partitioning corresponds to the classic and wellstudied submodular minimization problem which is polynomialtime solvable. In this talk, I will outline recent progress towards polynomialtime solvability of submodular kpartitioning for fixed constant integers k >= 3.

11:30 am  12:15 pm EDTThe Polyhedral Structure of Graphical Designs11th Floor Lecture Hall
 Speaker
 Catherine Babecki, University of Washington, Seattle
 Session Chair
 Jesús De Loera, University of California, Davis
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.

12:30  2:30 pm EDTLunch/Free Time

2:30  3:15 pm EDTTwo New Algorithms for Set Covering11th Floor Lecture Hall
 Speaker
 Anupam Gupta, Carnegie Mellon University
 Session Chair
 Yuri Faenza, Columbia University
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 NPhard to approximate to better than (ln n). Moreover we know matching algorithms which are achieved by both greedy and relaxandround 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 learningbased 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.

3:30  4:00 pm EDTCoffee Break11th Floor Collaborative Space

4:00  4:45 pm EDTAlternating Linear Minimization: Revisiting von Neumann’s alternating projections11th Floor Lecture Hall
 Speaker
 Sebastian Pokutta, Zuse Institute Berlin (ZIB)
 Session Chair
 Yuri Faenza, Columbia University
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.

5:00  6:30 pm EDTReception11th Floor Collaborative Space
Tuesday, March 28, 2023

9:00  9:45 am EDTReusing Cuts in Iterative Projections over Submodular Polytopes11th Floor Lecture Hall
 Speaker
 Swati Gupta, Georgia Tech
 Session Chair
 Karthekeyan Chandrasekaran, University of Illinois UrbanaChampaign
Abstract
Optimization algorithms such as projected Newton's method, FISTA, mirror descent and its variants enjoy nearoptimal 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 FrankWolfe). Motivated by this tradeoff in runtime v/s convergence rates, we consider iterative projections of closeby points over widelyprevalent 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 awaystep FrankWolfe algorithm to use this information and enable early termination.

10:00  10:30 am EDTCoffee Break11th Floor Collaborative Space

10:30  11:15 am EDTClique Trees and Disjunctive Constraints11th Floor Lecture Hall
 Speaker
 Illya Hicks, Rice University
 Session Chair
 Karthekeyan Chandrasekaran, University of Illinois UrbanaChampaign
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 mixedinteger 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.

11:30 am  12:15 pm EDTLower Bounds on the Complexity of MixedInteger Programs for Stable Set and Knapsack11th Floor Lecture Hall
 Speaker
 Stefan Weltge, Technical University of Munich
 Session Chair
 Karthekeyan Chandrasekaran, University of Illinois UrbanaChampaign
Abstract
Standard mixedinteger programming formulations for the stable set problem on nnode graphs require n integer variables. We prove that this is almost optimal: We give an explicit family of stable set polytopes of nnode graphs for which every polynomialsize formulation requires Ω(n / log^2 n) integer variables. By a polyhedral reduction we obtain an analogous result for nitem 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 nnode graphs is 2^(Ω(n / log n)). We show that the same bound holds for ɛ/napproximations 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 KarchmerWigderson games. This is joint work with Jamico Schade and Makrand Sinha.

12:30  2:00 pm EDTNetworking LunchLunch/Free Time  11th Floor Collaborative Space

2:00  2:45 pm EDTArc connectivity and submodular flows in digraphs11th Floor Lecture Hall
 Speaker
 Ahmad Abdi, London School of Economics
 Session Chair
 Steffen Borgwardt, University of Colorado Denver
Abstract
Given a digraph D, and an integer k>=1, a karcconnected flip is an arc subset whose reversal makes the digraph (strongly) karcconnected. The main result of this work introduces a sufficient condition for the existence of a karcconnected 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 tedgeconnected for some integer t>=2, there exists a decomposition of the arc set into a karcconnected flip and a (tk)dijoin, for any integer k such that 1<=k<=t/2. This extends NashWilliams’ 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.

3:00  3:45 pm EDTSmoothed Analysis of the Simplex Method11th Floor Lecture Hall
 Speaker
 Sophie Huiberts, Columbia University
 Session Chair
 Steffen Borgwardt, University of Colorado Denver
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.

4:00  4:30 pm EDTCoffee Break11th Floor Collaborative Space

4:30  6:00 pm EDT
Wednesday, March 29, 2023

9:00  9:45 am EDTDegree Sequence Optimization and Sparse Integer Programming11th Floor Lecture Hall
 Speaker
 Shmuel Onn, Technion  Israel Institute of Technology
 Session Chair
 Antoine Deza, McMaster University
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.

10:00  10:30 am EDTCoffee Break11th Floor Collaborative Space

10:30  11:15 am EDTAlgorithmic, combinatorial, and geometric aspects of linear optimization11th Floor Lecture Hall
 Speaker
 Lionel Pournin, University of Paris 13
 Session Chair
 Antoine Deza, McMaster University
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 worstcase 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.

11:30 am  12:15 pm EDTThe Exact Bipartite Matching Polytope Has Exponential Extension Complexity11th Floor Lecture Hall
 Speaker
 Ola Svensson, EPFL
 Session Chair
 Antoine Deza, McMaster University
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 polylogarithmictime parallel algorithm to solve this problem, dating back to the eighties, but no deterministic polynomialtime 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 subexponentialsized linear program that can describe the convex hull of exact matchings in bipartite graphs. In fact, we prove something stronger, that there is no subexponentialsized 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 
12:15  12:30 pm EDTGroup Photo (Immediately After Talk)11th Floor Lecture Hall

12:30  2:30 pm EDTLunch/Free Time

2:30  3:15 pm EDTApproximating Weighted Connectivity Augmentation Below Factor 211th Floor Lecture Hall
 Speaker
 Rico Zenklusen, ETH Zurich
 Session Chair
 Sophie Huiberts, Columbia University
Abstract
The Weighted Connectivity Augmentation Problem (WCAP) asks to augment the edgeconnectivity 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 betterthan2 approximation has been known, whereas 2approximations can easily be obtained through a variety of wellknown 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.

3:30  4:00 pm EDTCoffee Break11th Floor Collaborative Space

4:00  4:45 pm EDTUnit and distinct distances in typical norms11th Floor Lecture Hall
 Speaker
 Lisa Sauermann, MIT
 Session Chair
 Sophie Huiberts, Columbia University
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 socalled 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.
Thursday, March 30, 2023

9:00  9:45 am EDTUnderstanding graphs locally11th Floor Lecture Hall
 Speaker
 Annie Raymond, University of Massachusetts, Amherst
 Session Chair
 Mohit Singh, Georgia Tech
Abstract
Graphs are ubiquitous in modern applicationsincluding 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.

10:00  10:30 am EDTCoffee Break11th Floor Collaborative Space

10:30  11:15 am EDTUntangling near minimum cuts with applications in network design11th Floor Lecture Hall
 Speaker
 Nathan Klein, University of Washington
 Session Chair
 Mohit Singh, Georgia Tech
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 socalled polygon representation. In this talk I will show new algorithmically useful properties of this representation and demonstrate two applications in approximating network design problems.

11:30 am  12:15 pm EDTThe Subspace Flatness Conjecture and Faster Integer Programming11th Floor Lecture Hall
 Speaker
 Thomas Rothvoss, University of Washington
 Session Chair
 Mohit Singh, Georgia Tech
Abstract
In a seminal paper, Kannan and Lov\'asz (1988) considered a quantity $\mu_{KL}(\Lambda,K)$ which denotes the best volumebased lower bound on the covering radius $\mu(\Lambda,K)$ of a convex body $K$ with respect to a lattice $\Lambda$. Kannan and Lov\'asz proved that $\mu(\Lambda,K) \leq n \cdot \mu_{KL}(\Lambda,K)$ and the Subspace Flatness Conjecture by Dadush (2012) claims a $O(\log n)$ factor suffices, which would match the lower bound from the work of Kannan and Lov\'asz. We settle this conjecture up to a constant in the exponent by proving that $\mu(\Lambda,K) \leq O(\log^{7}(n)) \cdot \mu_{KL} (\Lambda,K)$. Our proof is based on the Reverse Minkowski Theorem due to Regev and StephensDavidowitz (2017). Following the work of Dadush (2012, 2019), we obtain a $(\log n)^{O(n)}$time randomized algorithm to solve integer programs in $n$ variables. Another implication of our main result is a nearoptimal flatness constant of $O(n \log^{8}(n))$. This is joint work with Victor Reis.

12:30  2:30 pm EDTNetworking LunchLunch/Free Time  11th Floor Collaborative Space

2:30  3:15 pm EDTTransshipments over time, submodular functions, and discrete Newton11th Floor Lecture Hall
 Speaker
 Martin Skutella, TU Berlin
 Session Chair
 Annie Raymond, University of Massachusetts, Amherst
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) polynomialtime 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. 
3:30  4:00 pm EDTCoffee Break11th Floor Collaborative Space

4:00  4:45 pm EDTOpenly Disjoint Paths, Jump Systems, and Discrete Convexity11th Floor Lecture Hall
 Speaker
 Satoru Iwata, University of Tokyo
 Session Chair
 Annie Raymond, University of Massachusetts, Amherst
Abstract
In 1978, Mader discovered a minmax 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 Mconvexity introduced by Murota (2006).
Friday, March 31, 2023

9:00  9:45 am EDTThin trees for laminar families11th Floor Lecture Hall
 Speaker
 Neil Olver, London School of Economics
 Session Chair
 Britta Peis, RWTH Aachen University
Abstract
In the strong form of the thin tree conjecture, formulated by Goddyn in 2004, we are given a kedgeconnected 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.

10:00  10:30 am EDTCoffee Break11th Floor Collaborative Space

10:30  11:15 am EDTStreaming algorithms for ksubmodular maximization and ad allocation11th Floor Lecture Hall
 Speaker
 Alina Ene, Boston University
 Session Chair
 Britta Peis, RWTH Aachen University
Abstract
Maximizing a monotone ksubmodular 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 ksubmodular function subject to a percoordinate 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.

11:30 am  12:15 pm EDTNonAdaptive Matroid Prophet Inequalities11th Floor Lecture Hall
 Speaker
 Kanstantsin Pashkovich, University of Waterloo
 Session Chair
 Britta Peis, RWTH Aachen University
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 2competitive mechanism for all matroids. However, it is not known what classes of matroids admit nonadaptive mechanisms with constant guarantee. Recently, it was shown that there are constantcompetitive nonadaptive mechanisms for graphic matroids. In this talk, we show that various known classes of matroids admit constantcompetitive nonadaptive mechanisms.

12:30  2:30 pm EDTLunch/Free Time

2:30  3:15 pm EDTApproximating Nash Social Welfare for Submodular Valuations11th Floor Lecture Hall
 Speaker
 László Végh, London School of Economics
 Session Chair
 Gerard Cornuejols, Carnegie Mellon University
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 NPcomplete already for additive valuation functions. We present a simple, deterministic 4approximation 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)eapproximation, 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.

3:30  4:15 pm EDTOptimal Deployment of Electric Vehicle Charging Infrastructure via Bilevel Optimization11th Floor Lecture Hall
 Speaker
 Miguel Anjos, University of Edinburgh
 Session Chair
 Gerard Cornuejols, Carnegie Mellon University
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 mixedinteger 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.

4:30  5:00 pm EDTCoffee Break11th Floor Collaborative Space
All event times are listed in ICERM local time in Providence, RI (Eastern Standard Time / UTC5).
All event times are listed in .
ICERM local time in Providence, RI is Eastern Standard Time (UTC5). Would you like to switch back to ICERM time or choose a different custom timezone?
Schedule Timezone Updated