14th Cargese Workshop on Combinatorial Optimization

Topic

This edition's workshop will focus on "Fast Algorithms for Linear Programming and their Combinatorial Applications".

Distinguished speakers

• Rasmus Kyng (ETH): Fast Flow Algorithms: Combinatorial Interior Point Methods and Graph Data Structures.
• Haihao Lu (MIT): An Overview of GPU-Based First-Order Methods for Linear Programming and Beyond.
• Bento Natura (Columbia): The Combinatorics of Interior Point Methods for Linear Programming.

Talks

Lectures

• Rasmus Kyng – Fast Flow Algorithms: Combinatorial Interior Point Methods and Graph Data Structures

  My first lecture will be on the Combinatorial Interior Point Method (CIPM) for solving linear programs, and the second lecture on Min-Ratio Cycle Data Structures that are used to implement the CIPM for minimum-cost flow. The third lecture will be on the Dual/Cut CIPM, data structures for cut-updates, and partially dynamic flow problems.
  An additional (optional) tutorial session on "Dynamic Edge and Vertex Distance Sparsification", building on the content of this lecture series, will be given by Aurelio Sulser and Simon Meierhans on Tuesday from 15:15pm-16:15pm.

• Haihao Lu – An Overview of GPU-Based First-Order Methods for Linear Programming and Beyond

  The rapid advancement of GPU computing has transformed numerous fields, yet its impact on mathematical programming, including linear programming (LP) and beyond, remains an actively evolving research area. In this lecture, we aim to provide an overview of recent developments in GPU-accelerated solvers, with a primary focus on first-order methods (FOMs) for LP and their extensions. We begin by outlining the fundamental differences between CPU and GPU architectures and presenting a numerical study on the speedup achieved by GPUs over CPUs for key numerical linear algebra operations that serve as bottlenecks for various optimization algorithms. Next, we discuss how to design FOMs for problems like LP from the ground up. We then introduce the newly developed LP solvers PDLP, cuPDLP, and cuPDLPx, describing practical enhancements that improve numerical performance, along with a summary of numerical studies comparing cuPDLPx to commercial solvers. This is followed by an in-depth discussion of the theoretical foundations of the primal-dual hybrid gradient (PDHG) method, which serves as the base algorithm for PDLP. We present a simplified and unified perspective on PDHG, including a basic convergence analysis, and explore its connections with non-expansive operators, leading to a principal understanding of the algorithm. Furthermore, we examine the sharpness property of LP, a key characteristic that enables the linear convergence of PDHG. We discuss optimal linear convergence, infeasibility detection, and Halpern acceleration, followed by a summary of condition-number-based analyses. Finally, we review recent progress in GPU-based solvers for quadratic and semidefinite programming, highlighting broader advancements in large-scale optimization with GPUs.
  The first lecture will be based on the following survey paper joint with Jinwen Yang.

• Bento Natura – The Combinatorics of Interior Point Methods for Linear Programming

  This tutorial introduces Straight Line Complexity, a geometric quantity that characterizes the number of iterations required by specialized Interior Point Methods to solve Linear Programs exactly. We analyze this complexity measure for several key classes of LPs, including Minimum Cost Flows, Markov Decision Processes, and two-variable-per-inequality systems, illustrating its role in combinatorial optimization. We will also touch on algorithmic aspects and initialization techniques that preserve combinatorial structure.

Contributed Talks

• Eleon Bach – Optimal Smoothed Analysis of the Simplex Method

  Smoothed analysis is a method for analysing the performance of algorithms, used especially for those algorithms whose running time in practice is significantly better than what can be proven through worst-case analysis and which have significant structure such that average case analysis remains inconclusive. Given an arbitrary linear program with $d$ variables and $n$ inequality constraints, we prove that there exists a simplex method whose smoothed complexity is upper bounded by $O(\sigma^{-1/2} d^{11/4} \log(n)^{7/4})$ pivot steps. Furthermore, we prove a matching high-probability lower bound of $\Omega( \sigma^{-1/2} d^{1/2}\ln(4/\sigma)^{-1/4})$ on the combinatorial diameter of the feasible polyhedron after smoothing, on instances using $n = \lfloor (4/\sigma)^d \rfloor$ inequality constraints. This lower bound indicates that our algorithm has optimal noise dependence among all simplex methods, up to polylogarithmic factors. In this talk we will discuss the algorithmic improvements that we used for the above new upper bound.
  This is joint work with Sophie Huiberts.

