Schedule

Full talks

A Framework for k-Median and k-Means Approximation 

Fabrizio Grandoni (IDSIA, USI-SUPSI) 

The connected min-sum radii problem

Hyung-Chan An (Yonsei University) 

In this talk, we consider the study for the connected minimum sum of radii problem. In this problem, we are given as input a metric defined on a set of facilities and clients, along with some cost parameters. The objective is to open a subset of facilities, assign every client to an open facilitiy, and connect open facilities using a Steiner tree so that the weighted (by cost parameters) sum of the maximum assignment distance of each facility and the Steiner tree cost is minimized. This problem introduces the min-sum radii objective, an objective function that is widely considered in the clustering literature, to the connected facility location problem, a well-studied network design/clustering problem. This problem is useful in communication network design on a shared medium, or energy optimization of mobile wireless chargers.

Joint work with Mong-Jen Kao.

Submodular k-Partitioning via Principal Partition Sequence

Karthik Chandrasekaran (UIUC) 

In the submodular k-partitioning problem, the input is a submodular function along with an integer k. The goal is to partition the ground set into k non-empty parts in order to minimize the sum of the function value of the parts. Several partitioning/clustering problems over graphs, hypergraphs, and matroids can be cast as special cases of submodular k-partition, and consequently, the approximability of the problem for three families of submodular functions is of particular interest – symmetric, monotone, and posimodular submodular functions. In this talk, I will outline the principal partition sequence-based approach to approximating submodular k-partitioning for these three families. A generalization of the problem---termed {s,t}-separating submodular k-partition---requires the k-partition to also separate two specified elements s and t. I will sketch the theory of {s,t}-separating principal partition sequence, and its application to approximating {s,t}-separating submodular k-partition.

Lightning talks

A Polylogarithmic Approximation for Buy-at-Bulk with Protection

Rhea Jain (UIUC) 

The nonuniform multicommodity buy-at-bulk problem is a classical and practical problem in network design, where the goal is to construct a low-cost network that supports multicommodity flow between node pairs. The cost of purchasing capacity on an edge is given by a sub-additive function, thus capturing settings that exhibit economies of scale. In the fault-tolerant setting, the goal is to protect against node or edge failures by sending demand flow along disjoint paths. Despite substantial work addressing various special cases, no nontrivial approximation algorithm was known for fault-tolerant nonuniform buy-at-bulk, even for protecting against a single edge failure (k=2)! 

In this talk, I will present recent work breaking this long standing barrier, that yields the first polylogarithmic approximation algorithm for fault-tolerant nonuniform buy-at-bulk that protects against a single node failure. 

A Better-Than-5/4 Approximation for Two-Edge Connectivity

Alex Lindermayr (Simons Institute) 

The $2$-Edge-Connected Spanning Subgraph problem (2ECSS) is among the most basic survivable network design problems: given an undirected and unweighted graph, the task is to find a spanning subgraph with the minimum number of edges that is 2-edge-connected (i.e., it remains connected after the removal of any single edge). 2ECSS is an NP-hard problem that has been extensively studied in the context of approximation algorithms. The best-known approximation ratio for 2ECSS prior to our work was $1.3+\varepsilon$, for any constant $\varepsilon>0$ [Garg, Grandoni, Jabal-Ameli'23; Kobayashi, Noguchi'23]. We first present a $5/4$-approximation algorithm, and also discuss how we can improve it slightly to $5/4 - \eta$ for some constant $\eta \geq 10^{-6}$.

A Better-Than-2 Approximation for the Directed Tree Augmentation Problem [arxiv]

Olha Silina (CMU) 

We introduce and study a directed analogue of the weighted Tree Augmentation Problem (WTAP). In the weighted Directed Tree Augmentation Problem (WDTAP), we are given an oriented tree T and a set of directed links L with positive costs. The goal is to select a minimum cost set of links which enters each fundamental dicut of T (cuts with one leaving and no entering tree arc). WDTAP captures the problem of covering a cross-free set family with directed links. WDTAP can be approximated to within a factor of 2 using standard techniques. We provide an improved (1.75+\eps)-approximation algorithm for WDTAP in the case where the links have bounded costs, a setting that has received significant attention for WTAP. Joint work with Meike Neuwohner and Michael Zlatin.

