In a packing problem, we are given a collection \(I\) of \(n\) items, each one with a given profit. Our goal is to compute a maximum profit subset of these items that satisfies a given set of packing constraints which depend on the problem at hand. Several approximation algorithms for well-studied NP-hard packing problems are based on a reduction to an auxiliary (packing) problem which is then solved with a dynamic program (DP). Examples for this include approximation algorithms for Knapsack, Geometric Knapsack, Independent Set of Rectangles, and Maximum Throughput Scheduling.

In the (Unit Demand) Euclidean Capacitated Vehicle Routing problem (CVRP), we are given a collection of \(n\) points in the Euclidean plane (the clients), one extra point (the depot), and one integer \(Q \ge 1\) (the vehicle capacity). A feasible solution is a collection of tours, where each tour contains the depot and at most \(Q\) clients, such that each client belongs to at least one such tour. Our goal is to minimize the total length of the tours. This models, e.g., the problem of delivering identical items stored at the depot to clients using a single vehicle that can carry at most \(Q\) items at a time.

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.

We present a polynomial-time (4+є)-approximation algorithm for (high-dimensional) Euclidean k-Means. This substantially improves on the current-best 5.83-approximation in [Charikar, Cohen-Addad, Gao, Grandoni, Lee, Van Wijland - FOCS’25] (that also works for the metric case). The mentioned algorithm by Charikar et al. critically exploits a greedy Lagrangian Multiplier Preserving (LMP) approximation for Facility Location with squared metric distances, that adapts the classical greedy algorithm with dual-fitting analysis for Metric Facility Location in [Jain, Mahdian, Markakis, Saberi, Vazirani - J.ACM’03]. The authors then turn it into an approximation algorithm for (Metric) k-Means, at the cost on an extra factor 1+є, by exploiting the framework introduced in [Cohen-Addad, Grandoni, Lee, Schwiegelshohn, Svensson - STOC’25] for k-Median. Our main contribution is a greedy LMP 4-approximation for Facility Location with squared Euclidean distances. Differently from Charikar et al., our algorithm sometimes decreases the dual variables, a quite uncommon feature for dual-based algorithms. This is critical in our dual-fitting analysis in order to exploit the specific properties of Euclidean metrics. For the (4+є)-approximation for k-Means, we extend the framework by Cohen-Addad et al. by overcoming substantial technical challenges posed by decreased dual values.

In their breakthrough ICALP’15 paper, Bernstein and Stein presented an algorithm for maintaining a \((3/2+\epsilon)\) -approximate maximum matching in fully dynamic bipartite graphs with a worst-case update time of \(O_{\epsilon}(m^{1/4})\) ; we use the \(O_{\epsilon}\) notation to suppress the \(\epsilon\) -dependence. Their main technical contribution was in presenting a new type of bounded-degree subgraph, which they named an edge degree constrained subgraph (EDCS) , which contains a large matching—of size that is smaller than the maximum matching size of the entire graph by at most a \(3/2+\epsilon\) factor. They demonstrate that the EDCS can be maintained with a worst-case update time of \(O_{\epsilon}(m^{1/4})\) , and their main result follows as a direct corollary. In their followup SODA’16 paper, Bernstein and Stein generalized their result for general graphs, achieving the same update time of \(O_{\epsilon}(m^{1/4})\) , albeit with an amortized rather than worst-case bound. To date, the best deterministic worst-case update time bound for any better-than-2 approximate matching is \(O(\sqrt{m})\) [Neiman and Solomon, STOC’13] and [Gupta and Peng, FOCS’13]; allowing randomization (against an oblivious adversary) one can achieve a much better (still polynomial) update time for approximation slightly below 2 [Behnezhad et al., SODA’20]. In this work we ( quasi nanos, gigantium humeris insidentes ) simplify the approach of Bernstein and Stein for bipartite graphs, which allows us to generalize it to general graphs while maintaining the same \(O_{\epsilon}(m^{1/4})\) bound on the worst-case update time. Moreover, our approach is density-sensitive : If the arboricity of the dynamic graph is always bounded by \(\alpha\) , then the worst-case update time of the algorithm is \(O_{\epsilon}(\sqrt{\alpha})\) .

Clustering is a basic task in data analysis and machine learning, and the optimization of clustering objectives are well-studied optimization problems; amongst these, the k Means objective is arguably the most well known. Given a collection of points in a metric space, the goal is to partition them into k clusters, each with an associated center, so as to minimize the sum of squared distances of points to their cluster centers. In this paper, we present a polynomial-time $3+2 \sqrt{2}+\varepsilon{\lt}5.83$-approximation algorithm for k-Means in general metrics. This substantially improves on the current-best $(9+\varepsilon)$-approximation in [Ahmadian, Norouzi-Fard, Svensson, Ward - FOCS’17, SICOMP’20], and even slightly improves on the 5.92-approximation in [Cohen-Addad, Esfandiari, Mirrokni, Narayanan - STOC’22] for the Euclidean special case. A natural approach for k-Means is to leverage Lagrangian Multiplier Preserving (LMP) approximations for the facility location problem. The previous best results for k-Means build upon an adaptation of an LMP 3-approximation for facility location with metric connection costs in [Jain, Vazirani J.ACM’01] based on a primal-dual method, rather than on the improved LMP greedy 2-approximation for the same problem in [Jain, Mahdian, Markakis, Saberi, Vazirani - J.ACM’03]. The barrier to using the improved LMP algorithm was that no adaptation of this algorithm and its analysis to the case of squared metric connection costs was known (since squared distances violate triangle inequality). Our main contribution is overcoming this barrier by providing such an adaptation. This new LMP approximation algorithm is then combined with the framework recently introduced in [Cohen-Addad, Grandoni, Lee, Schwiegelshohn, Svensson - STOC’25] for the related (metric) k Median problem.

Abstract In the Time-Windows Unsplittable Flow on a Path problem ( twUFP ) we are given a resource whose available amount changes over a given time interval (modeled as the edge-capacities of a given path G ) and a collection of tasks. Each task is characterized by a demand (of the considered resource), a profit, an integral processing time, and a time window. Our goal is to compute a maximum profit subset of tasks and schedule them non-preemptively within their respective time windows, such that the total demand of the tasks using each edge e is at most the capacity of e . We prove that twUFP is $$\textsf{APX}$$ APX -hard which contrasts the setting of the problem without time windows, i.e., Unsplittable Flow on a Path, for which a PTAS was recently discovered [Grandoni, Mömke, Wiese, STOC 2022]. Then, we present a quasi-polynomial-time $$2+\varepsilon $$ 2 + ε approximation for twUFP under resource augmentation. Our approximation ratio improves to $$1+\varepsilon $$ 1 + ε if all tasks’ time windows are identical. Our $$\textsf{APX}$$ APX -hardness holds also for this special case and, hence, rules out such a PTAS (and even a QPTAS, unless $$\textsf{NP}\subseteq \textrm{DTIME}(n^{\textrm{poly}(\log n)})$$ NP ⊆ DTIME ( n poly ( log n ) ) ) without resource augmentation.

In the classical NP-hard (metric) k-median problem, we are given a set of n clients and centers with metric distances between them, along with an integer parameter k ≥ 1. The objective is to select a subset of k 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 k-median that opens k 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 k centers, as required in the k-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 bi-point rounding, which inherently adds an additional factor to the approximation guarantee. Our main result closes this gap: for any > 0, we present a (2+)-approximation algorithm for the k-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 non-trivial modification of the Greedy algorithm that operates with only O(logn/2) adaptive phases. Through a novel walk-between-solutions approach, this enables us to construct a (2+)-approximation algorithm for k-median that consistently opens at most k + O(logn/2) centers: via known results, this already implies a (2+)-approximation algorithm that runs in quasi-polynomial time. Second, we develop a novel (2+)-approximation algorithm tailored for stable instances, where removing any center from an optimal solution increases the cost by at least an ω(3/logn) fraction. Achieving this involves several ideas, including a sampling approach inspired by the k-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 k centers while maintaining the (2+)-approximation guarantee.

In the maximum independent set of convex polygons problem, we are given a set of $n$ convex polygons in the plane with the objective of selecting a maximum cardinality subset of non-overlapping polygons. Here we study a special case of the problem where the edges of the polygons can take at most $d$ fixed directions. We present an $8d/3$-approximation algorithm for this problem running in time $O((nd)^{O(d4^d)})$. The previous-best polynomial-time approximation (for constant $d$) was a classical $n^\varepsilon$ approximation by Fox and Pach [SODA'11] that has recently been improved to a $OPT^{\varepsilon}$-approximation algorithm by Cslovjecsek, Pilipczuk and Węgrzycki [SODA '24], which also extends to an arbitrary set of convex polygons. Our result builds on, and generalizes the recent constant factor approximation algorithms for the maximum independent set of axis-parallel rectangles problem (which is a special case of our problem with $d=2$) by Mitchell [FOCS'21] and Gálvez, Khan, Mari, Mömke, Reddy, and Wiese [SODA'22].

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.