• Alexander Black – Circuit Augmentation in Fixed Dimension

  Circuit augmentation algorithms for linear programming are generalizations of the simplex method that have garnered recent attention due to being both combinatorial and having polynomial run-time guarantees. Circuit augmentation follows a sequence of discrete steps along the boundary of a polytope until converging on the optimum by following a path along so-called circuit directions called a circuit walk. However, the choices of circuit walks are numerous, and a key bottleneck for studying circuit augmentation schemes is the computational problem of finding short circuit walks. In this talk, I will show that finding a shortest circuit walk is NP-Hard already for polygons, and as a consequence of our proof, finding an $O(n^{1-\epsilon})$-approximation of a shortest circuit walk is NP-Hard for any $\epsilon > 0$ for a polyhedron defined by n inequalities.
  This is based on joint work with Christian Nöbel and Raphael Steiner.

• Adrian Vladu – Breaking the Barrier of Self-Concordant Barriers: Faster Interior Point Methods for M-Matrices

  We study two fundamental optimization problems: (1) scaling a symmetric positive definite matrix by a positive diagonal matrix so that the resulting matrix has row and column sums equal to 1; and (2) minimizing a quadratic function subject to hard non-negativity constraints. Both problems lend themselves to efficient algorithms based on interior point methods (IPMs). For general instances, standard self-concordance theory places a limit on the iteration complexity of these methods at $\tilde{O}(n^{1/2})$, where $n$ denotes the matrix dimension. We show via an amortized analysis that, when the input matrix is an M-matrix, an IPM with adaptive step sizes solves both problems in only $\tilde{O}(n^{1/3})$ iterations. As a corollary, using fast Laplacian solvers, we obtain an L2 flow diffusion algorithm with depth $\tilde{O}(n^{1/3})$ and work $\tilde{O}(n^{1/3} {\rm NNZ})$. This result marks a significant instance in which a standard log-barrier IPM permits provably fewer than $O(n^{1/2})$ iterations.
  Appears in STOC 2025. Full version available here.

• Yang P. Liu - Improved Algorithms for Estimating the Spanning Tree Count

  We study the problem of estimating the number of spanning trees in an undirected graph G up to multiplicative $(1+\epsilon)$ error, and give an algorithm with running time $m^{1.5}/\epsilon$, improving over previous works in sparse graphs. To obtain the results, we take a different approach than previous works, which leveraged Schur complement determinant sparsifiers, and instead use tools such as the localization of electrical flows.
  Joint work with Richard Peng and Junzhao Yang.

• Shunhua Jiang - Generalized Flow in Nearly-linear Time on Moderately Dense Graphs

  In this talk, we consider generalized flow problems where there is an $m$-edge $n$-node directed graph $G = (V,E)$ and each edge $e \in E$ has a loss factor $\gamma_e >0$ governing whether the flow is increased or decreased as it crosses edge $e$. We provide a randomized $\tilde{O}( (m + n^{1.5}) \cdot \mathrm{poly} \log(\frac{W}{\delta}))$ time algorithm for generalized maximum flow and generalized minimum cost flow in this setting where $\delta$ is the target accuracy and $W$ is the maximum of all costs, capacities, and loss factors and their inverses. This improves upon the previous state-of-the-art $\tilde{O}(m \sqrt{n} \cdot \log^2(\frac{W}{\delta}) )$ time algorithm, obtained by combining the algorithm of [Daitch-Spielman 2008] with techniques from [Lee-Sidford 2014]. To obtain this result we provide new dynamic data structures and spectral results regarding the matrices associated to generalized flows and apply them through the interior point method framework of [Brand-Lee-Liu-Saranurak-Sidford-Song-Wang 2021].
  Based on joint work with Michael Kapralov, Lawrence Li, and Aaron Sidford.

