In Asymmetric A Priori TSP (with independent activation probabilities) we are given an instance of the Asymmetric Traveling Salesman Problem together with an activation probability for each vertex. The task is to compute a tour that minimizes the expected length after short-cutting to the randomly sampled set of active vertices.

In the Steiner Forest problem, we are given a graph with edge lengths, and a collection of demand pairs; the goal is to find a subgraph of least total length such that each demand pair is connected in this subgraph. For over twenty years, the best approximation ratio known for the problem was a 2-approximation due to Agrawal, Klein, and Ravi (STOC 1991), despite many attempts to surpass this bound. Finally, in a recent breakthrough, Ahmadi, Gholami, Hajiaghayi, Jabbarzade, and Mahdavi (FOCS 2025) gave a 2-ϵ-approximation, where ϵ ≈ 10-11. In this work, we show how to simplify and extend the work of Ahmadi et al. to obtain an improved 1.994-approximation. We combine some ideas from their work (e.g., an extended run of the moat-growing primal-dual algorithm, and identifying autarkic pairs) with other ideas - submodular maximization to find components to contract, as in the relative greedy algorithms for Steiner tree, and the use of autarkic triples. We hope that our cleaner abstraction will open the way for further improvements.

We present the first approximation algorithms for the Weighted Tree Augmentation Problem (WTAP) that beat the longstanding approximation factor of 2, which can be achieved through standard techniques. The core of our approach is a novel decomposition theorem based on a well-chosen class of thin components . The decomposition theorem asserts that for any pair of a highly structured (but potentially expensive) WTAP solution and a cheaper WTAP solution, there is a way to decompose the cheaper solution into thin components, one of which allows for improving the structured solution. Together with the fact that we can efficiently optimize over thin components through a dynamic program, our decomposition theorem leads to a relative greedy algorithm for WTAP that is a (1 + ln 2 + ϵ)-approximation. Moreover, we present an approach to improve on some relative greedy procedures by well-chosen (non-oblivious) local search algorithms. The main application of this approach leads to a (1.5 + ϵ)-approximation for WTAP. Furthermore, for the Steiner Tree Problem, it provides 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, way to bound its integrality gap by ln 4.