In the Submodular Facility Location problem (SFL) we are given a collection of $n$ clients and $m$ facilities in a metric space. A feasible solution consists of an assignment of each client to some facility. For each client, one has to pay the distance to the associated facility. Furthermore, for each facility $f$ to which we assign the subset of clients $S^f$, one has to pay the opening cost $g(S^f)$, where $g(\cdot)$ is a monotone submodular function with $g(\emptyset)=0$. SFL is APX-hard since it includes the classical (metric uncapacitated) Facility Location problem (with uniform facility costs) as a special case. Svitkina and Tardos [SODA'06] gave the current-best $O(\log n)$ approximation algorithm for SFL. The same authors pose the open problem whether SFL admits a constant approximation and provide such an approximation for a very restricted special case of the problem. We make some progress towards the solution of the above open problem by presenting an $O(\log\log n)$ approximation. Our approach is rather flexible and can be easily extended to generalizations and variants of SFL. In more detail, we achieve the same approximation factor for the practically relevant generalizations of SFL where the opening cost of each facility $f$ is of the form $p_f+g(S^f)$ or $w_f\cdot g(S^f)$, where $p_f,w_f \geq 0$ are input values. We also obtain an improved approximation algorithm for the related Universal Stochastic Facility Location problem. In this problem one is given a classical (metric) facility location instance and has to a priori assign each client to some facility. Then a subset of active clients is sampled from some given distribution, and one has to pay (a posteriori) only the connection and opening costs induced by the active clients. The expected opening cost of each facility $f$ can be modelled with a submodular function of the set of clients assigned to $f$.

In the Unsplittable Flow on a Path problem UFP, we are given a path graph with edge capacities and a collection of tasks. Each task is characterized by a demand, a profit, and a subpath. Our goal is to select a maximum profit subset of tasks such that the total demand of the selected tasks that use each edge $e$ is at most the capacity of $e$. Bag-UFP is the generalization of UFP where tasks are partitioned into bags, and we are allowed to select at most one task per bag. UFP admits a PTAS [Grandoni,M{ö}mke,Wiese'22] but not an EPTAS [Wiese'17]. Bag-UFP is APX-hard [Spieksma'99] and the current best approximation is $O(\log n/\log\log n)$ [Grandoni,Ingala,Uniyal'15], where $n$ is the number of tasks. In this paper, we study the mentioned two problems when parameterized by the number $m$ of edges in the graph, with the goal of designing faster parameterized approximation algorithms. We present a parameterized EPTAS for Bag-UFP, and a substantially faster parameterized EPTAS for UFP (which is an FPTAS for $m=O(1)$). We also show that a parameterized FPTAS for UFP (hence for BagUFP) does not exist, therefore our results are qualitatively tight.

The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph G. Our goal is to find a subgraph S of G with the minimum number of edges which is 2-vertex-connected, namely S remains connected after the deletion of an arbitrary node. 2VCSS is well-studied in terms of approximation algorithms, and the current best (polynomial-time) approximation factor is 10/7 by Heeger and Vygen [SIDMA'17] (improving on earlier results by Khuller and Vishkin [STOC'92] and Garg, Vempala and Singla [SODA'93]). Here we present an improved 4/3 approximation. Our main technical ingredient is an approximation preserving reduction to a conveniently structured subset of instances which are "almost" 3-vertex-connected. The latter reduction might be helpful in future work.

In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the depot such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. Our main result is a polynomial-time (2+ε)-approximation algorithm for this problem in the two-dimensional Euclidean plane, i.e., for the special case where the terminals and the depot are associated with points in the Euclidean plane and their distances are defined accordingly. This improves on recent work by Blauth, Traub, and Vygen [IPCO'21] and Friggstad, Mousavi, Rahgoshay, and Salavatipour [IPCO'22].

The basic goal of survivable network design is to construct low-cost networks which preserve a sufficient level of connectivity despite the failure or removal of a few nodes or edges. One of the most basic problems in this area is the 2-Edge-Connected Spanning Subgraph problem (2-ECSS): given an undirected graph G, find a 2-edge-connected spanning subgraph H of G with the minimum number of edges (in particular, H remains connected after the removal of one arbitrary edge). 2-ECSS is NP-hard and the best-known (polynomial-time) approximation factor for this problem is 4/3. Interestingly, this factor was achieved with drastically different techniques by [Hunkenschröder, Vempala and Vetta '00,'19] and [Sebö and Vygen, '14]. In this paper we present an improved approximation for 2-ECSS. The key ingredient in our approach (which might also be helpful in future work) is a reduction to a special type of structured graphs: our reduction preserves approximation factors up to 6/5. While reducing to 2-vertex-connected graphs is trivial (and heavily used in prior work), our structured graphs are “almost” 3-vertex-connected: more precisely, given any 2-vertex-cut {u, v} of a structured graph G = (V, E), G[V \ {u, v}] has exactly 2 connected components, one of which contains exactly one node of degree 2 in G. * Partially supported by the SNSF Excellence Grant 200020B 182865/1 and the SNSF Grant 200021 200731/1.

The Uncapacitated Facility Location (UFL) problem is one of the most fundamental clustering problems: Given a set of clients C and a set of facilities F in a metric space (C ∪ F, dist) with facility costs open : F→ ℝ+, the goal is to find a set of facilities S ⊆ F to minimize the sum of the opening cost open(S) and the connection cost d(S) := Σp∈C minc∈S dist(p,c). An algorithm for UFL is called a Lagrangian Multiplier Preserving (LMP) α approximation if it outputs a solution S ⊆ F satisfying open(S) + d(S) ≤ open(S*) + αd(S*) for any S* ⊆ F. The best-known LMP approximation ratio for UFL is at most 2 by the JMS algorithm of Jain, Mahdian, and Saberi [STOC'02, J.ACM'03] based on the Dual-Fitting technique. The lack of progress on improving the upper bound on αLMP in the last two decades raised the natural question whether αLMP = 2. We answer this question negatively by presenting a (slightly) improved LMP approximation algorithm for UFL. This is achieved by combining the Dual-Fitting technique with Local Search, another popular technique to address clustering problems. In more detail, we use the LMP solution S produced by JMS to seed a local search algorithm. We show that local search substantially improves S unless a big fraction of the connection cost of S is associated with facilities of relatively small opening costs. In the latter case however the analysis of Jain, Mahdian, and Saberi can be improved (i.e., S is cheaper than expected). To summarize: Either S is close enough to the optimum, or it must belong to the local neighborhood of a good enough local optimum. From a conceptual viewpoint, our result gives a theoretical evidence that local search can be enhanced so as to avoid bad local optima by choosing the initial feasible solution with LP-based techniques. Our result directly implies a (slightly) improved approximation for the related k-Median problem, another fundamental clustering problem: Given (C ∪ F, dist) as in a UFL instance and an integer k ∈ ℕ, find S ⊆ F with |S| = k that minimizes d(S). The current best approximation algorithms for k-Median are based on the following framework: use an LMP α approximation algorithm for UFL to build an α approximate bipoint solution for k-Median, and then round it with a ρBR approximate bipoint rounding algorithm. This implies an α · ρBR approximation. The current-best value of ρBR is 1.338 by Byrka, Pensyl, Rybicki, Srinivasan, and Trinh [SODA'15, TALG'17], which yields 2.6742-approximation. Combining their algorithm with our refined LMP algorithm for UFL (replacing JMS) gives a 2.67059-approximation. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.05150

Abstract. The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The connectivity augmentation problem ([Formula: see text]) is arguably one of the most basic problems in this area: given a [Formula: see text](-edge)-connected graph [Formula: see text] and a set of extra edges ( links), select a minimum cardinality subset [Formula: see text] of links such that adding [Formula: see text] to [Formula: see text] increases its edge connectivity to [Formula: see text]. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [G. N. Frederickson and Jájá, SIAM J. Comput., 10 (1981), pp. 270–283]. It is known [E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov, Studies in Discrete Optimization, Nauka, Moscow, 1976, pp. 290–306] that [Formula: see text] can be reduced to the case [Formula: see text], also known as the t ree augmentation problem ([Formula: see text]) for odd [Formula: see text], and to the case [Formula: see text], also known as the c actus augmentation problem ([Formula: see text]) for even [Formula: see text]. Prior to the conference version of this paper [J. Byrka, F. Grandoni, and A. Jabal Ameli, STOC’20, ACM, New York, 2020, pp. 815–825], several better than 2 approximation algorithms were known for [Formula: see text], culminating with a recent [Formula: see text] approximation [F. Grandoni, C. Kalaitzis, and R. Zenklusen, STOC’18, ACM, New York, 1918, pp. 632–645]. However, for [Formula: see text] the best known approximation was 2. In this paper we breach the 2 approximation barrier for [Formula: see text], hence, for [Formula: see text], by presenting a polynomial-time [Formula: see text] approximation. From a technical point of view, our approach deviates quite substantially from previous work. In particular, the better-than-2 approximation algorithms for [Formula: see text] either exploit greedy-style algorithms or are based on rounding carefully designed LPs. We instead use a reduction to the Steiner tree problem which was previously used in parameterized algorithms [Basavaraju et al., ICALP ’14, Springer, Berlin, 2014, pp. 800–811]. This reduction is not approximation preserving, and using the current best approximation factor for a Steiner tree [Byrka et al., J. ACM, 60 (2013), 6] as a black box would not be good enough to improve on 2. To achieve the latter goal, we “open the box” and exploit the specific properties of the instances of a Steiner tree arising from [Formula: see text]. In our opinion this connection between approximation algorithms for survivable network design and Steiner-type problems is interesting, and might lead to other results in the area.

Measuring the importance of a node in a network is a major goal in the analysis of social networks, biological systems, transportation networks, and so forth. Different centrality measures have been proposed to capture the notion of node importance. For example, the center of a graph is a node that minimizes the maximum distance to any other node (the latter distance is the radius of the graph). The median of a graph is a node that minimizes the sum of the distances to all other nodes. Informally, the betweenness centrality of a node w measures the fraction of shortest paths that have w as an intermediate node. Finally, the reach centrality of a node w is the smallest distance r such that any s - t shortest path passing through w has either s or t in the ball of radius r around w . The fastest known algorithms to compute the center and the median of a graph and to compute the betweenness or reach centrality even of a single node take roughly cubic time in the number n of nodes in the input graph. It is open whether these problems admit truly subcubic algorithms, i.e., algorithms with running time Õ(n 3-δ ) for some constant δ > 0. 1 We relate the complexity of the mentioned centrality problems to two classical problems for which no truly subcubic algorithm is known, namely All Pairs Shortest Paths (APSP) and Diameter. We show that Radius, Median, and Betweenness Centrality are equivalent under subcubic reductions to APSP, i.e., that a truly subcubic algorithm for any of these problems implies a truly subcubic algorithm for all of them. We then show that Reach Centrality is equivalent to Diameter under subcubic reductions. The same holds for the problem of approximating Betweenness Centrality within any finite factor. Thus, the latter two centrality problems could potentially be solved in truly subcubic time, even if APSP required essentially cubic time. On the positive side, our reductions for Reach Centrality imply an improved Õ(Mn ω )-time algorithm for this problem in case of non-negative integer weights upper bounded by M , where ω is a fast matrix multiplication exponent.

The unsplittable flow on a path (UFP) problem is a well-studied optimization problem, and it has applications in various settings like bandwidth allocation, caching, and scheduling. We are given a path with capacities on its edges and a set of n tasks, each of them defined via a demand, a subpath, and a profit. The goal is to select the most profitable set of tasks that together respect the edge capacities, i.e., for each edge e the total demand of the selected tasks whose subpath contains e is at most the capacity of e. The best known polynomial time approximation algorithm for UFP is a (5/3 + ∊)-approximation [Grandoni et al., STOC 2018]. It is an important open question whether the problem admits a PTAS. Informally, a task is large if its demand is at least an ∊-fraction of the capacity of some edge on its path, and small otherwise. If all tasks are large, a PTAS can be obtained via dynamic programming: intuitively each edge e is used by only O(1) relevant tasks in the optimal solution OPT. The same approach fails for small tasks since then this number can be up to Ω(n) which would yield an exponential number of states. In this paper we introduce a novel randomized sketching technique to address this issue. We model the computation of a solution as a solitary game where tasks are presented one by one to a player, who has to decide for each task i whether to select i (hence getting its profit) or not. When a small task i is selected, with some probability its demand is rounded up to some large value (and then i behaves like a large task), and otherwise down to zero (and then i can be “forgotten” afterwards), so that in expectation the demand of i does not change. The optimal strategy to play this game can be computed using similar ideas as used in the DP for large tasks. Furthermore, the expected profit of this strategy is at least as large as the profit of OPT. One complication is that the player's solution might be infeasible, e.g., when too many tasks are rounded down. Still, via probabilistic arguments, we can use it to construct a feasible UFP solution which is 1 + + ∊ < 1.269 approximate in expectation. It is potentially possible that a more sophisticated probabilistic analysis gives a PTAS for the problem. We believe that randomized sketching might turn out to be useful to address also other problems in which “large” and “small” objects interact, for example in packing, scheduling, or resource allocation settings, in particular when dynamic programming works if there are only large objects.

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.

In the Unsplittable Flow on a Path problem (UFP) we are given a path with edge capacities, and a set of tasks where each task is characterized by a subpath, a demand, and a weight. The goal is to select a subset of tasks of maximum total weight such that the total demand of the selected tasks using each edge e is at most the capacity of e. The problem admits a QPTAS [Bansal, Chakrabarti, Epstein, Schieber, STOC'06; Batra, Garg, Kumar, Mömke, Wiese, SODA'15]. After a long sequence of improvements [Bansal, Friggstad, Khandekar, Salavatipour, SODA'09; Bonsma, Schulz, Wiese, FOCS'11; Anagnostopoulos, Grandoni, Leonardi, Wiese, SODA'14; Grandoni, Mömke, Wiese, Zhou, STOC'18], the best known polynomial time approximation algorithm for UFP has an approximation ratio of 1+1/(e+1) + epsilon < 1.269 [Grandoni, Mömke, Wiese, SODA'22]. It has been an open question whether this problem admits a PTAS. In this paper, we solve this open question and present a polynomial time (1 + epsilon)-approximation algorithm for UFP.

In the Euclidean k-Means problem we are given a collection of n points D in an Euclidean space and a positive integer k. Our goal is to identify a collection of k points in the same space (centers) so as to minimize the sum of the squared Euclidean distances between each point in D and the closest center. This problem is known to be APX-hard and the current best approximation ratio is a primal-dual 6.357 approximation based on a standard LP for the problem [Ahmadian et al. FOCS'17, SICOMP'20]. In this note we show how a minor modification of Ahmadian et al.'s analysis leads to a slightly improved 6.12903 approximation. As a related result, we also show that the mentioned LP has integrality gap at least 16+515>1.2157.

The problem of (Δ +1)-vertex coloring a graph of maximum degree Δ has been extremely well studied over the years in various settings and models. Surprisingly, for the dynamic setting, almost nothing was known until recently. In SODA’18, Bhattacharya, Chakrabarty, Henzinger and Nanongkai devised a randomized algorithm for maintaining a (Δ +1)-coloring with O (log Δ) expected amortized update time. In this article, we present an improved randomized algorithm for (Δ +1)-coloring that achieves O (1) amortized update time and show that this bound holds not only in expectation but also with high probability. Our starting point is the state-of-the-art randomized algorithm for maintaining a maximal matching (Solomon, FOCS’16). We carefully build on the approach of Solomon, but, due to inherent differences between the maximal matching and (Δ +1)-coloring problems, we need to deviate significantly from it in several crucial and highly nontrivial points. 1

In the Demand Strip Packing problem (DSP), we are given a time interval and a collection of tasks, each characterized by a processing time and a demand for a given resource (such as electricity, computational power, etc.). A feasible solution consists of a schedule of the tasks within the mentioned time interval. Our goal is to minimize the peak resource consumption, i.e. the maximum total demand of tasks executed at any point in time. It is known that DSP is NP-hard to approximate below a factor 3/2, and standard techniques for related problems imply a (polynomial-time) 2-approximation. Our main result is a (5/3+eps)-approximation algorithm for any constant eps>0. We also achieve best-possible approximation factors for some relevant special cases.

Given a set of n non-overlapping geometric objects, can we separate a constant fraction of them using straight-line cuts that extend from edge to edge? In 1996, Urrutia posed this question for compact convex objects. Pach and Tardos later refuted it for general line segments by constructing a family where any separable subfamily has size at most O (n^{log₃ 2}). However, for axis-parallel rectangles, they provided positive evidence, showing that an Ω(1/log n)-fraction can be separated. This problem naturally arises in geometric approximation algorithms. In particular, when restricting cuts to only orthogonal straight lines, known as a guillotine cut sequence, any bound on the separability ratio directly translates into a clean and simple dynamic programming for computing a maximum independent set of geometric objects. This paper focuses on the case when the objects are squares. For squares of arbitrary sizes, an Ω(1)-fraction can be separated (Abed et al., APPROX 2015), recently improved to 1/40 (and 1/160 ≈ 0.62% for the weighted case) (Khan and Pittu, APPROX 2020). We further improve this bound, showing that a 9/256 ≈ 3.51% can be separated for the weighted case. This result significantly narrows the possible range for squares to [3.51%, 50%]. The key to our improvement is a refined analysis of the existing framework.

Unsplittable flow on a path (UFP) is an important and well-studied problem. We are given a path with capacities on its edges, and a set of tasks where for each task we are given a demand, a subpath, and a weight. The goal is to select the set of tasks of maximum total weight whose total demands do not exceed the capacity on any edge. UFP admits an (1+ε)-approximation with a running time of n^{O_{ε}(poly(log n))}, i.e., a QPTAS {[}Bansal et al., STOC 2006; Batra et al., SODA 2015{]} and it is considered an important open problem to construct a PTAS. To this end, in a series of papers polynomial time approximation algorithms have been developed, which culminated in a (5/3+ε)-approximation {[}Grandoni et al., STOC 2018{]} and very recently an approximation ratio of (1+1/(e+1)+ε) < 1.269 {[}Grandoni et al., 2020{]}. In this paper, we address the search for a PTAS from a different angle: we present a faster (1+ε)-approximation with a running time of only n^{O_{ε}(log log n)}. We first give such a result in the relaxed setting of resource augmentation and then transform it to an algorithm without resource augmentation. For this, we present a framework which transforms algorithms for (a slight generalization of) UFP under resource augmentation in a black-box manner into algorithms for UFP without resource augmentation, with only negligible loss.

Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured that an online (1 + o(1))Δ-edge-coloring algorithm exists for n-node graphs of maximum degree Δ = ω(log n). This conjecture remains open in general, though it was recently proven for bipartite graphs under one-sided vertex arrivals by Cohen et al. [FOCS'19]. In a similar vein, we study edge coloring under widely-studied relaxations of the online model. Our main result is in the random-order online model. For this model, known results fall short of the Bar-Noy et al. conjecture, either in the degree bound [Aggarwal et al. FOCS'03], or number of colors used [Bahmani et al. SODA'10]. We achieve the best of both worlds, thus resolving the Bar-Noy et al. conjecture in the affirmative for this model. Our second result is in the adversarial online (and dynamic) model with recourse. A recent algorithm of Duan et al. [SODA'19] yields a (1 + ∊) Δ-edge-coloring with poly(log n/∊) recourse. We achieve the same with poly(1/∊) recourse, thus removing all dependence on n. Underlying our results is one common offline algorithm, which we show how to implement in these two online models. Our algorithm, based on the Rödl Nibble Method, is an adaptation of the distributed algorithm of Dubhashi et al. [TCS'98]. The Nibble Method has proven successful for distributed edge coloring. We display its usefulness in the context of online algorithms.

Let G = (V, E) be an n-vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices u and v is a common ancestor w of u and v such that no descendant of w has the same property. In this paper, we consider the problem of computing an LCA, if any, for all pairs of vertices in a DAG. The fastest known algorithms for this problem exploit fast matrix multiplication subroutines and have running times ranging from (n2.687) [Bender et al. SODA'01] down to (n2.615) [Kowaluk and Lingas ICALP'05] and (n2.569) [Czumaj et al. TCS'07]. Somewhat surprisingly, all those bounds would still be Ω(n2.5) even if matrix multiplication could be solved optimally (i.e., ω = 2). This appears to be an inherent barrier for all the currently known approaches, which raises the natural question on whether one could break through the (n2.5) barrier for this problem. In this paper, we answer this question affirmatively: in particular, we present an for ω = 2) algorithm for finding an LCA for all pairs of vertices in a DAG, which represents the first improvement on the running times for this problem in the last 13 years. A key tool in our approach is a fast algorithm to partition the vertex set of the transitive closure of G into a collection of (ℓ) chains and (n/ℓ) antichains, for a given parameter ℓ. As usual, a chain is a path while an antichain is an independent set. We then find, for all pairs of vertices, a candidate LCA among the chain and antichain vertices, separately. The first set is obtained via a reduction to (max, min) matrix multiplication. The computation of the second set can be reduced to Boolean matrix multiplication similarly to previous results on this problem. We finally combine the two solutions together in a careful (non-obvious) manner.

Abstract In the k-Connectivity Augmentation Problem we are given a k-edge-connected graph and a set of additional edges called links. Our goal is to find a set of links of minimum size whose addition to the graph makes it (k + 1)-edge-connected. There is an approximation preserving reduction from the mentioned problem to the case k = 1 (a.k.a. the Tree Augmentation Problem or TAP) or k = 2 (a.k.a. the Cactus Augmentation Problem or CacAP). While several better-than-2 approximation algorithms are known for TAP, for CacAP only recently this barrier was breached (hence for k-Connectivity Augmentation in general). As a first step towards better approximation algorithms for CacAP, we consider the special case where the input cactus consists of a single cycle, the Cycle Augmentation Problem (CycAP). This apparently simple special case retains part of the hardness of the general case. In particular, we are able to show that it is APX-hard. In this paper we present a combinatorial $\left (\frac {3}{2}+\varepsilon \right )$ 3 2 + ε -approximation for CycAP, for any constant ε > 0. We also present an LP formulation with a matching integrality gap: this might be useful to address the general case of the problem.

In the Strip Packing problem, we are given a vertical half-strip [0,W]× [0,+∞) and a collection of open rectangles of width at most W. Our goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip such that the maximum height OPT spanned by the packing is as small as possible. Strip Packing generalizes classical well-studied problems such as Makespan Minimization on identical machines (when rectangle widths are identical) and Bin Packing (when rectangle heights are identical). It has applications in manufacturing, scheduling and energy consumption in smart grids among others. It is NP-hard to approximate this problem within a factor (3/2-ε) for any constant ε > 0 by a simple reduction from the Partition problem. The current best approximation factor for Strip Packing is (5/3+ε) by Harren et al. [Computational Geometry '14], and it is achieved with a fairly complex algorithm and analysis. It seems plausible that Strip Packing admits a (3/2+ε)-approximation. We make progress in that direction by achieving such tight approximation guarantees for a special family of instances, which we call skewed instances. As standard in the area, for a given constant parameter δ > 0, we call large the rectangles with width at least δ W and height at least δ OPT, and skewed the remaining rectangles. If all the rectangles in the input are large, then one can easily compute the optimal packing in polynomial time (since the input can contain only a constant number of rectangles). We consider the complementary case where all the rectangles are skewed. This second case retains a large part of the complexity of the original problem; in particular, it is NP-hard to approximate within a factor (3/2-ε) and we provide an (almost) tight (3/2+ε)-approximation algorithm.

The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The Connectivity Augmentation Problem (CAP) is arguably one of the most basic problems in this area: given a k(-edge)-connected graph G and a set of extra edges (links), select a minimum cardinality subset A of links such that adding A to G increases its edge connectivity to k+1. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [Frederickson and Jájá’81]).

Shortest paths computation is one of the most fundamental problems in computer science. An important variant of the problem is when edges can fail, and one needs to compute shortest paths that avoid a (failing) edge. More formally, given a source node s , a target node t , and an edge e , a replacement path for the triple ( s , t , e ) is a shortest s - t path avoiding edge e . Replacement paths computation can be seen either as a static problem or as a data structure problem. In the static setting, a typical goal is to compute for fixed s and t , for every possible failed edge e , the length of the best replacement path around e ( replacement paths problem ). In the data structure setting, a typical goal is to design a data structure ( distance sensitivity oracle ) that, after some preprocessing, quickly answers queries of the form: What is the length of the replacement path for the triple ( s , t , e )? In this article, we focus on n -node directed graphs with integer edge weights in [− M , M ], and present improved replacement paths algorithms and distance sensitivity oracles based on fast matrix multiplication. In more detail, we obtain the following main results: • We describe a replacement paths algorithm with runtime Õ( Mn ω ), where ω < 2.373 is the fast matrix multiplication exponent. For a comparison, the previous fastest algorithms have runtime õ( Mn 1+2ω /3 ) [Weimann,Yuster—FOCS’10] and, in the unweighted case, õ( n 2.5 ) [Roditty, Zwick—ICALP’05]. Our result shows that, at least for small integer weights, the replacement paths problem in directed graphs may be easier than the related all-pairs shortest paths problem, as the current best runtime for the latter is õ( M 1\4−ω n 2+1 \ 4−ω ): this is Ω ( n 2.5 ) even if ω = 2. Our algorithm also implies that the k shortest simple s - t paths can be computed in õ( kMn ω ) time. • We consider the single-source generalization of the replacement paths problem, where only the source s is fixed. We show how to solve this problem in all-pairs shortest paths time, currently õ( M 1\4−ω n 2+1\4−ω ). Our runtime reduces to õ( Mn ω ) for positive weights, hence matching our mentioned result for the simpler replacement paths case (that, however, holds also for nonpositive weights). One of the ingredients that we use is an algorithm to compute the distances from a set s of source nodes to a set T of target nodes in õ( Mn ω +| S |ṡ | T |ṡ ( Mn ) 1\4−ω ) time. This improves on a result in Yuster,Zwick—FOCS’05. • We present the first distance sensitivity oracle that achieves simultaneously subcubic preprocessing time and sublinear query time. More precisely, for a given parameter α ∈ [0,1], our oracle has preprocessing time Õ( Mn ω + 1\ 2 + Mn ω + α (4−ω) ) and query time Õ( n 1−&alpha ). The previous best oracle for small integer weights has Õ( Mn ω +1−α ) preprocessing time and (superlinear) Õ( n 1+α ) query time [Weimann,Yuster-FOCS’10]. From a technical point of view, an interesting and novel aspect of our oracle is that it exploits as a subroutine our single-source replacement paths algorithm. We also present an oracle with the same preprocessing time as in Weimann,Yuster—FOCS’10 and with smaller query time õ( n 1−1−α\4−ω + n 2α ).

The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1+epsilon)-approximations in f(k,epsilon)n^O(1) time where k is some parameter of the input. The goal is to overcome lower bounds from either of the areas. We obtain the following results on parameterized approximability: - In the maximum independent set of rectangles problem (MISR) we are given a collection of n axis parallel rectangles in the plane. Our goal is to select a maximum-cardinality subset of pairwise non-overlapping rectangles. This problem is NP-hard and also W[1]-hard [Marx, ESA'05]. The best-known polynomial-time approximation factor is O(log log n) [Chalermsook and Chuzhoy, SODA'09] and it admits a QPTAS [Adamaszek and Wiese, FOCS'13; Chuzhoy and Ene, FOCS'16]. Here we present a parameterized approximation scheme (PAS) for MISR, i.e. an algorithm that, for any given constant epsilon>0 and integer k>0, in time f(k,epsilon)n^g(epsilon), either outputs a solution of size at least k/(1+epsilon), or declares that the optimum solution has size less than k. - In the (2-dimensional) geometric knapsack problem (2DK) we are given an axis-aligned square knapsack and a collection of axis-aligned rectangles in the plane (items). Our goal is to translate a maximum cardinality subset of items into the knapsack so that the selected items do not overlap. In the version of 2DK with rotations (2DKR), we are allowed to rotate items by 90 degrees. Both variants are NP-hard, and the best-known polynomial-time approximation factor is 2+epsilon [Jansen and Zhang, SODA'04]. These problems admit a QPTAS for polynomially bounded item sizes [Adamaszek and Wiese, SODA'15]. We show that both variants are W[1]-hard. Furthermore, we present a PAS for 2DKR. For all considered problems, getting time f(k,epsilon)n^O(1), rather than f(k,epsilon)n^g(epsilon), would give FPT time f'(k)n^O(1) exact algorithms by setting epsilon=1/(k+1), contradicting W[1]-hardness. Instead, for each fixed epsilon>0, our PASs give (1+epsilon)-approximate solutions in FPT time. For both MISR and 2DKR our techniques also give rise to preprocessing algorithms that take n^g(epsilon) time and return a subset of at most k^g(epsilon) rectangles/items that contains a solution of size at least k/(1+epsilon) if a solution of size k exists. This is a special case of the recently introduced notion of a polynomial-size approximate kernelization scheme [Lokshtanov et al., STOC'17].

In the Highway problem, we are given a path with n edges (the highway), and a set of m drivers, each one characterized by a subpath and a budget. For a given assignment of edge prices (the tolls), the highway owner collects from each driver the total price of the associated path when it does not exceed drivers’s budget, and zero otherwise. The goal is to choose the prices to maximize the total profit. A PTAS is known for this (strongly NP-hard) problem [Grandoni,Rothvoss-SODA'11, SICOMP'16]. In this paper we study the limited supply generalization of Highway, that incorporates capacity constraints. Here the input also includes a capacity u_e >= 0 for each edge e; we need to select, among drivers that can afford the required price, a subset such that the number of drivers that use each edge e is at most u_e (and we get profit only from selected drivers). To the best of our knowledge, the only approximation algorithm known for this problem is a folklore O(log m) approximation based on a reduction to the related Unsplittable Flow on a Path problem (UFP). The main result of this paper is a PTAS for limited supply highway. As a second contribution, we study a natural generalization of the problem where each driver i demands a different amount d_i of capacity. Using known techniques, it is not hard to derive a QPTAS for this problem. Here we present a PTAS for the case that drivers have uniform budgets. Finding a PTAS for non-uniform-demand limited supply highway is left as a challenging open problem.

We study the matching problem in the incremental setting, where we are given a sequence of edge insertions and aim at maintaining a near-maximum cardinality matching of the graph with small update time. We present a deterministic algorithm that, for any constant ε > 0, maintains a (1 + ε)-approximate matching with constant amortized update time per insertion.

In the Directed Steiner Tree (DST) problem we are given an n-vertex directed edge-weighted graph, a root r , and a collection of k terminal nodes. Our goal is to find a minimum-cost subgraph that contains a directed path from r to every terminal. We present an O(log^2 k /log log k )-approximation algorithm for DST that runs in quasi-polynomial-time, i.e., in time n^polylog(k). By making standard complexity assumptions, we show the matching lower bound of Omega(log^2 k/loglogk) for the class of quasi-polynomial time algorithms, meaning that our approximation ratio is asymptotically the best possible. This is the first improvement on the DST problem since the classical quasi-polynomial-time O (log^3 k ) approximation algorithm by Charikar et al. [SODA’98J. Algorithms’99]. (The paper erroneously claims an O (log^2 k ) approximation due to a mistake in prior work.)

We give new upper and lower bounds for the dynamic set cover problem. First, we give a (1+є) f-approximation for fully dynamic set cover in O(f2logn/є5) (amortized) update time, for any є > 0, where f is the maximum number of sets that an element belongs to. In the decremental setting, the update time can be improved to O(f2/є5), while still obtaining an (1+є) f-approximation. These are the first algorithms that obtain an approximation factor linear in f for dynamic set cover, thereby almost matching the best bounds known in the offline setting and improving upon the previous best approximation of O(f2) in the dynamic setting.

We show that for n points in d-dimensional Euclidean space, a data oblivious random projection of the columns onto m∈ O((logk+loglogn)ε−6log1/ε) dimensions is sufficient to approximate the cost of all k-means clusterings up to a multiplicative (1±ε) factor. The previous-best upper bounds on m are O(logn· ε−2) given by a direct application of the Johnson-Lindenstrauss Lemma, and O(kε−2) given by [Cohen et al.-STOC’15].

In the directed Steiner tree (DST) problem, we are given an $n$-vertex directed edge-weighted graph, a root $r$, and a collection of $k$ terminal nodes. Our goal is to find a minimum-cost subgraph that contains a directed path from $r$ to every terminal. We present an $O(\log^2 k/\log\log{k})$-approximation algorithm for DST that runs in quasi-polynomial time, i.e., in time $n^{{poly}\log (k)}$. By assuming the projection game conjecture and ${NP}\not\subseteq{\bigcap}_{0<\epsilon<1}{ZPTIME}(2^{n^\epsilon})$ and adjusting the parameters in the hardness result of [Halperin and Krauthgamer, Polylogarithmic inapproximability, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585--594], we show the matching lower bound of $\Omega(\log^2{k}/\log\log{k})$ for the class of quasi-polynomial time algorithms, meaning that our approximation ratio is asymptotically the best possible. Our algorithm is proceeded by reducing DST to an intermediate problem, namely, the group Steiner tree on trees with dependency constraint problem, which we approximate using the framework developed by [Rothvoß, Directed Steiner Tree and the Lasserre Hierarchy, preprint, arxiv:1111.5473, 2011] and [Friggstad et al., Linear programming hierarchies suffice for directed Steiner tree, in Proceedings of the 17th Annual Conference on Integer Programming and Combinatorial Optimization, 2014, pp. 285--296].

The Tree Augmentation Problem (TAP) is a fundamental network design problem in which we are given a tree and a set of additional edges, also called links. The task is to find a set of links, of minimum size, whose addition to the tree leads to a 2-edge-connected graph. A long line of results on TAP culminated in the previously best known approximation guarantee of 1.5 achieved by a combinatorial approach due to Kortsarz and Nutov [ACM Transactions on Algorithms 2016], and also by an SDP-based approach by Cheriyan and Gao [Algorithmica 2017]. Moreover, an elegant LP-based (1.5+є)-approximation has also been found very recently by Fiorini, Groß, K'onemann, and Sanitá [SODA 2018]. In this paper, we show that an approximation factor below 1.5 can be achieved, by presenting a 1.458-approximation that is based on several new techniques.

In the unsplittable flow on a path problem (UFP) we are given a path with edge capacities and a collection of tasks. Each task is characterized by a subpath, a profit, and a demand. Our goal is to compute a maximum profit subset of tasks such that, for each edge e, the total demand of selected tasks that use e does not exceed the capacity of e. The current best polynomial-time approximation factor for this problem is 2+є for any constant є>0 [Anagostopoulos et al.-SODA 2014]. This is the best known factor even in the case of uniform edge capacities [Călinescu et al.-IPCO 2002, TALG 2011]. These results, likewise most prior work, are based on a partition of tasks into large and small depending on their ratio of demand to capacity over their respective edges: these algorithms invoke (1+є)-approximations for large and small tasks separately.

We study the problem of unsplittable flow on a path (UFP), which arises naturally in many applications such as bandwidth allocation, job scheduling, and caching. Here we are given a path with nonnegative edge capacities and a set of tasks, which are characterized by a subpath, a demand, and a profit. The goal is to find the most profitable subset of tasks whose total demand does not violate the edge capacities. Not surprisingly, this problem has received a lot of attention in the research community. If the demand of each task is at most a small-enough fraction δ of the capacity along its subpath (δ- small tasks ), then it has been known for a long time [Chekuri et al., ICALP 2003] how to compute a solution of value arbitrarily close to the optimum via LP rounding. However, much remains unknown for the complementary case, that is, when the demand of each task is at least some fraction δ > 0 of the smallest capacity of its subpath (δ- large tasks ). For this setting, a constant factor approximation is known, improving on an earlier logarithmic approximation [Bonsma et al., FOCS 2011]. In this article, we present a polynomial-time approximation scheme (PTAS) for δ-large tasks, for any constant δ > 0. Key to this result is a complex geometrically inspired dynamic program. Each task is represented as a segment underneath the capacity curve, and we identify a proper maze-like structure so that each corridor of the maze is crossed by only O (1) tasks in the optimal solution. The maze has a tree topology, which guides our dynamic program. Our result implies a 2+ε approximation for UFP, for any constant ε > 0, improving on the previously best 7+ε approximation by Bonsma et al. We remark that our improved approximation algorithm matches the best known approximation ratio for the considerably easier special case of uniform edge capacities.

No abstract available.

We study the two-dimensional geometric knapsack problem, in which we are given a set of n axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack (without rotating items). The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is 2+ε [Jansen and Zhang, SODA 2004]. In this article we present a polynomial-time 17/9+ε < 1.89-approximation, which improves to 558/325+ε < 1.72 in the cardinality case. Prior results pack items into a constant number of rectangular containers that are filled via greedy strategies. We deviate from this setting and show that there exists a large profit solution where items are packed into a constant number of containers plus one L-shaped region at the boundary of the knapsack containing narrow-high items and thin-wide items. These items may interact in complex manners at the corner of the L. The best-known approximation ratio for the subproblem in the L-shaped region is 2+ε (via a trivial reduction to one-dimensional knapsack); hence, as a second major result we present a PTAS for this case that we believe might be of broader utility. We also consider the variant with rotations, where items can be rotated by 90 degrees. Again, the best-known polynomial-time approximation factor (even for the cardinality case) is 2+ε [Jansen and Zhang, SODA 2004]. We present a polynomial-time (3/2+ε)-approximation for this setting, which improves to 4/3+ε in the cardinality case.

Consider the following variant of the set cover problem. We are given a universe U={1,...,n} and a collection of subsets C = {S_1,...,S_m} where each S_i is a subset of U. For every element u from U we need to find a set phi(u) from collection C such that u belongs to phi(u). Once we construct and fix the mapping phi from U to C a subset X from the universe U is revealed, and we need to cover all elements from X with exactly phi(X), that is {phi(u)}_{all u from X}. The goal is to find a mapping such that the cover phi(X) is as cheap as possible. This is an example of a universal problem where the solution has to be created before the actual instance to deal with is revealed. Such problems appear naturally in some settings when we need to optimize under uncertainty and it may be actually too expensive to begin finding a good solution once the input starts being revealed. A rich body of work was devoted to investigate such problems under the regime of worst case analysis, i.e., when we measure how good the solution is by looking at the worst-case ratio: universal solution for a given instance vs optimum solution for the same instance. As the universal solution is significantly more constrained, it is typical that such a worst-case ratio is actually quite big. One way to give a viewpoint on the problem that would be less vulnerable to such extreme worst-cases is to assume that the instance, for which we will have to create a solution, will be drawn randomly from some probability distribution. In this case one wants to minimize the expected value of the ratio: universal solution vs optimum solution. Here the bounds obtained are indeed smaller than when we compare to the worst-case ratio. But even in this case we still compare apples to oranges as no universal solution is able to construct the optimum solution for every possible instance. What if we would compare our approximate universal solution against an optimal universal solution that obeys the same rules as we do? We show that under this viewpoint, but still in the stochastic variant, we can indeed obtain better bounds than in the expected ratio model. For example, for the set cover problem we obtain $H_n$ approximation which matches the approximation ratio from the classic deterministic setup. Moreover, we show this for all possible probability distributions over $U$ that have a polynomially large carrier, while all previous results pertained to a model in which elements were sampled independently. Our result is based on rounding a proper configuration IP that captures the optimal universal solution, and using tools from submodular optimization. The same basic approach leads to improved approximation algorithms for other related problems, including Vertex Cover, Edge Cover, Directed Steiner Tree, Multicut, and Facility Location.

Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve the distances between given pairs of nodes exactly or with some small additive error, respectively. Since real-world networks are prone to failures, it makes sense to study fault-tolerant versions of the above structures. This turns out to be a surprisingly difficult task. For every small but arbitrary set of edge or vertex failures, the preservers and spanners need to contain replacement paths around the faulted set. Unfortunately, the complexity of the interaction between replacement paths blows up significantly, even from 1 to 2 faults, and the structure of optimal preservers and spanners is poorly understood. In particular, no nontrivial bounds for preservers and additive spanners are known when the number of faults is bigger than 2. Even the answer to the following innocent question is completely unknown: what is the worst-case size of a preserver for a single pair of nodes in the presence of f edge faults? There are no super-linear lower bounds, nor subquadratic upper bounds for f>2. In this paper we make substantial progress on this and other fundamental questions: - We present the first truly sub-quadratic size fault-tolerant single-pair preserver in unweighted (possibly directed) graphs: for any n node graph and any fixed number f of faults, O~(fn^{2-1/2^f}) size suffices. Our result also generalizes to the single-source (all targets) case, and can be used to build new fault-tolerant additive spanners (for all pairs). - The size of the above single-pair preserver grows to O(n^2) for increasing f. We show that this is necessary even in undirected unweighted graphs, and even if you allow for a small additive error: If you aim at size O(n^{2-eps}) for \eps>0, then the additive error has to be \Omega(eps f). This surprisingly matches known upper bounds in the literature. - For weighted graphs, we provide matching upper and lower bounds for the single pair case. Namely, the size of the preserver is Theta(n^2) for f > 1 in both directed and undirected graphs, while for f=1 the size is Theta(n) in undirected graphs. For directed graphs, we have a superlinear upper bound and a matching lower bound. Most of our lower bounds extend to the distance oracle setting, where rather than a subgraph we ask for any compact data structure.

In the Unsplittable Flow on a Path problem (UFP) we are given a path with non-negative edge capacities and a set of tasks, each one characterized by a subpath, a demand, and a profit. Our goal is to select a subset of tasks of maximum total profit so that the total demand of the selected tasks on each edge does not exceed the respective edge capacity. UFP naturally captures several applications in bandwidth allocation, job scheduling, and caching. Following a sequence of improvements, the current best (polynomial time) approximation factor for UFP is 2 + ∊ [Anagnostopoulos et al. SODA'14]. UFP also admits a QPTAS [Bansal et al. STOC'06, Batra et al. SODA'15], and finding a PTAS is considered a challenging open problem. In this paper we make progress in the direction of the mentioned open problem. Informally, we introduce a technique to obtain real PTASs from PTASs with resource augmentation where edge capacities can be violated by a 1 + ∊ factor. While unfortunately we do not have a resource-augmentation PTAS for the general case of UFP, for many relevant special cases we have such an algorithm or we provide one in this paper. For example, our approach leads to a PTAS for the rooted case of UFP, where all tasks share a common edge. This is one of the simplest natural restrictions of UFP where the best-known approximation was 2 + ∊ (like for the general case). At a high level, our technique is to sacrifice a few tasks in the optimal solution (with a small loss of profit) in order to create a sufficient amount of slack capacity on each edge. This slack turns out to be large enough to substitute the additional capacity we would gain from resource augmentation. Crucial for our approach is that we obtain slack from tasks with relatively small and relatively large demand simultaneously. In all prior polynomial time approximation algorithms the sacrificed tasks came from only one of these two groups.

Real-word networks are often prone to failures. A reliable network needs to cope with this situation and must provide a backup communication channel. This motivates the study of survivable network design, which has been a focus of research for a few decades. To date, survivable network design problems on undirected graphs are well-understood. For example, there is a 2 approximation in the case of edge failures [Jain, FOCS'98/Combinatorica'01]. The problems on directed graphs, in contrast, have seen very little progress. Most techniques for the undirected case like primal-dual and iterative rounding methods do not seem to extend to the directed case. Almost no non-trivial approximation algorithm is known even for a simple case where we wish to design a network that tolerates a single failure.

Kernelization is a strong and widely applied technique in parameterized complexity. In a nutshell, a kernelization algorithm for a parameterized problem transforms in polynomial time a given instance of the problem into an equivalent instance whose size depends solely on the parameter. Recent years have seen major advances in the study of both upper and lower bound techniques for kernelization, and by now this area has become one of the major research threads in parameterized complexity. In this article, we consider kernelization for problems on d -degenerate graphs, that is, graphs such that any subgraph contains a vertex of degree at most d . This graph class generalizes many classes of graphs for which effective kernelization is known to exist, for example, planar graphs, H -minor free graphs, and H -topological-minor free graphs. We show that for several natural problems on d -degenerate graphs the best-known kernelization upper bounds are essentially tight. In particular, using intricate constructions of weak compositions, we prove that unless coNP ⊆ NP/poly: • D ominating S et has no kernels of size O ( k ( d −1)( d −3)−ε ) for any ε > 0. The current best upper bound is O ( k (d+1) 2 ). • I ndependent D ominating S et has no kernels of size O ( k d −4−ε ) for any ε > 0. The current best upper bound is O ( k d +1 ). • I nduced M atching has no kernels of size O ( k d −3−ε ) for any ε > 0. The current best upper bound is O ( k d ). To the best of our knowledge, D ominating S et is the the first problem where a lower bound with superlinear dependence on d (in the exponent) can be proved. In the last section of the article, we also give simple kernels for C onnected V ertex C over and C apacitated V ertex C over of size O ( k d ) and O ( k d +1 ), respectively. We show that the latter problem has no kernels of size O ( k d −ε ) unless coNP ⊆ NP/poly by a simple reduction from d -E xact S et C over (the same lower bound for C onnected V ertex C over on d -degenerate graphs is already known).

It is a major open problem whether the (min,+)-product of two n by n matrices has a truly sub-cubic time algorithm, as it is equivalent to the famous All-Pairs-Shortest-Paths problem (APSP) in n-vertex graphs. There are some restrictions of the (min,+)-product to special types of matrices that admit truly sub-cubic algorithms, each giving rise to a special case of APSP that can be solved faster. In this paper we consider a new, different and powerful restriction in which one matrix can be arbitrary, as long as the other matrix has "bounded differences" in either its columns or rows, i.e. any two consecutive entries differ by only a small amount. We obtain the first truly sub-cubic algorithm for this Bounded Differences (min,+)-product (answering an open problem of Chan and Lewenstein). Our new algorithm, combined with a strengthening of an approach of L. Valiant for solving context-free grammar parsing with matrix multiplication, yields the first truly sub-cubic algorithms for the following problems: Language Edit Distance (a major problem in the parsing community), RNA-folding (a major problem in bioinformatics) and Optimum Stack Generation (answering an open problem of Tarjan).

We study the strip packing problem, a classical packing problem which generalizes both bin packing and makespan minimization. Here we are given a set of axis-parallel rectangles in the two-dimensional plane and the goal is to pack them in a vertical strip of fixed width such that the height of the obtained packing is minimized. The packing must be non-overlapping and the rectangles cannot be rotated. A reduction from the partition problem shows that no approximation better than 3/2 is possible for strip packing in polynomial time (assuming P!=NP). Nadiradze and Wiese [SODA16] overcame this barrier by presenting a (7/5+epsilon)-approximation algorithm in pseudo-polynomial-time (PPT). As the problem is strongly NP-hard, it does not admit an exact PPT algorithm (though a PPT approximation scheme might exist). In this paper we make further progress on the PPT approximability of strip packing, by presenting a (4/3+epsilon)-approximation algorithm. Our result is based on a non-trivial repacking of some rectangles in the "empty space" left by the construction by Nadiradze and Wiese, and in some sense pushes their approach to its limit. Our PPT algorithm can be adapted to the case where we are allowed to rotate the rectangles by 90 degrees, achieving the same approximation factor and breaking the polynomial-time approximation barrier of 3/2 for the case with rotations as well.

In the highway problem, we are given an $n$-edge path graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the associated path, when it does not exceed the budget of the driver, and zero otherwise. The goal is to choose weights so as to maximize the profit. A lot of research has been devoted to this apparently simple problem. The highway problem was shown to be strongly $\mathbf{NP}$-hard only recently [K. M. Elbassioni et al., in Proceedings of the International Symposium on Algorithmic Game Theory (SAGT), 2009, pp. 275--286]. The best-known approximation is $O(\log n/\log\log n)$ [I. Gamzu and D. Segev, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2010, pp. 582--593], which improves on the previous best $O(\log n)$ approximation [M.-F. Balcan and A. Blum, in Proceedings of the ACM Conference on Electronic Commerce, 2006, pp. 29--35]. Better approximations are known for a number of special cases. Finding a constant (or better!) approximation algorithm for the general case is a challenging open problem. In this paper we present a polynomial-time approximation scheme (PTAS) for the highway problem, hence greatly improving our understanding of the complexity status of this problem. Our result is based on a novel randomized dissection approach, which has some points in common with Arora's quadtree dissection for Euclidean network design [S. Arora, J. ACM, 45 (1998), pp. 753--782]. The basic idea is to enclose the highway in a bounding path, such that both the size of the bounding path and the position of the highway in it are random variables. Then we consider a recursive $O(1)$-ary dissection of the bounding path, in subpaths of uniform optimal weight. Since the optimal weights are unknown, we construct the dissection in a bottom-up fashion via dynamic programming, while computing the approximate solution at the same time. Our algorithm can be easily derandomized. The same basic approach also provides PTASs for two generalizations of the problem: the tollbooth problem with a constant number of leaves and the maximum-feasibility subsystem problem on interval matrices. In both cases the previous best approximation factors are polylogarithmic [I. Gamzu and D. Segev, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2010, pp. 582--593; K. M. Elbassioni et al., in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009, pp. 1210--1219].

Measuring the importance of a node in a network is a major goal in the analysis of social networks, biological systems, transportation networks etc. Different centrality measures have been proposed to capture the notion of node importance. For example, the center of a graph is a node that minimizes the maximum distance to any other node (the latter distance is the radius of the graph). The median of a graph is a node that minimizes the sum of the distances to all other nodes. Informally, the betweenness centrality of a node w measures the fraction of shortest paths that have w as an intermediate node. Finally, the reach centrality of a node w is the smallest distance r such that any s-t shortest path passing through w has either s or t in the ball of radius r around w. The fastest known algorithms to compute the center and the median of a graph, and to compute the betweenness or reach centrality even of a single node take roughly cubic time in the number n of nodes in the input graph. It is open whether these problems admit truly subcubic algorithms, i.e. algorithms with running time Õ(n3–δ) for some constant δ > 01. We relate the complexity of the mentioned centrality problems to two classical problems for which no truly subcubic algorithm is known, namely All Pairs Shortest Paths (APSP) and Diameter. We show that Radius, Median and Betweenness Centrality are equivalent under subcubic reductions to APSP, i.e. that a truly subcubic algorithm for any of these problems implies a truly subcubic algorithm for all of them. We then show that Reach Centrality is equivalent to Diameter under subcubic reductions. The same holds for the problem of approximating Betweenness Centrality within any constant factor. Thus the latter two centrality problems could potentially be solved in truly subcubic time, even if APSP requires essentially cubic time.

In the Set Connectivity problem, we are given an n-node edge-weighted undirected graph and a collection of h set pairs (Si, Ti), where Si and Ti are subsets of nodes. The goal is to compute a min-cost subgraph H so that, for each set pair (Si, Ti), there exists at least one path in H between some node in Si and some node in Ti. In this paper, we initiate the study of the Survivable Set Connectivity problem (SSC), i.e., the generalization of Set Connectivity where we are additionally given an integer requirement ki ≥ 1 for each set pair (Si, Ti), and we want to find a min-cost subgraph H so that there are at least ki edge-disjoint paths in H between Si and Ti. We achieve the following main results: We show that there is no poly-logarithmic approximation for SSC unless NP has a quasi-polynomial time algorithm. This result is based on a reduction from the Minimum Label Cover problem, and the result holds even for the special case where Si = {r} for all i, i.e., for the high-connectivity variant of the classical Group Steiner Tree problem. More precisely, we prove an approximability lower bound of 2log1−ε n for SSC, for any constant ∊ > 0, which is almost polynomial on n. A technical novelty of our proof is the first use of a padding scheme technique for an edge-connectivity problem on undirected graphs. (Prior to our results, the applications of this technique only pertain to either node-connectivity problems or problems on directed graphs). We present a bicriteria approximation algorithm for SSC that computes a solution H of cost at most poly-logarithmically larger than the optimal cost and provides a connectivity at least Ω(ki/log n) for each set pair (Si,Ti). The main algorithmic idea is to solve a standard LP relaxation to the problem, and then embed the resulting fractional capacities into a tree via Räcke's cut-based tree embeddings. Based on that, we generate a random collection of Group Steiner Tree-like fractional solutions, which can then be handled by the rounding scheme of [Garg, Konjevod and Ravi – SODA'98]. The prior work on Set Connectivity and Group Steiner Tree used Bartal's distance-based tree embeddings which do not seem to generalize to the k-connectivity versions of these problems. Finally, we remark an interesting contrast demonstrated by our results: While our hardness result almost rules out “polynomial” approximation ratios, relaxing connectivity constraints allows us to obtain “poly-logarithmic” bounds. This naturally suggests that relaxing connectivity requirements might be a proper way in getting big improvements, even beyond (non-bicriteria) lower bounds, for other connectivity problems, especially those whose approximability lower bounds are derived from Minimum Label Cover.

We study the unsplittable flow on a path problem (UFP), which arises naturally in many applications such as bandwidth allocation, job scheduling, and caching. Here we are given a path with nonnegative edge capacities and a set of tasks, which are characterized by a subpath, a demand, and a profit. The goal is to find the most profitable subset of tasks whose total demand does not violate the edge capacities. Not surprisingly this problem has received a lot of attention in the research community. If the demand of each task is at most a small enough fraction δ of the capacity along its subpath (δ-small tasks), then it has been known for a long time [Chekuri et al., ICALP 2003] how to compute a solution of value arbitrarily close to the optimum via LP rounding. However, much remains unknown for the complementary case, that is, when the demand of each task is at least some fraction δ > 0 of the smallest capacity of its subpath (δ-large tasks). For this setting a constant factor approximation, improving on an earlier logarithmic approximation, was found only recently [Bonsma et al., FOCS 2011]. In this paper we present a PTAS for δ-large tasks, for any constant δ > 0. Key to this result is a complex geometrically inspired dynamic program. Each task is represented as a segment underneath the capacity curve, and we identify a proper maze-like structure so that each corridor of the maze is crossed by only O(1) tasks in the optimal solution. The maze has a tree topology, which guides our dynamic program. Our result implies a 2 + ∊ approximation for UFP, for any constant ∊ > 0, improving on the previously best 7 + ∊ approximation by Bonsma et al. We remark that our improved approximation algorithm matches the best known approximation ratio for the considerably easier special case of uniform edge capacities.

In a classic optimization problem, the complete input data is assumed to be known to the algorithm. This assumption may not be true anymore in optimization problems motivated by the Internet where part of the input data is private knowledge of independent selfish agents. The goal of algorithmic mechanism design is to provide (in polynomial time) a solution to the optimization problem and a set of incentives for the agents such that disclosing the input data is a dominant strategy for the agents. In the case of NP-hard problems, the solution computed should also be a good approximation of the optimum. In this paper we focus on mechanism design for multiobjective optimization problems. In this setting we are given a main objective function and a set of secondary objectives which are modeled via budget constraints. Multiobjective optimization is a natural setting for mechanism design as many economical choices ask for a compromise between different, partially conflicting goals. The main contribution of this paper is showing that two of the main tools for the design of approximation algorithms for multiobjective optimization problems, namely, approximate Pareto sets and Lagrangian relaxation, can lead to truthful approximation schemes. By exploiting the method of approximate Pareto sets, we devise truthful deterministic and randomized multicriteria fully polynomial-time approximation schemes (FPTASs) for multiobjective optimization problems whose exact version admits a pseudopolynomial-time algorithm, as, for instance, the multibudgeted versions of minimum spanning tree, shortest path, maximum (perfect) matching, and matroid intersection. Our construction also applies to multidimensional knapsack and multiunit combinatorial auctions. Our FPTASs compute a $(1+\varepsilon)$-approximate solution violating each budget constraint by a factor $(1+\varepsilon)$. When feasible solutions induce an independence system, i.e., when subsets of feasible solutions are feasible as well, we present a PTAS (not violating any constraint), which combines the approach above with a novel monotone way to guess the heaviest elements in the optimum solution. Finally, we present a universally truthful Las Vegas PTAS for minimum spanning tree with a single budget constraint, where one wants to compute a minimum cost spanning tree whose length is at most a given value $L$. This result is based on the Lagrangian relaxation method, in combination with our monotone guessing step and with a random perturbation step (ensuring low expected running time). This result can be derandomized in the case of integral lengths. All the mentioned results match the best known approximation ratios, which are, however, obtained by nontruthful algorithms.

We are given a set of clients with budget constraints and a set of indivisible items. Each client is willing to buy one or more bundles of (at most) k items each (bundles can be seen as hyperedges in a k-hypergraph). If client i gets a bundle e, she pays bi,e and yields a net profit wi,e. The Hypermatching Assignment Problem (HAP) is to assign a set of pairwise disjoint bundles to clients so as to maximize the total profit while respecting the budgets. This problem has various applications in production planning and budget-constrained auctions and generalizes well-studied problems in combinatorial optimization: for example the weighted (unweighted) k-hypergraph matching problem is the special case of HAP with one client having unbounded budget and general (unit) profits; the Generalized Assignment Problem (GAP) is the special case of HAP with k = 1. Let ε > 0 denote an arbitrarily small constant. In this paper we obtain the following main results: We give a randomized (k + 1 + ∊) approximation algorithm for HAP, which is based on rounding the 1-round Lasserre strengthening of a novel LP. This is one of a few approximation results based on Lasserre hierarchies and our approach might be of independent interest. We remark that for weighted k-hypergraph matching no LP nor SDP relaxation is known to have integrality gap better than k − 1 + 1/k for general k [Chan and Lau, SODA'10]. For the relevant special case that one wants to maximize the total revenue (i.e., bi,e = wi,e), we present a local search based (k + O(√k))/2 approximation algorithm for k = O(1). This almost matches the best known (k + 1 + ∊)/2 approximation ratio by Berman [SWAT'00] for the (less general) weighted k-hypergraph matching problem. For the unweighted k-hypergraph matching problem, we present a (k + 1 + ∊)/3 approximation in quasipolynomial time. This improves over the (k + 2)/3 approximation by Halldórsson [SODA'95] (also in quasipolynomial time). In particular this suggests that a 4/3 + ∊ approximation for 3-dimensional matching might exist, whereas the currently best known polynomial-time approximation ratio is 3/2.

Given an undirected n-node unweighted graph G = (V, E), a spanner with stretch function f(.) is a subgraph H \subseteq G such that, if two nodes are at distance d in G, then they are at distance at most f(d) in H. Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function. In this paper we study pairwise spanners, where we require to approximate the u-v distance only for pairs (u,v) in a given set P \subseteq V x V. Such P-spanners were studied before [Coppersmith,Elkin'05] only in the special case that f(.) is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers). Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same P) and of the best known spanners (with the same f(.)). In more detail, for arbitrary P, we show that there exists a P-spanner of size O(n(|P|log n)^{1/4}) with f(d) = d + 4 log n. Alternatively, for any epsislon > 0, there exists a P-spanner of size O(n|P|^{1/4} sqrt{(log n) / epsilon}) with f(d) = (1 + epsilon)d + 4. We also consider the relevant special case that there is a critical set of nodes S \subseteq V, and we wish to approximate either the distances within nodes in S or from nodes in S to any other node. We show that there exists an (S x S)-spanner of size O(n sqrt{|S|}) with f(d) = d + 2, and an (S x V)-spanner of size O(n sqrt{|S| log n}) with f(d) = d + 2 log n. All the mentioned pairwise spanners can be constructed in polynomial time.

The Steiner tree problem is one of the most fundamental NP -hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to 1.55 [Robins and Zelikovsky 2005]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP relaxation of Steiner tree with integrality gap smaller than 2 [Rajagopalan and Vazirani 1999]. In this article we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most ln(4) + ε < 1.39 times the cost of an optimal Steiner tree. The algorithm can be derandomized using the method of limited independence. As a by-product of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering the mentioned open question.

Given a universe $U$ of $n$ elements and a weighted collection $\mathscr{S}$ of $m$ subsets of $U$, the universal set cover problem is to a priori map each element $u \in U$ to a set $S(u) \in \mathscr{S}$ containing $u$ such that any set $X{\subseteq U}$ is covered by $S(X)=\cup_{u\in XS(u)$. The aim is to find a mapping such that the cost of $S(X)$ is as close as possible to the optimal set cover cost for $X$. (Such problems are also called oblivious or a priori optimization problems.) Unfortunately, for every universal mapping, the cost of $S(X)$ can be $\Omega(\sqrt{n})$ times larger than optimal if the set $X$ is adversarially chosen. In this paper we study the performance on average, when $X$ is a set of randomly chosen elements from the universe: we show how to efficiently find a universal map whose expected cost is $O(\log mn)$ times the expected optimal cost. In fact, we give a slightly improved analysis and show that this is the best possible. We generalize these ideas to weighted set cover and show similar guarantees to (nonmetric) facility location, where we have to balance the facility opening cost with the cost of connecting clients to the facilities. We show applications of our results to universal multicut and disc-covering problems and show how all these universal mappings give us algorithms for the stochastic online variants of the problems with the same competitive factors.

A distance sensitivity oracle is a data structure which, given two nodes s and t in a directed edge-weighted graph G and an edge e, returns the shortest length of an s-t path not containing e, a so called replacement path for the triple (s, t, e). Such oracles are used to quickly recover from edge failures. In this paper we consider the case of integer weights in the interval [-M, M], and present the first distance sensitivity oracle that achieves simultaneously subcubic preprocessing time and sublinear query time. More precisely, for a given parameter α ∈ [0, 1], our oracle has preprocessing time Õ(Mnω+1/2+Mnω+α(4-ω)) and query time Õ(n1-α). Here wω+1-α) preprocessing time and (superlinear) Õ(n1+α) query time [Weimann, Yuster-FOCS'10]. The main novelty in our approach is an algorithm to compute all the replacement paths from a given source s, an interesting problem on its own. We can solve the latter single-source replacement paths problem in Õ(APSP(n, M))) time, where APSP(n, M)0.681n2.575) [Zwick-JACM'02] is the runtime for computing all-pairs shortest paths in a graph with n vertices and integer edge weights in [-M, M]. For positive weights the runtime of our algorithm reduces to Õ(Mnω). This matches the best known runtime for the simpler replacement paths problem in which both the source s and the target t are fixed [Vassilevska-SODA'11].

In a classical covering problem, we are given a set of requests that we need to satisfy (fully or partially), by buying a subset of items at minimum cost. For example, in the k-MST problem we want to find the cheapest tree spanning at least k nodes of an edge-weighted graph. Here, nodes represent requests whereas edges correspond to items. In this paper, we initiate the study of a new family of multi-layer covering problems. Each such problem consists of a collection of h distinct instances of a standard covering problem (layers), with the constraint that all layers share the same set of requests. We identify two main subfamilies of these problems: - in an union multi-layer problem, a request is satisfied if it is satisfied in at least one layer; - in an intersection multi-layer problem, a request is satisfied if it is satisfied in all layers. To see some natural applications, consider both generalizations of k-MST. Union k-MST can model a problem where we are asked to connect a set of users to at least one of two communication networks, e.g., a wireless and a wired network. On the other hand, Intersection k-MST can formalize the problem of providing both electricity and water to at least k users.

In the highway problem, we are given an n-edge line graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the associated path, when it does not exceed the budget of the driver, and zero otherwise. The goal is choosing weights so as to maximize the profit. A lot of research has been devoted to this apparently simple problem. The highway problem was shown to be strongly NP-hard only recently [Elbassioni, Raman, Ray, Sitters-'09]. The best-known approximation is O(log n/log log n) [Gamzu, Segev-'10], which improves on the previous-best O(log n) approximation [Balcan, Blum-'06]. Better approximations are known for a number of special cases. Finding a constant (or better!) approximation algorithm for the general case is a challenging open problem. In this paper we present a PTAS for the highway problem, hence closing the complexity status of the problem. Our result is based on a novel randomized dissection approach, which has some points in common with Arora's quadtree dissection for Euclidean network design [Arora-'98]. The basic idea is enclosing the highway in a bounding path, such that both the size of the bounding path and the position of the highway in it are random variables. Then we consider a recursive O(1)-ary dissection of the bounding path, in sub-paths of uniform optimal weight. Since the optimal weights are unknown, we construct the dissection in a bottom-up fashion via dynamic programming, while computing the approximate solution at the same time. Our algorithm can be easily derandomized. The same basic approach provides PTASs also for two generalizations of the problem: the tollbooth problem with a constant number of leaves and the maximum-feasibility subsystem problem on interval matrices. In both cases the previous best approximation factors are polylogarithmic [Gamzu, Segev-'10, Elbassioni, Raman, Ray, Sitters-'09].

In a classic optimization problem the complete input data is known to the algorithm. This assumption may not be true anymore in optimization problems motivated by the Internet where part of the input data is private knowledge of independent selfish agents. The goal of algorithmic mechanism design is to provide (in polynomial time) a solution to the optimization problem and a set of incentives for the agents such that disclosing the input data is a dominant strategy for the agents. In case of NP-hard problems, the solution computed should also be a good approximation of the optimum. In this paper we focus on mechanism design for multi-objective optimization problems, where we are given the main objective function, and a set of secondary objectives which are modeled via budget constraints. Multi-objective optimization is a natural setting for mechanism design as many economical choices ask for a compromise between different, partially conflicting, goals. Our main contribution is showing that two of the main tools for the design of approximation algorithms for multi-objective optimization problems, namely approximate Pareto curves and Lagrangian relaxation, can lead to truthful approximation schemes. By exploiting the method of approximate Pareto curves, we devise truthful FPTASs for multi-objective optimization problems whose exact version admits a pseudo-polynomial-time algorithm, as for instance the multi-budgeted versions of minimum spanning tree, shortest path, maximum (perfect) matching, and matroid intersection. Our technique applies also to multi-dimensional knapsack and multi-unit combinatorial auctions. Our FPTASs compute a (1 + ε)-approximate solution violating each budget constraint by a factor (1 + ε). For a relevant sub-class of the mentioned problems we also present a PTAS (not violating any constraint), which combines the approach above with a novel monotone way to guess the heaviest elements in the optimum solution. Finally we present a universally truthful Las Vegas PTAS for minimum spanning tree with a single budget constraint. This result is based on the Lagrangian relaxation method, in combination with our monotone guessing step and a random perturbation step (ensuring low expected running time in a way similar to the smoothed analysis of algorithms). All the mentioned results match the best known approximation ratios, which however are obtained by non-truthful algorithms.

The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to the current best 1.55 [Robins,Zelikovsky-SIDMA'05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than 2 [Vazirani,Rajagopalan-SODA'99]. In this paper we improve the approximation factor for Steiner tree, developing an LP-based approximation algorithm. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider a directed-component cut relaxation for the k-restricted Steiner tree problem. We sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. We iterate this process for a proper number of times and finally output the sampled components together with a minimum-cost terminal spanning tree in the remaining graph. Our algorithm delivers a solution of cost at most ln(4) times the cost of an optimal k-restricted Steiner tree. This directly implies a ln(4)+ε<1.39 approximation for Steiner tree. As a byproduct of our analysis, we show that the integrality gap of our LP is at most $1.55$, hence answering to the mentioned open question. This might have consequences for a number of related problems.

For more than 40 years, Branch & Reduce exponential-time backtracking algorithms have been among the most common tools used for finding exact solutions of NP-hard problems. Despite that, the way to analyze such recursive algorithms is still far from producing tight worst-case running time bounds. Motivated by this, we use an approach, that we call “Measure & Conquer”, as an attempt to step beyond such limitations. The approach is based on the careful design of a nonstandard measure of the subproblem size; this measure is then used to lower bound the progress made by the algorithm at each branching step. The idea is that a smarter measure may capture behaviors of the algorithm that a standard measure might not be able to exploit, and hence lead to a significantly better worst-case time analysis. In order to show the potentialities of Measure & Conquer, we consider two well-studied NP-hard problems: minimum dominating set and maximum independent set. For the first problem, we consider the current best algorithm, and prove (thanks to a better measure) a much tighter running time bound for it. For the second problem, we describe a new, simple algorithm, and show that its running time is competitive with the current best time bounds, achieved with far more complicated algorithms (and standard analysis). Our examples show that a good choice of the measure, made in the very first stages of exact algorithms design, can have a tremendous impact on the running time bounds achievable.

We address the problem of designing data structures in the presence of faults that may arbitrarily corrupt memory locations. More precisely, we assume that an adaptive adversary can arbitrarily overwrite the content of up to δ memory locations, that corrupted locations cannot be detected, and that only O (1) memory locations are safe. In this framework, we call a data structure resilient if it is able to operate correctly (at least) on the set of uncorrupted values. We present a resilient dictionary, implementing search, insert, and delete operations. Our dictionary has O (log n + δ) expected amortized time per operation, and O ( n ) space complexity, where n denotes the current number of keys in the dictionary. We also describe a deterministic resilient dictionary, with the same amortized cost per operation over a sequence of at least δ ϵ operations, where ϵ > 0 is an arbitrary constant. Finally, we show that any resilient comparison-based dictionary must take Ω(log n + δ) expected time per search. Our results are achieved by means of simple, new techniques which might be of independent interest for the design of other resilient algorithms.

Given a universe U of n elements and a weighted collection l of m subsets of U, the universal set cover problem is to a-priori map each element u epsi U to a set S(u) epsi l containing u, so that X sube U is covered by S(X)=UuepsiXS(u). The aim is finding a mapping such that the cost of S(X) is as close as possible to the optimal set-cover cost for X. (Such problems are also called oblivious or a-priori optimization problems.) Unfortunately, for every universal mapping, the cost of S(X) can be Omega(radicn) times larger than optimal if the set X is adversarially chosen. In this paper we study the performance on average, when X is a set of randomly chosen elements from the universe: we show how to efficiently find a universal map whose expected cost is O(log mn) times the expected optimal cost. In fact, we give a slightly improved analysis and show that this is the best possible. We generalize these ideas to weighted set cover and show similar guarantees to (non-metric) facility location, where we have to balance the facility opening cost with the cost of connecting clients to the facilities. We show applications of our results to universal multi-cut and disc-covering problems, and show how all these universal mappings give us stochastic online algorithms with the same competitive factors.

In this paper we consider the capacitated vertex cover problem, which is the variant of vertex cover where each node is allowed to cover a limited number of edges. We present an efficient, deterministic, distributed approximation algorithm for the problem. Our algorithm computes a $(2+\epsilon)$-approximate solution which violates the capacity constraints by a factor of $(4+\epsilon)$ in a polylogarithmic number of communication rounds. On the other hand, we also show that every efficient distributed approximation algorithm for this problem must violate the capacity constraints. Our result is achieved in two steps. We first develop a 2-approximate, sequential primal-dual algorithm that violates the capacity constraints by a factor of 2. Subsequently, we present a distributed version of this algorithm. We demonstrate that the sequential algorithm has an inherent need for synchronization which forces any naive distributed implementation to use a linear number of communication rounds. The challenge in this step is therefore to achieve a reduction of the communication complexity to a polylogarithmic number of rounds without worsening the approximation guarantee.

We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O (1.7159 n ). This result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a graph on n vertices is at most 1.7159 n , thus improving on the trivial O (2 n /√ n ) bound. Our result makes use of the measure-and-conquer technique which was recently developed in the area of exact algorithms. Based on this result, we derive an O (2.8718 n ) algorithm for the domatic number problem.

In this article, we consider the problem of computing a minimum-weight vertex-cover in an n -node, weighted, undirected graph G = ( V , E ). We present a fully distributed algorithm for computing vertex covers of weight at most twice the optimum, in the case of integer weights. Our algorithm runs in an expected number of O (log n + log Ŵ ) communication rounds, where Ŵ is the average vertex-weight. The previous best algorithm for this problem requires O (log n (log n + log Ŵ )) rounds and it is not fully distributed. For a maximal matching M in G , it is a well-known fact that any vertex-cover in G needs to have at least | M | vertices. Our algorithm is based on a generalization of this combinatorial lower-bound to the weighted setting.

Virtual private network design is the following NP-hard problem. We are given a communication network represented as a weighted graph with thresholds on the nodes which represent the amount of flow that a node can send to and receive from the network. The task is to reserve capacities at minimum cost and to specify paths between every ordered pair of nodes such that all valid traffic-matrices can be routed along the corresponding paths. Recently, this network design problem has received considerable attention in the literature. It is motivated by the fact that the exact amount of flow which is exchanged between terminals is not known in advance and prediction is often elusive. The main contributions of this paper are as follows: (1) Using Hu's 2-commodity flow theorem, we provide a new and considerably stronger lower bound on the cost of an optimum solution. With this lower bound we reanalyze a simple routing scheme which has been described in the literature many times, and provide an improved upper bound on its approximation ratio. (2) We present a new randomized approximation algorithm. In contrast to earlier approaches from the literature, the resulting solution does not have tree structure. A combination of our new algorithm with the simple routing scheme yields an expected performance ratio of $3.79$ for virtual private network design. This is a considerable improvement of the previously best known $5.55$-approximation result [A. Gupta, A. Kumar, and T. Roughgarden, Simpler and better approximation algorithms for network design, in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365–372]. (3) Our VPND algorithm uses a Steiner tree approximation algorithm as a subroutine. It is known that an optimum Steiner tree can be computed in polynomial time if the number of terminals is logarithmic. Replacing the approximate Steiner tree computation with an exact one whenever the number of terminals is sufficiently small, we finally reduce the approximation ratio to $3.55$. To the best of our knowledge, this is the first time that a nontrivial result from exact (exponential) algorithms leads to an improved polynomial-time approximation algorithm.

In this paper we consider the weighted, capacitated vertex cover problem with hard capacities (capVC). Here, we are given an undirected graph G = (V, E), non-negative vertex weightswtv for all vertices v ∈ V, and node-capacities Bv ≥ 1 for all v ∈ V. A feasible solution to a givencapVC instance consists of a vertex cover C ⊆ V. Each edge e ∈ E is assigned to one of its endpoints in C and the number of edges assigned to any vertex v ∈ C is at most Bv. The goal is to minimize the total weight of C. For a parameter ɛ> 0 we give a deterministic, distributed algorithm for thecapVC problem that computes a vertex cover C of weight at most (2+ɛ)·opt whereopt is the weight of a minimumweight feasible solution to the given instance. The number of edges assigned to any node v ∈ C is at most (4 + ɛ) · Bv. The running time of our algorithm is O(log(nW)/ɛ), where n is the number of nodes in the network and W = wtmax/wtmin is the ratio of largest to smallest weight. This result is complemented by a lower-bound saying that any distributed algorithm forcapVC which requires a poly-logarithmic number of rounds is bound to violate the capacity constraints by a factor two. The main feature of the algorithm is that it is derived in a systematic fashion starting from a primal-dual sequential algorithm.