Fabrizio Grandoni

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 [Fulkerson’74], 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 cut relaxation, which is exactly 2. We resolve this question by proving an upper bound of 1.9988 on the integrality gap of BCR.

In the classical NP-hard (metric) [Formula: see text]-median problem, we are given a set of [Formula: see text] clients and centers with metric distances between them, along with an integer parameter [Formula: see text]. The objective is to select a subset of [Formula: see text] open centers that minimizes the total distance from each client to its closest open center. In their seminal work, Jain, Mahdian, Markakis, Saberi, and Vazirani presented the Greedy algorithm for facility location, which implies a 2-approximation algorithm for [Formula: see text]-median that opens [Formula: see text] centers in expectation. Since then, substantial research has aimed at narrowing the gap between their algorithm and the best achievable approximation by an algorithm guaranteed to open exactly [Formula: see text] centers, as required in the [Formula: see text]-median problem. During the last decade, all improvements have been achieved by leveraging their algorithm (or a small improvement thereof), followed by a second step called bipoint rounding, which inherently adds an additional factor to the approximation guarantee. Our main result closes this gap: for any [Formula: see text], we present a [Formula: see text]-approximation algorithm for the [Formula: see text]-median problem, improving the previous best-known approximation factor of 2.613. Our approach builds on a combination of two key algorithms. First, we present a nontrivial modification of the Greedy algorithm that operates with only [Formula: see text] adaptive phases. Through a novel walk-between-solutions approach, this enables us to construct a [Formula: see text]-approximation algorithm for [Formula: see text]-median that consistently opens at most [Formula: see text] centers: via known results, this already implies a [Formula: see text]-approximation algorithm that runs in quasi-polynomial time. Second, we develop a novel [Formula: see text]-approximation algorithm tailored for stable instances, where removing any center from an optimal solution increases the cost by at least an [Formula: see text] fraction. Achieving this involves several ideas, including a sampling approach inspired by the [Formula: see text]-means++ algorithm and a reduction to submodular optimization subject to a partition matroid. This allows us to convert the previous result into a polynomial time algorithm that opens exactly [Formula: see text] centers while maintaining the [Formula: see text]-approximation guarantee.

The (Non-Preemptive) Throughput Maximization problem is a natural and fundamental scheduling problem. We are given n jobs, where each job j is characterized by a processing time and a time window, contained in a global interval [0,T), during which j can be scheduled. Our goal is to schedule the maximum possible number of jobs non-preemptively on a single machine, so that no two scheduled jobs are processed at the same time. This problem is known to be strongly NP-hard. The best-known approximation algorithm for it has an approximation ratio of 1/0.6448 + ε ≈ 1.551 + ε [Im, Li, Moseley IPCO’17], improving on an earlier result in [Chuzhoy, Ostrovsky, Rabani FOCS’01]. In this paper we substantially improve the approximation factor for the problem to 4/3+ε for any constant ε>0. Using pseudo-polynomial time (nT)^O(1), we improve the factor even further to 5/4+ε. Our results extend to the setting in which we are given an arbitrary number of (identical) machines.