The Steiner tree problem is one of the most prominent problems in network design. Given an edge-weighted undirected graph and a subset of the vertices, called terminals, the task is to compute a minimum-weight tree containing all terminals (and possibly further vertices). The best-known approximation algorithms for Steiner tree involve enumeration of a (polynomial but) very large number of candidate components and are therefore slow in practice. A promising ingredient for the design of fast and accurate approximation algorithms for Steiner tree is the bidirected cut relaxation (BCR): bidirect all edges, choose an arbitrary terminal as a root, and enforce that each cut containing some terminal but not the root has one unit of fractional edges leaving it. BCR is known to be integral in the spanning tree case [Edmonds'67], i.e., when all the vertices are terminals. For general instances, however, it was not even known whether the integrality gap of BCR is better than the integrality gap of the natural undirected relaxation, which is exactly 2. We resolve this question by proving an upper bound of 1.9988 on the integrality gap of BCR.

The single-source unsplittable flow (SSUF) problem asks to send flow from a common source to different terminals with unrelated demands, each terminal being served through a single path. One of the most heavily studied SSUF objectives is to minimize the violation of some given arc capacities. A seminal result of Dinitz, Garg, and Goemans showed that, whenever a fractional flow exists respecting the capacities, then there is an unsplittable one violating the capacities by at most the maximum demand. Goemans conjectured a very natural cost version of the same result, where the unsplittable flow is required to be no more expensive than the fractional one. This intriguing conjecture remains open. More so, there are arguably no non-trivial graph classes for which it is known to hold.

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.

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.

The basic goal of survivable network design is to build cheap networks that guarantee the connectivity of certain pairs of nodes despite the failure of a few edges or nodes. A celebrated result by Jain [Combinatorica'01] provides a 2-approximation for a wide class of these problems. However nothing better is known even for very basic special cases, raising the natural question whether any improved approximation factor is possible at all.

We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and Végh [ J. ACM, 67 (2020), 37]. We improve on each part of this algorithm. We avoid the reduction to irreducible instances and thus obtain a simpler and much better reduction to vertebrate pairs. We also show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio. Overall we improve the approximation ratio from 506 to $22+\epsilon$ for any $\epsilon > 0$. This also improves the upper bound on the integrality ratio from 319 to 22.

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, given an $\alpha$-approximation algorithm for TSP, then, for any $\epsilon >0$, we obtain an $(\alpha+\epsilon)$-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 $\alpha$-approximation algorithm for Graph TSP implies an $(\alpha+\epsilon)$-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+\epsilon)$-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 $\Phi$-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.

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. −

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 revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and Végh [STOC 2018]. We improve on each part of this algorithm. We avoid the reduction to irreducible instances and thus obtain a simpler and much better reduction to vertebrate pairs. We also show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio. Overall we improve the approximation ratio from 506 to 22+ε for any ε > 0. This also improves the upper bound on the integrality ratio from 319 to 22.

We show that there is a polynomial-time algorithm with approximation guarantee 3/2+ε for the s - t -path TSP, for any fixed ε > 0. It is well-known that Wolsey’s analysis of Christofide algorithm also works for the s - t -path TSP with its natural LP relaxation, except for the narrow cuts (in which the LP solution has a value less than two). A fixed optimum tour has either a single edge in a narrow cut (then call the edge and the cut lonely ) or at least three (then call the cut busy ). Our algorithm “guesses” (by dynamic programming) lonely cuts and edges. Then, we partition the instance into smaller instances and strengthen the LP, requiring a value of at least three for busy cuts. By setting up a k -stage recursive dynamic program, we can compute a spanning tree ( V , S ) and an LP solution y such that (½+ O (2 − k )) y is in the T -join polyhedron, where T is the set of vertices whose degree in S has the wrong parity.

Among various variants of the traveling salesman problem, the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this paper, we go below this threshold: we devise a polynomial-time algorithm for the s-t-path graph TSP with approximation ratio 1.497. Our algorithm can be viewed as a refinement of the 3/2-approximation algorithm by Sebo and Vygen [16], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics).

We show that there is a polynomial-time algorithm with approximation guarantee for the s-t-path TSP, for any fixed ε > 0. It is well known that Wolsey's analysis of Christofides’ algorithm also works for the s-t-path TSP with its natural LP relaxation except for the narrow cuts (in which the LP solution has value less than two). A fixed optimum tour has either a single edge in a narrow cut (then call the edge and the cut lonely) or at least three (then call the cut busy). Our algorithm “guesses” (by dynamic programming) lonely cuts and edges. Then we partition the instance into smaller instances and strengthen the LP, requiring value at least three for busy cuts. By setting up a k-stage recursive dynamic program, we can compute a spanning tree (V, S) and an LP solution y such that is in the T-join polyhedron, where T is the set of vertices whose degree in S has the wrong parity.

We show how to incorporate global static timing constraints into global routing. Our approach is based on the min-max resource sharing model that proved successful for global routing in theory and practice. Static timing constraints are modeled by a linear number of additional resources and customers. The algorithm dynamically adjusts delay budgets and can, thus, tradeoff wiring congestion for delay. As a subroutine, the algorithm routes a single net. If this subroutine is near-optimal, we will find near-optimal solutions for the overall problem very efficiently. The approach works for many delay models; here we discuss a linear delay model (before buffering) and the Elmore delay model (after buffering). We demonstrate the benefit of our timing-constrained global routing algorithm by experimental results on industrial chips.

We show how to incorporate global static timing constraints into global routing. Our approach is based on the min-max resource sharing model that proved successful for global routing in theory and practice. Static timing constraints are modeled by a linear number of additional resources and customers. The algorithm dynamically adjusts delay budgets and can, thus, trade off wiring congestion for delay. The approach works for many delay models. As a subroutine, the algorithm routes a single net. If this subroutine is near-optimal, we will find near-optimal solutions for the overall problem very efficiently. We demonstrate the benefit of our timing-driven global routing algorithm by experimental results on industrial chips.