Online Resource Allocation with Concave, Diminishing-Returns Objectives

Kalen Patton (Georgia Tech) 

Optimal Online Bipartite Matching in Degree-2 Graphs

Arghya Chakraborty (TIFR) 

Weighted k-server problem admits an exponentially-competitive algorithm [arxiv]

Adithya Bijoy (NUS) 

In this talk, I will explain the recent progress of the weighted k-server problem.

Full talks

Optimal Stopping with a Predicted Prior [arxiv]

Zhiyi Huang (HKU) 

There are two major models of value uncertainty in the optimal stopping literature: the secretary model, which assumes no prior knowledge, and the prophet inequality model, which assumes full information about value distributions. In practice, decision makers often rely on machine-learned priors that may be erroneous. Motivated by this gap, we formulate the model of optimal stopping with a predicted prior to design algorithms that are both consistent, exploiting the prediction when accurate, and robust, retaining worst-case guarantees when it is not.

Existing secretary and prophet inequality algorithms are either pessimistic in consistency or not robust to misprediction. A randomized combination only interpolates their guarantees linearly. We show that a family of bi-criteria algorithms achieves improved consistency-robustness trade-offs, both for maximizing the expected accepted value and for maximizing the probability of accepting the maximum value. We further prove that for the latter objective, no algorithm can simultaneously match the best prophet inequality algorithm in consistency, and the best secretary algorithm in robustness.

The forbidden pattern method for graph sparsification

Greg Bodwin (University of Michigan) 

In theoretical computer science, one often wants to either (1) sparsify a graph while approximating its important structural properties (spanners, preservers, cut/flow/spectral sparsifiers, etc), or (2) edit a few edges of a graph while improving its important structural properties (hopsets, shortcut sets, low-diameter decompositions, etc). We will survey the "forbidden pattern method," a recently popular approach to these problems, which works by reducing to extremal Turán-type problems about forbidden patterns in some combinatorial structure.

Short talks

Edmonds++: Efficiently Coloring More Matroid Intersections [arxiv]

Michael Zlatin (Pomona College) 

Edmonds’ classical augmenting-path algorithm for matroid coloring shows us how to partition the elements of a single matroid into the fewest number of independent sets. But for matroid intersection coloring, no better than O(log n)-approximation is known in general. We give the first constant-factor approximation for coloring the intersection of a general matroid with one or more partition matroids. Leveraging the fact that many standard combinatorial matroids (graphic, laminar, transversal, gammoid) can be reduced to partition matroids at a loss of a factor of two in the chromatic number, we obtain constant approximations for all of these cases as well. 

Unsplittable Multicommodity Flow in Undirected Graphs

Nikhil Kumar (TIFR) 

We study multicommodity flows in undirected graphs, where we are given a supply graph G with edge capacities and a demand graph H that specifies source-sink pairs and their demands. An instance is feasible if all demands can be routed without violating the edge capacities. In the unsplittable version, each commodity must be routed along a single path. We investigate instances where the existence of a feasible (splittable) flow guarantees an unsplittable flow with only small capacity violations. We focus on instances where feasibility admits a natural characterization, i.e. the cut-condition: for every cut, the total demand crossing the cut is at most the total capacity of the edges crossing it. We study instances for which the cut-condition is sufficient, and we show that, for such cut-sufficient instances, there exists a polynomial-time–computable unsplittable flow that violates edge capacities only by a small amount. These are the first results of this kind for unsplittable multicommodity flows since the seminal work of Seymour, Schrijver, and Winkler on rings.

On the Capacitated Facility Location Problem and Multicommodity Flow Network Relaxation

Mong-Jen Kao (National Yang-Ming Chiao-Tung University) 

The study of classic covering and location problems under the concept of limited capacity supply has emerged in the past two decades and drawn a wide attention with a sequence of algorithmic results. In this talk I will introduce the capacitated facility location problem and relative algorithmic results.

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth [arxiv]

Sorrachai Yingchareonthawornchai (ETH Zurich) 

We present a nearly linear work parallel algorithm for approximating the Held-Karp bound for the Metric TSP problem. Given an edge-weighted undirected graph 