• Sorrachai Yingchareonthawornchai – Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness

  We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph n vertices and m edges in $\widehat O(mn)$ time. This breaks the long-standing $\widehat \Omega(n^{4})$-time barrier in dense graphs, achievable by trivially computing all-pairs maximum flows. Up to subpolynomial factors, we match the fastest randomized $\tilde O(mn)$-time algorithm by [Henzinger, Rao, and Gabow'00], and affirmatively answer the question by [Gabow'06] whether deterministic $O(mn)$-time algorithms exist even for unweighted graphs. Our algorithm works in directed graphs, too. In unweighted undirected graphs, we present a faster deterministic $\widehat O(m\kappa)$-time algorithm where $\kappa \le n$ is the size of the global minimum vertex cut. For a moderate value of $\kappa$, this strictly improves upon all previous deterministic algorithms in unweighted graphs with running time $\widehat O(m(n+\kappa^{2}))$ [Even'75], $\widehat O(m(n+\kappa\sqrt{n}))$ [Gabow'06], and $\widehat O(m2^{O(\kappa^{2})})$ [Saranurak and Yingchareonthawornchai'22]. Recently, a linear-time algorithm has been shown by [Korhonen'24] for very small $\kappa$. Our approach applies the common-neighborhood clustering, recently introduced by [Blikstad, Jiang, Mukhopadhyay, Yingchareonthawornchai'25], in novel ways, e.g., on top of weighted graphs and on top of vertex-expander decomposition. We also exploit pseudorandom objects often used in computational complexity communities, including crossing families based on dispersers from [Wigderson and Zuckerman'99; TaShma, Umans and Zuckerman'01] and selectors based on linear lossless condensers [Guruswwami, Umans and Vadhan'09; Cheraghchi'11]. To our knowledge, this is the first application of selectors in graph algorithms.
  Joint work with Yonggang Jiang, Chaitanya Nalam and Thatchaphol Saranurak.

• Aaron Sidford - The Complexity of Solving Matrix Games

  Matrix games are a fundamental class of bilinear optimization problems and perhaps some of the simplest non-trivial minimax optimization problems. Nevertheless, matrix games are pervasive and encompass well-studied, prominent algorithmic challenges including linear programming and finding a maximum-margin linear classifier. In this talk I will survey recent advances in understanding the complexity of approximately solving matrix games. In addition, this talk will introduce recent, new efficient algorithms for efficiently solving certain matrix games developed in joint work with Ishani Karmarkar and Liam O'Carroll.
  

• Robert M. Freund - The Role of Level-Set Geometry on the Performance of PDHG for Conic Convex Optimization

  We consider solving huge-scale instances of (convex) conic linear optimization problems, at the scale where matrix-factorization-free methods are attractive or necessary. The restarted primal-dual hybrid gradient method (rPDHG)—with heuristic enhancements and GPU implementation—has been very successful in solving these huge-scale LP problems; however, its performance can have substantial variance, and an intuitive understanding of the drivers of its performance has been lacking. We present a new theoretical analysis of rPDHG for general (convex) conic linear optimization and for LP as a special case thereof. We show a relationship between geometric measures of the primal-dual (sub-)level sets and the convergence rate of rPDHG. We then specialize our results to the case of LP with unique optima. Under unique optima, we present an iteration bound that is “accessible” in the sense that computing the bound is no more difficult than computing the optimal solution itself. This furthermore enables an analysis of the “two-stage performance” of rPDHG: we present a bound on the number of iterations of the first stage (which identifies the optimal basis), and also a bound on the second stage (which computes a nearly-optimal solution). Furthermore, computational tests mostly confirm the tightness of these iteration bounds. We also show a reciprocal relation between the iteration bounds and three equivalent types of condition measures: (i) stability under data perturbation, (ii) proximity to multiple optima, and (iii) the LP sharpness of the instance.
  This is joint work with Zikai Xiong.

• Tommaso d'Orsi - Eigenspace Enumeration and Sparsest Cut on low degree Abelian Cayley graphs

  We present a novel algorithm for Sparsest Cut that combines eigenspace enumeration with a simple linear program. The runtime of our algorithm is parametrized by a quantity that we call the solution dimension: the smallest k such that the subspace spanned by the first k Laplacian eigenvectors contains all but a small fraction of the sparsest cut. Our algorithm matches the guarantees of prior methods based on the threshold-rank paradigm, while also extending beyond them. To illustrate this, we study its performance on low degree Cayley graphs over Abelian groups -- canonical examples of graphs with poor expansion properties. We prove that low-degree Abelian Cayley graphs have small solution dimension, yielding an efficient algorithm that computes a constant approximation to the uniform Sparsest Cut. Along the way to bounding the solution dimension of Abelian Cayley graphs, we prove tight bounds on the metric entropy of approximate sparsest cuts and the multiplicity of the smallest non-trivial eigenvalue.

• Jiaye Wei - Robustness of Matching: Backup Nodes Problem

  We study the following problem on the robustness of matching. Consider a bipartite graph with parts $A$ and $B$. We assume that $B$ has a larger size than $A$ and that the graph has an $A$-perfect matching. The goal is to find an $A$-perfect matching such that the number of nodes in $A$ which has a neighbor in the unsaturated nodes of $B$, is maximized; in other words, we want the maximum number of $A$ nodes to have “backup nodes”. A related problem is studied in the setting of second bidder auctions with binary bids by Azar, Birnbaum, Karlin, and Nguyen in 2009. In that problem, the condition of finding a perfect matching is relaxed but every $A$ nodes in the matching is required to have backup nodes. In this talk, I will first explain a tight $(1-1/e)$ approximation for the general Backup Nodes problem via submodular maximization. I will also introduce the results for the degree-constrained case, including a polynomial-time exact algorithm for $(d,2)$-regular graphs and the APX-hardness for graphs with small degrees.
  This is joint work with Rom Pinchasi, Neta Singer, and Lukas Vogl.

• Katharina Eickhoff - On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem

  In train routing, the headway is the minimum distance that must be maintained between successive trains for safety and robustness. We introduce a model for train routing that requires a fixed headway to be maintained between trains, and study the problem of minimizing the makespan, i.e., the arrival time of the last train, in a single-source single-sink network. For this problem, we first show that there exists an optimal solution where trains move in convoys – that is, the optimal paths for any two trains are either the same or are arc-disjoint. While min-max disjoint paths inherits a strong inapproximability result on directed acyclic graphs from the multi-level bottleneck assignment problem, we show that a natural greedy composition approach yields a logarithmic approximation in the number of disjoint paths for series-parallel graphs. We also present an alternative analysis of this approach that yields a guarantee depending on how often the decomposition tree of the series-parallel graph alternates between series and parallel compositions on any root-leaf path.
  This is joint work with Umang Bhaskar, Lennart Kauther, Jannik Matuschke, Britta Peis and Laura Vargas Koch.

• Sarah Morell - Unsplittable Transshipments

  We consider an arc-capacitated directed graph $D=(V,A)$, where each node $v$ is associated with a rational balance value $b(v)$. Nodes with negative balance values are referred to as sources, while those with positive balance values are called sinks. A feasible $b$-transshipment is a flow that routes the total supply from the sources to the sinks through the digraph $D$, while respecting the given arc capacity constraints and satisfying the balance requirements at each node. An unsplittable $b$-transshipment additionally requires that the flow from each specific source to each sink is routed along at most one path. Given a feasible $b$-transshipment, our objective is to compute an unsplittable $b$-transshipment without exceeding the arc capacities by more than the maximum balance value. This problem generalizes the well-studied single source unsplittable flow problem, introduced by Kleinberg in 1996. In a seminal paper published 25 years ago, Dinitz, Garg and Goemans proved that, given an instance of the single source unsplittable flow problem, any feasible flow can be transformed into an unsplittable one without exceeding the arc capacities by more than the maximum demand value. In this talk, we present an adaptation of the Dinitz-Garg-Goemans algorithm to the more general setting of unsplittable transshipments. More precisely, we show how, given a feasible $b$-transshipment, one can efficiently compute an unsplittable $b$-transshipment while ensuring that no arc capacity is exceeded by more than the maximum balance value.
  This is joint work with Srinwanti Debgupta and Martin Skutella.

• Zhuan Khye Koh - Approximating the Held–Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth

  In this talk, I will present a nearly linear work parallel approximation scheme for the Held–Karp bound for metric TSP. Given an edge-weighted graph G with $m$ edges and $\epsilon > 0$, it returns a $(1+\epsilon)$-approximation to the Held–Karp bound with high probability, in $\tilde{O}(m/\epsilon^4)$ work and $\tilde{O}(1/\epsilon^4)$ depth.
  Joint work with Omri Weinstein and Sorrachai Yingchareonthawornchai.

• Tamás Schwartz - Couplings and Tensor Products of Matroids and Submodular Functions

  The tensor product of two matroids is a natural extension of the tensor product from linear algebra. However, Las Vergnas showed that two matroids do not necessarily admit such a product. Inspired by the concept of coupling in probability theory, we introduce the notion of coupling for matroids, and more generally for submodular set functions. This operation relaxes the tensor product and, in contrast, always exists: any two matroids or submodular functions admit a coupling. We further reveal a close connection between the existence of tensor products and matroid representability over skew fields, which in turn leads to new linear rank inequalities. Based on joint works with Kristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász, Balázs Maga, and Carles Padró.

• László Végh - Matroids are Equitable

  We show that if the ground set of a matroid can be partitioned into $k \geq 2$ bases, then for any given subset $S$ of the ground set, there is a partition into $k$ bases such that the sizes of the intersections of the bases with S may differ by at most one. This settles the matroid equitability conjecture by Fekete and Szabó from 2011 in the affirmative. We also present results on near-equal splittings of two disjoint set, and derive applications to matroid constrained fair division problems. This is joint work with Hannaneh Akrami and Roshan Raj.

Participants

Previous editions

A list of all previous editions can be found here.

Credits

Logo designed by Giuseppe Musolino. Website hosted at GitHub Pages. Layout based on skeleton using AmatiSC font.