G=(V,E) on m edges and ϵ>0, it returns a (1+ϵ)-approximation to the Held-Karp bound with high probability, in Õ(m/ϵ^4) work and Õ(1/ϵ^4) depth. While a nearly linear time sequential algorithm was known for almost a decade (Chekuri and Quanrud'17), it was not known how to simultaneously achieve nearly linear work alongside polylogarithmic depth. Using a reduction by Chalermsook et al.'22, we also give a parallel algorithm for computing a (1+ϵ)-approximate fractional solution to the k-edge-connected spanning subgraph (kECSS) problem, with similar complexity.

To obtain these results, we introduce a notion of core-sequences for the parallel Multiplicative Weights Update (MWU) framework (Luby-Nisan'93, Young'01). For the Metric TSP and kECSS problems, core-sequences enable us to exploit the structure of approximate minimum cuts to reduce the cost per iteration and/or the number of iterations. The acceleration technique via core-sequences is generic and of independent interest. In particular, it improves the best-known iteration complexity of MWU algorithms for packing/covering LPs from polylog(nnz(A)) to polylogarithmic in the product of cardinalities of the core-sequence sets, where A is the constraint matrix of the LP. For certain implicitly defined LPs such as the kECSS LP, this yields an exponential improvement in depth.

Plenary talk

Breaking a Long-Standing Barrier: 2–ε Approximation for Steiner Forest

MohammadTaghi Hajiaghayi (University of Maryland) 

The Steiner Forest problem, also known as the Generalized Steiner Tree problem, is a fundamental optimization problem on edge-weighted graphs where, given a set of vertex pairs, the goal is to select a minimum-cost subgraph such that each pair is connected. 

This problem generalizes the Steiner Tree problem, first introduced in 1811, for which the best known approximation factor is 1.39 by [Byrka, Grandoni, Rothvoß, and Sanità, 2010].

The celebrated work of [Agrawal, Klein, and Ravi, 1989], along with refinements by [Goemans and Williamson, 1992], established a 2-approximation for Steiner Forest over 35 years ago. Despite the long-standing importance of this problem, breaking the approximation factor of 2 has remained a major challenge.

In this talk, I present a novel deterministic algorithm that breaks the approximation barrier of 2 for this fundamental problem. As a key component of our approach, we also introduce a novel dual-based local search algorithm for the Steiner Tree problem with an approximation guarantee of 1.943, which is of independent interest.

Full talks

Sequential Testing with Subadditive Costs

Viswanath Nagarajan (University of Michigan) 

In the classic sequential testing problem, we are given a system with several components each of which fails with some independent probability. The goal is to identify whether or not some component has failed. When the test costs are additive, it is well known that a greedy algorithm finds an optimal solution. We consider a much more general setting with subadditive cost functions and provide a (4ρ+γ)-approximation algorithm, assuming a γ-approximate value oracle (that computes the cost of any subset) and a ρ-approximate ratio oracle (that finds a subset with minimum ratio of cost to failure probability). While the natural greedy algorithm has a poor approximation ratio in the subadditive case, we show that a suitable truncation achieves the above guarantee.

Games of combinatorial optimization

Yuval Rabani (Hebrew University of Jerusalem) 

Six decades ago Lehman and Edmonds developed a remarkable theory which, among other consequences for the later development of matroid theory, demonstrated a class of two-player alternating-turn combinatorial games, in which winning moves can be computed in polynomial time. The original example of such a game is the Shannon switching game. This existing theory resolves only the win-lose binary alternative. But, as with most matroid questions, once we endow the ground set of the matroid with a weight function, the decision question generalizes to an optimization problem. In the game-theoretic setting, this leads to a zero-sum game with numerical payoff, rather than merely a win-lose outcome. We shall discuss problems of this flavor and we will present some results and some open questions.

TBD

Chaitanya Swamy (University of Waterloo)

Full talk

On the Approximability of Directed Steiner Tree

Bundit Laekhanukit 

Lighting talks

Fair Transit Stop Placement: a Clustering Perspective and Beyond [arxiv]

Yuhang Guo (UNSW) 

Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade [arxiv]

Simone di Gregorio (Sapienza University of Rome) 

A new algorithm analysis framework: By the book analysis [arxiv]

Eleon Bach (TU Munich) 

Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new algorithm analysis framework that we call by the book analysis. In contrast to earlier frameworks, by the book analysis not only models an algorithm's input data, but also the algorithm itself. Results from by the book analysis are meant to correspond well with established knowledge of an algorithm's practical behavior, as they are meant to be grounded in observations from implementations, input modeling best practices, and measurements on practical benchmark instances. The simplex method similarly showcased the state of the art framework smoothed analysis (Spielman and Teng, STOC'01). We prove that under input scaling assumptions, feasibility tolerances and other design principles used by simplex method implementations, the simplex method indeed attains a polynomial running time. This is joint work with Alexander Black, Sophie Huiberts and Sean Kafer.

Minimum Cost Nowhere-Zero Flows and Cut-Balanced Orientations

Siyue Liu (CMU) 

Flows and colorings are disparate concepts in graph algorithms---the former is tractable while the latter is intractable. Tutte introduced the concept of nowhere-zero flows to unify these two concepts. Jaeger showed that nowhere-zero flows are equivalent to cut-balanced orientations. Motivated by connections between nowhere-zero flows, cut-balanced orientations, Nash-Williams' well-balanced orientations, and postman problems, we study optimization versions of nowhere-zero flows and cut-balanced orientations. Given a bidirected graph with asymmetric costs on two orientations of each edge, we study the min cost nowhere-zero k-flow problem and min cost k-cut-balanced orientation problem. We show that both problems are NP-hard to approximate within any finite factor. Given the strong inapproximability result, we design bicriteria approximations for both problems. For the case of symmetric costs (where the costs of both orientations are the same for every edge), we show that the nowhere-zero k-flow problem remains NP-hard and admits a 3-approximation. Joint work with Karthekeyan Chandrasekaran (UIUC) and R. Ravi (CMU).

Maximum Matching in $\Theta(\log \log n)$ Passes in Dynamic Streams [arxiv]

Janani Sundaresan (University of Waterloo) 

In the dynamic streaming model, an $n$-vertex input graph is defined through a sequence of edge insertions and deletions in a stream. The algorithms are allowed to process this stream in multiple passes while using O(n \poly\log{(n)}) space. This model has been introduced in the seminal work of Ahn, Guha, and McGregor (AGM) in 2012 and has been studied extensively since.

In this talk, we focus on approximating maximum matching in the dynamic stream model. An $O(1)$-approximation algorithm in $O(\log n)$ passes was already introduced by [AGM12], but improving the number of passes has remained elusive. We give a randomized sketching based algorithm that achieves an $O(1)$-approximation in only $O(\log \log n)$-passes and $O(n \poly \log n)$ space, which exponentially improves the state-of-art. Using standard techniques, the approximation ratio of this algorithm can be improved to (1+eps)-approximation for any constant eps > 0 with asymptotically the same space and number of passes.

Furthermore, we prove the first multi-pass lower bound for this problem, showing that $\Omega(\log \log n)$ passes are also necessary for any algorithm which finds an $O(1)$-approximation to maximum matching in $O(n \poly \log n)$ space.

Our upper and lower bounds collectively settle the pass complexity of this fundamental problem in the dynamic streaming model. This is joint work with Sepehr Assadi, Soheil Behnezhad, Christian Konrad and Kheeran K. Naidu.

Fast Nearest Neighbor Search for $\ell_p$ Metrics

Nir Petruschka (Weizmann Institute) 

The Nearest Neighbor Search (NNS) problem asks to design a data structure that preprocesses an $n$-point dataset $X$ lying in a metric space $\mathcal{M}$, so that given a query point $q \in \mathcal{M}$, one can quickly return a point of $X$ minimizing the distance to $q$. The efficiency of such a data structure is evaluated primarily by the amount of space it uses and the time required to answer a query.

We focus on the fast query-time regime, which is crucial for modern large-scale applications, where datasets are massive and queries must be processed online, and is often modeled by query time $\text{poly}(d \log n)$.

Our main result is such a randomized data structure for NNS in $\ell_p$ spaces, $p>2$, that achieves $p^{O(1) + \log\log p}$ approximation with fast query time and $\text{poly}(dn)$ space. Our data structure improves, or is incomparable to, the state-of-the-art for the fast query-time regime from [Bartal and Gottlieb, TCS 2019] and [Krauthgamer, Petruschka and Sapir, FOCS 2025].

Fully Dynamic k-Median with Near-Optimal Update Time and Recourse [arxiv, video]

Ermiya Farokhnejad (University of Warwick)