Search

We study rectangle stabbing problems in which we are given n axis-aligned rectangles in the plane that we want to stab, that is, we want to select line segments such that for each given rectangle there is a line segment that intersects two opposite edges of it. In the horizontal rectangle stabbing problem (Stabbing), the goal is to find a set of horizontal line segments of minimum total length such that all rectangles are stabbed. In the horizontal–vertical stabbing problem (HV-Stabbing), the goal is to find a set of rectilinear (that is, either vertical or horizontal) line segments of minimum total length such that all rectangles are stabbed. Both variants are NP-hard. Chan et al. (ISAAC, 2018) initiated the study of these problems by providing constant approximation algorithms. Recently, Eisenbrand et al. (A QPTAS for stabbing rectangles, 2021) have presented a QPTAS and a polynomial-time 8-approximation algorithm for Stabbing, but it was open whether the problem admits a PTAS. In this paper, we obtain a PTAS for Stabbing, settling this question. For HV-Stabbing, we obtain a (2 + ε) -approximation. We also obtain PTASs for special cases of HV-Stabbing: (i) when all rectangles are squares, (ii) when each rectangle's width is at most its height, and (iii) when all rectangles are δ -large, that is, have at least one edge whose length is at least δ , while all edge lengths are at most 1. Our result also implies improved approximations for other problems such as generalized minimum Manhattan network. [ABSTRACT FROM AUTHOR]

In generalized malleable scheduling, jobs can be allocated and processed simultaneously on multiple machines so as to reduce the overall makespan of the schedule. The required processing time for each job is determined by the joint processing speed of the allocated machines. We study the case that processing speeds are job-dependent M ♮ -concave functions and provide a constant-factor approximation for this setting, significantly expanding the realm of functions for which such an approximation is possible. Further, we explore the connection between malleable scheduling and the problem of fairly allocating items to a set of agents with distinct utility functions, devising a black-box reduction that allows to obtain resource-augmented approximation algorithms for the latter. [ABSTRACT FROM AUTHOR]

In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ratio of the total capacity on the edges of G crossing the cut over the total demand of the crossing edges of D. In this work, we study the non-uniform sparsest cut problem for supply graphs with bounded treewidth k. For this case, Gupta et al. (ACM STOC, 2013) obtained a 2-approximation with polynomial running time for fixed k, and it remained open the question of whether there exists a c-approximation algorithm for a constant c independent of k, that runs in FPT time. We answer this question in the affirmative. We design a 2-approximation algorithm for the non-uniform sparsest cut with bounded treewidth supply graphs that runs in FPT time, when parameterized by the treewidth. Our algorithm is based on rounding the optimal solution of a linear programming relaxation inspired by the Sherali-Adams hierarchy. In contrast to the classic Sherali-Adams approach, we construct a relaxation driven by a tree decomposition of the supply graph by including a carefully chosen set of lifting variables and constraints to encode information of subsets of nodes with super-constant size, and at the same time we have a sufficiently small linear program that can be solved in FPT time. [ABSTRACT FROM AUTHOR]

We consider the class of disjoint bilinear programs max { x T y ∣ x ∈ X , y ∈ Y } where X and Y are packing polytopes. We present an O (log log m 1 log m 1 log log m 2 log m 2 ) -approximation algorithm for this problem where m 1 and m 2 are the number of packing constraints in X and Y respectively. In particular, we show that there exists a near-optimal solution (x ~ , y ~) such that x ~ and y ~ are "near-integral". We give an LP relaxation of the problem from which we obtain the near-optimal near-integral solution via randomized rounding. We show that our relaxation is tightly related to the widely used reformulation linearization technique. As an application of our techniques, we present a tight approximation for the two-stage adjustable robust optimization problem with covering constraints and right-hand side uncertainty where the separation problem is a bilinear optimization problem. In particular, based on the ideas above, we give an LP restriction of the two-stage problem that is an O (log n log log n log L log log L) -approximation where L is the number of constraints in the uncertainty set. This significantly improves over state-of-the-art approximation bounds known for this problem. Furthermore, we show that our LP restriction gives a feasible affine policy for the two-stage robust problem with the same (or better) objective value. As a consequence, affine policies give an O (log n log log n log L log log L) -approximation of the two-stage problem, significantly generalizing the previously known bounds on their performance. [ABSTRACT FROM AUTHOR]

The Connectivity Augmentation Problem (CAP) together with a well-known special case thereof known as the Tree Augmentation Problem (TAP) are among the most basic Network Design problems. There has been a surge of interest recently to find approximation algorithms with guarantees below 2 for both TAP and CAP, culminating in the currently best approximation factor for both problems of 1.393 through quite sophisticated techniques. We present a new and arguably simple matching-based method for the well-known special case of leaf-to-leaf instances. Combining our work with prior techniques, we readily obtain a (4 / 3 + ε) -approximation for Leaf-to-Leaf CAP by returning the better of our solution and one of an existing method. Prior to our work, a 4 / 3 -guarantee was only known for Leaf-to-Leaf TAP instances on trees of height 2. Moreover, when combining our technique with a recently introduced stack analysis approach, which is part of the above-mentioned 1.393-approximation, we can further improve the approximation factor to 1.29, obtaining for the first time a factor below 4 3 for a nontrivial class of TAP/CAP instances. [ABSTRACT FROM AUTHOR]

We present approximation algorithms for several network design problems in the model of flexible graph connectivity (Adjiashvili et al., in: IPCO, pp 13–26, 2020, Math Program 1–33, 2021). Let k ≥ 1 , p ≥ 1 and q ≥ 0 be integers. In an instance of the (p, q)-Flexible Graph Connectivity problem, denoted (p , q) -FGC , we have an undirected connected graph G = (V , E) , a partition of E into a set of safe edges S and a set of unsafe edges U , and nonnegative costs c : E → R ≥ 0 on the edges. A subset F ⊆ E of edges is feasible for the (p , q) -FGC problem if for any set F ′ ⊆ U with | F ′ | ≤ q , the subgraph (V , F \ F ′) is p-edge connected. The algorithmic goal is to find a feasible solution F that minimizes c (F) = ∑ e ∈ F c e . We present a simple 2-approximation algorithm for the (1 , 1) -FGC problem via a reduction to the minimum-cost rooted 2-arborescence problem. This improves on the 2.527-approximation algorithm of Adjiashvili et al. Our 2-approximation algorithm for the (1 , 1) -FGC problem extends to a (k + 1) -approximation algorithm for the (1 , k) -FGC problem. We present a 4-approximation algorithm for the (k , 1) -FGC problem, and an O (q log | V |) -approximation algorithm for the (p , q) -FGC problem. Finally, we improve on the result of Adjiashvili et al. for the unweighted (1 , 1) -FGC problem by presenting a 16/11-approximation algorithm. The (p , q) -FGC problem is related to the well-known Capacitatedk-Connected Subgraph problem (denoted Cap- k -ECSS ) that arises in the area of Capacitated Network Design. We give a min (k , 2 u max) -approximation algorithm for the Cap- k -ECSS problem, where u max denotes the maximum capacity of an edge. [ABSTRACT FROM AUTHOR]

We initiate the work on maximin share (MMS) fair allocation of m indivisible chores to n agents using only their ordinal preferences, from both algorithmic and mechanism design perspectives. The previous best-known approximation ratio using ordinal preferences is 2 - 1 / n by Aziz et al. [AAAI 2017]. We improve this result by giving a deterministic 5/3-approximation algorithm that determines an allocation sequence of agents, according to which items are allocated one by one. By a tighter analysis, we show that for n = 2 and 3, our algorithm achieves better approximation ratios, and is actually optimal. We also consider the setting with strategic agents, where agents may misreport their preferences to manipulate the outcome. We first provide a strategyproof O (log (m / n)) -approximation consecutive picking algorithm, and then improve the approximation ratio to O (log n) by a randomized algorithm. Both algorithms only use the ordinal preferences of agents. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods. [ABSTRACT FROM AUTHOR]

In this paper, we give an algorithm that finds an ϵ -approximate solution to a mixed integer quadratic programming (MIQP) problem. The algorithm runs in polynomial time if the rank of the quadratic function and the number of integer variables are fixed. The running time of the algorithm is expected unless P = NP. In order to design this algorithm we introduce the novel concepts of spherical form MIQP and of aligned vectors, and we provide a number of results of independent interest. In particular, we give a strongly polynomial algorithm to find a symmetric decomposition of a matrix, and show a related result on simultaneous diagonalization of matrices. [ABSTRACT FROM AUTHOR]

Many network design problems deal with the design of low-cost networks that are resilient to the failure of their elements (such as nodes or links). One such problem is Connectivity Augmentation, with the goal of cheaply increasing the (edge- or node-)connectivity of a given network from a value k to k + 1 . The problem is NP-hard for k ≥ 1 , and the most studied setting focuses on the case of edge-connectivity with k = 1 . In this work, we give a 1.892-approximation algorithm for the NP-hard problem of augmenting the node-connectivity of any given graph from 1 to 2, which improves upon the state-of-the-art approximation previously developed in the literature. The starting point of our work is a known reduction from Connectivity Augmentation to some specific instances of the Node-Steiner Tree problem, and our result is obtained by developing a new and simple analysis of the iterative randomized rounding technique when applied to such Steiner Tree instances. Our results also imply a 1.892-approximation algorithm for the problem of augmenting the edge-connectivity of a given graph from any value k to k + 1 . While this does not beat the best approximation factor known for this problem, a key point of our work is that the analysis of our approximation factor is less involved when compared to previous results in the literature. In addition, our work gives new insights on the iterative randomized rounding method, that might be of independent interest. [ABSTRACT FROM AUTHOR]

We consider the problem of interdicting a directed graph by deleting nodes with the goal of minimizing the local edge connectivity of the remaining graph from a given source to a sink. We introduce and study a general downgrading variant of the interdiction problem where the capacity of an arc is a function of the subset of its endpoints that are downgraded, and the goal is to minimize the downgraded capacity of a minimum source-sink cut subject to a node downgrading budget. This models the case when both ends of an arc must be downgraded to remove it, for example. For this generalization, we provide a bicriteria (4, 2)-approximation that downgrades nodes with total weight at most 4 times the budget and provides a solution where the downgraded connectivity from the source to the sink is at most 2 times that in an optimal solution. We accomplish this with an LP relaxation and rounding using a ball-growing algorithm based on the LP values. Furthermore, we show that other bicriteria approximations exist where one can worsen the approximation factor for one of the costs in order to improve the other. We further generalize the downgrading problem to one where each vertex can be downgraded to one of k levels, and the arc capacities are functions of the pairs of levels to which its ends are downgraded. We generalize our LP rounding to get a (4k, 4k)-approximation for this case. Trade-offs between the two approximation ratios similar to the two-level case also exist for the generalized problem. By transferring node values to edge values, we also derive new bicriteria approximation results for the vertex interdiction versions of the multiway cut problem in digraphs and multicut problems in undirected graphs. [ABSTRACT FROM AUTHOR]

We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the rooted Subtree Prune-and-Regraft (rSPR) distance between two phylogenetic trees. Our algorithm is combinatorial and its running time is quadratic in the input size. To prove the approximation guarantee, we construct a feasible dual solution for a novel exponential-size linear programming formulation. In addition, we show this linear program has a smaller integrality gap than previously known formulations, and we give an equivalent compact formulation, showing that it can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of n items, each associated with a non-negative weight, and T time periods with non-decreasing capacities W 1 ≤ ⋯ ≤ W T . When item i is inserted at time t, we gain a profit of p it ; however, this item remains in the knapsack for all subsequent periods. The goal is to decide if and when to insert each item, subject to the time-dependent capacity constraints, with the objective of maximizing our total profit. Interestingly, this setting subsumes as special cases a number of recently-studied incremental knapsack problems, all known to be strongly NP-hard. Our first contribution comes in the form of a polynomial-time (1 2 - ϵ) -approximation for the generalized incremental knapsack problem. This result is based on a reformulation as a single-machine sequencing problem, which is addressed by blending dynamic programming techniques and the classical Shmoys–Tardos algorithm for the generalized assignment problem. Combined with further enumeration-based self-reinforcing ideas and new structural properties of nearly-optimal solutions, we turn our algorithm into a quasi-polynomial time approximation scheme (QPTAS). Hence, under widely believed complexity assumptions, this finding rules out the possibility that generalized incremental knapsack is APX-hard. [ABSTRACT FROM AUTHOR]

While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of 2 for the unweighted matching problem, it was only recently that Paz and Schwartzman obtained an analogous result for weighted instances. Their approach is based on the versatile local ratio technique and also applies to generalizations such as weighted hypergraph matchings. However, the framework for the analysis fails for the related problem of weighted matroid intersection and as a result the approximation guarantee for weighted instances did not match the factor 2 achieved by the greedy algorithm for unweighted instances.Our main result closes this gap by developing a semi-streaming algorithm with an approximation guarantee of 2 + ε for weighted matroid intersection, improving upon the previous best guarantee of 4 + ε . Our techniques also allow us to generalize recent results by Levin and Wajc on submodular maximization subject to matching constraints to that of matroid-intersection constraints. While our algorithm is an adaptation of the local ratio technique used in previous works, the analysis deviates significantly and relies on structural properties of matroid intersection, called kernels. Finally, we also conjecture that our algorithm gives a (k + ε) approximation for the intersection of k matroids but prove that new tools are needed in the analysis as the structural properties we use fail for k ≥ 3 . [ABSTRACT FROM AUTHOR]

We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for the unit-demand case and the splittable variant. Our results hold in arbitrary metric spaces. This is the first improvement upon the classical tour partitioning algorithm by Haimovich and Rinnooy Kan (Math Oper Res 10:527–542, 1985) and Altinkemer and Gavish (Oper Res Lett 6:149–158, 1987). [ABSTRACT FROM AUTHOR]

We consider the graph k-partitioning problem under the min-max objective, termed as Minmax k -cut. The input here is a graph G = (V , E) with non-negative integral edge weights w : E → Z + and an integer k ≥ 2 and the goal is to partition the vertices into k non-empty parts V 1 , ... , V k so as to minimize max i = 1 k w (δ (V i)) . Although minimizing the sum objective ∑ i = 1 k w (δ (V i)) , termed as Minsum k -cut, has been studied extensively in the literature, very little is known about minimizing the max objective. We initiate the study of Minmax k -cut by showing that it is NP-hard and W[1]-hard when parameterized by k, and design a parameterized approximation scheme when parameterized by k. The main ingredient of our parameterized approximation scheme is an exact algorithm for Minmax k -cut that runs in time (λ k) O (k 2) n O (1) + O (m) , where λ is value of the optimum, n is the number of vertices, and m is the number of edges. Our algorithmic technique builds on the technique of Lokshtanov, Saurabh, and Surianarayanan (FOCS, 2020) who showed a similar result for Minsum k -cut. Our algorithmic techniques are more general and can be used to obtain parameterized approximation schemes for minimizing ℓ p -norm measures of k-partitioning for every p ≥ 1 . [ABSTRACT FROM AUTHOR]

We revisit the deadline version of the discrete time-cost tradeoff problem for the special case of bounded depth. Such instances occur for example in VLSI design. The depth of an instance is the number of jobs in a longest chain and is denoted by d. We prove new upper and lower bounds on the approximability. First we observe that the problem can be regarded as a special case of finding a minimum-weight vertex cover in a d-partite hypergraph. Next, we study the natural LP relaxation, which can be solved in polynomial time for fixed d and—for time-cost tradeoff instances—up to an arbitrarily small error in general. Improving on prior work of Lovász and of Aharoni, Holzman and Krivelevich, we describe a deterministic algorithm with approximation ratio slightly less than d 2 for minimum-weight vertex cover in d-partite hypergraphs for fixed d and given d-partition. This is tight and yields also a d 2 -approximation algorithm for general time-cost tradeoff instances, even if d is not fixed. We also study the inapproximability and show that no better approximation ratio than d + 2 4 is possible, assuming the Unique Games Conjecture and P ≠ NP . This strengthens a result of Svensson [21], who showed that under the same assumptions no constant-factor approximation algorithm exists for general time-cost tradeoff instances (of unbounded depth). Previously, only APX-hardness was known for bounded depth. [ABSTRACT FROM AUTHOR]

Since 1997 there has been a steady stream of advances for the maximum disjoint paths problem. Achieving tractable results has usually required focusing on relaxations such as: (i) to allow some bounded edge congestion in solutions, (ii) to only consider the unit weight (cardinality) setting, (iii) to only require fractional routability of the selected demands (the all-or-nothing flow setting). For the general form (no congestion, general weights, integral routing) of edge-disjoint paths (edp) even the case of unit capacity trees which are stars generalizes the maximum matching problem for which Edmonds provided an exact algorithm. For general capacitated trees, Garg, Vazirani, Yannakakis showed the problem is APX-Hard and Chekuri, Mydlarz, Shepherd provided a 4-approximation. This is essentially the only setting where a constant approximation is known for the general form of edp. We extend their result by giving a constant-factor approximation algorithm for general-form edp in outerplanar graphs. A key component for the algorithm is to find a single-treeO(1) cut approximator for outerplanar graphs. Previously O(1) cut approximators were only known via distributions on trees and these were based implicitly on the results of Gupta, Newman, Rabinovich and Sinclair for distance tree embeddings combined with results of Anderson and Feige. [ABSTRACT FROM AUTHOR]

We give the first 2-approximation algorithm for the cluster vertex deletion problem. This approximation factor is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines previous approaches, based on the local ratio technique and the management of twins, with a novel construction of a "good" cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem. [ABSTRACT FROM AUTHOR]

This paper discusses an outer-approximation guided optimization method for constrained neural network inverse problems with rectified linear units. The constrained neural network inverse problems refer to an optimization problem to find the best set of input values of a given trained neural network in order to produce a predefined desired output in presence of constraints on input values. This paper analyzes the characteristics of optimal solutions of neural network inverse problems with rectified activation units and proposes an outer-approximation algorithm by exploiting their characteristics. The proposed outer-approximation guided optimization comprises primal and dual phases. The primal phase incorporates neighbor curvatures with neighbor outer-approximations to expedite the process. The dual phase identifies and utilizes the structure of local convex regions to improve the convergence to a local optimal solution. At last, computation experiments demonstrate the superiority of the proposed algorithm compared to a projected gradient method. [ABSTRACT FROM AUTHOR]

The network reconfiguration problem seeks to find a rooted tree T such that the energy of the (unique) feasible electrical flow over T is minimized. The tree requirement on the support of the flow is motivated by operational constraints in electricity distribution networks. The bulk of existing results on convex optimization over vertices of polytopes and on the structure of electrical flows do not easily give guarantees for this problem, while many heuristic methods have been developed in the power systems community as early as 1989. Our main contribution is to give the first provable approximation guarantees for the network reconfiguration problem. We provide novel lower bounds and corresponding approximation factors for various settings ranging from min { O (m - n) , O (n) } for general graphs, to O (n) over grids with uniform resistances on edges, and O (1) for grids with uniform edge resistances and demands. To obtain the result for general graphs, we propose a new method for (approximate) spectral graph sparsification, which may be of independent interest. Using insights from our theoretical results, we propose a general heuristic for the network reconfiguration problem that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance. [ABSTRACT FROM AUTHOR]

We study the nonlinear newsvendor problem concerning goods of a non-discrete nature, and a class of stochastic dynamic programs with several application areas such as supply chain management and economics. The class is characterized by continuous state and action spaces, either convex or monotone cost functions that are accessed via value oracles, and affine transition functions. We establish that these problems cannot be approximated to any degree of either relative or additive error, regardless of the scheme used. To circumvent these hardness results, we generalize the concept of fully polynomial-time approximation scheme allowing arbitrarily small additive and multiplicative error at the same time, while requiring a polynomial running time in the input size and the error parameters. We develop approximation schemes of this type for the classes of problems mentioned above. In light of our hardness results, such approximation schemes are "best possible". A computational evaluation shows the promise of this approach. [ABSTRACT FROM AUTHOR]

In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-multicut-gap. We consider instances where the union of the supply and demand graphs is planar and prove that there exists a multiflow of value at least half the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer flow of value at least half the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing at most half the value thus providing a 1/4-approximation algorithm and integrality gap for maximum integer multiflows in the plane. [ABSTRACT FROM AUTHOR]

This paper considers approximation algorithms for generalized k-median problems. These problems can be informally described as k-median with a constant number of extra constraints, and includes k-median with outliers, and knapsack median. Our first contribution is a pseudo-approximation algorithm for generalized k-median that outputs a 6.387-approximate solution, with a constant number of fractional variables. The algorithm builds on the iterative rounding framework introduced by Krishnaswamy, Li, and Sandeep for k-median with outliers as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018). The main technical innovation is allowing richer constraint sets in the iterative rounding and using the structure of the resulting extreme points. Using our pseudo-approximation algorithm, we give improved approximation algorithms for k-median with outliers and knapsack median. This involves combining our pseudo-approximation with pre- and post-processing steps to round a constant number of fractional variables at a small increase in cost. Our algorithms achieve approximation ratios 6.994+ϵ\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$6.994 + \epsilon $$\end{document} and 6.387+ϵ\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$6.387 + \epsilon $$\end{document} for k-median with outliers and knapsack median, respectively. These improve on the best-known approximation ratio 7.081+ϵ\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$7.081 + \epsilon $$\end{document} for both problems as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018). [ABSTRACT FROM AUTHOR]

We consider a problem of maximizing a monotone DR-submodular function under multiple order-consistent knapsack constraints on a distributive lattice. Because a distributive lattice is used to represent a dependency constraint, the problem can represent a dependency constrained version of a submodular maximization problem on a set. We propose a ( 1 - 1 / e )-approximation algorithm for this problem. To achieve this result, we generalize the continuous greedy algorithm to distributive lattices: We choose a median complex as a continuous relaxation of the distributive lattice and define the multilinear extension on it. We show that the median complex admits special curves, named uniform linear motions. The multilinear extension of a DR-submodular function is concave along a positive uniform linear motion, which is a key property used in the continuous greedy algorithm. [ABSTRACT FROM AUTHOR]

A displacement aggregation strategy is proposed for the curvature pairs stored in a limited-memory BFGS (a.k.a. L-BFGS) method such that the resulting (inverse) Hessian approximations are equal to those that would be derived from a full-memory BFGS method. This means that, if a sufficiently large number of pairs are stored, then an optimization algorithm employing the limited-memory method can achieve the same theoretical convergence properties as when full-memory (inverse) Hessian approximations are stored and employed, such as a local superlinear rate of convergence under assumptions that are common for attaining such guarantees. To the best of our knowledge, this is the first work in which a local superlinear convergence rate guarantee is offered by a quasi-Newton scheme that does not either store all curvature pairs throughout the entire run of the optimization algorithm or store an explicit (inverse) Hessian approximation. Numerical results are presented to show that displacement aggregation within an adaptive L-BFGS scheme can lead to better performance than standard L-BFGS. [ABSTRACT FROM AUTHOR]

We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of n tasks and m resources, where each task j uses some subset of the resources. Tasks have random sizes X j , and our goal is to non-adaptively select t tasks to minimize the expected maximum load over all resources, where the load on any resource i is the total size of all selected tasks that use i. For example, when resources are points and tasks are intervals in a line, we obtain an O (log log m) -approximation algorithm. Our technique is also applicable to other problems with some geometric structure in the relation between tasks and resources; e.g., packing paths, rectangles, and "fat" objects. Our approach uses a strong LP relaxation using the cumulant generating functions of the random variables. We also show that this LP has an Ω (log ∗ m) integrality gap, even for the problem of selecting intervals on a line; here log ∗ m is the iterated logarithm function. [ABSTRACT FROM AUTHOR]

In the classic maximum coverage problem, we are given subsets T 1 , ... , T m of a universe [n] along with an integer k and the objective is to find a subset S ⊆ [ m ] of size k that maximizes C (S) : = | ∪ i ∈ S T i | . It is well-known that the greedy algorithm for this problem achieves an approximation ratio of (1 - e - 1) and there is a matching inapproximability result. We note that in the maximum coverage problem if an element e ∈ [ n ] is covered by several sets, it is still counted only once. By contrast, if we change the problem and count each element e as many times as it is covered, then we obtain a linear objective function, C (∞) (S) = ∑ i ∈ S | T i | , which can be easily maximized under a cardinality constraint. We study the maximum ℓ -multi-coverage problem which naturally interpolates between these two extremes. In this problem, an element can be counted up to ℓ times but no more; hence, we consider maximizing the function C (ℓ) (S) = ∑ e ∈ [ n ] min { ℓ , | { i ∈ S : e ∈ T i } | } , subject to the constraint | S | ≤ k . Note that the case of ℓ = 1 corresponds to the standard maximum coverage setting and ℓ = ∞ gives us a linear objective. We develop an efficient approximation algorithm that achieves an approximation ratio of 1 - ℓ ℓ e - ℓ ℓ ! for the ℓ -multi-coverage problem. In particular, when ℓ = 2 , this factor is 1 - 2 e - 2 ≈ 0.73 and as ℓ grows the approximation ratio behaves as 1 - 1 2 π ℓ . We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture. This problem is motivated by the question of finding a code that optimizes the list-decoding success probability for a given noisy channel. We show how the multi-coverage problem can be relevant in other contexts, such as combinatorial auctions. [ABSTRACT FROM AUTHOR]

We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are APX -hard to approximate and present constant-factor approximation algorithms based upon two different algorithmic techniques: a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation, and a greedy strategy. We further show that a combination of these techniques can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of these algorithms for problem instances arising in the context of real-world gas transport networks. [ABSTRACT FROM AUTHOR]

An instance of colorfulk-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius ρ such that there exist balls of radius ρ around k of the points that meet the coverage requirements. The motivation behind this problem is twofold. First, from fairness considerations: each color/group should receive a similar service guarantee, and second, from the algorithmic challenges it poses: this problem combines the difficulties of clustering along with the subset-sum problem. In particular, we show that this combination results in strong integrality gap lower bounds for several natural linear programming relaxations. Our main result is an efficient approximation algorithm that overcomes these difficulties to achieve an approximation guarantee of 3, nearly matching the tight approximation guarantee of 2 for the classical k-center problem which this problem generalizes. algorithms either opened more than k centers or only worked in the special case when the input points are in the plane. [ABSTRACT FROM AUTHOR]

We introduce and study the problem Flexible Graph Connectivity, which in contrast to many classical connectivity problems features a non-uniform failure model. We distinguish between safe and unsafe resources and postulate that failures can only occur among the unsafe resources. Given an undirected edge-weighted graph and a set of unsafe edges, the task is to find a minimum-cost subgraph that remains connected after removing at most k unsafe edges. We give constant-factor approximation algorithms for this problem for k = 1 as well as for unit costs and k ≥ 1 . Our approximation guarantees are close to the known best bounds for special cases, such as the 2-edge-connected spanning subgraph problem and the tree augmentation problem. Our algorithm and analysis combine various techniques including a weight-scaling algorithm, a charging argument that uses a variant of exchange bijections between spanning trees and a factor revealing min–max–min optimization problem. [ABSTRACT FROM AUTHOR]

There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the k-Center problem in this spirit are Colorful k-Center, introduced by Bandyapadhyay, Inamdar, Pai, and Varadarajan, and lottery models, such as the Fair Robust k-Center problem introduced by Harris, Pensyl, Srinivasan, and Trinh. To address fairness aspects, these models, compared to traditional k-Center, include additional covering constraints. Prior approximation results for these models require to relax some of the normally hard constraints, like the number of centers to be opened or the involved covering constraints, and therefore, only obtain constant-factor pseudo-approximations. In this paper, we introduce a new approach to deal with such covering constraints that leads to (true) approximations, including a 4-approximation for Colorful k-Center with constantly many colors—settling an open question raised by Bandyapadhyay, Inamdar, Pai, and Varadarajan—and a 4-approximation for Fair Robust k-Center, for which the existence of a (true) constant-factor approximation was also open. We complement our results by showing that if one allows an unbounded number of colors, then Colorful k-Center admits no approximation algorithm with finite approximation guarantee, assuming that P ≠ NP . Moreover, under the Exponential Time Hypothesis, the problem is inapproximable if the number of colors grows faster than logarithmic in the size of the ground set. [ABSTRACT FROM AUTHOR]

In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we are given a rooted tree with edge weights and a subset of vertices of the tree 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 root of the tree 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.For the special case when all terminals have equal demands, a long line of research culminated in a quasi-polynomial time approximation scheme [Jayaprakash and Salavatipour, TALG 2023] and a polynomial time approximation scheme [Mathieu and Zhou, TALG 2023].In this work, we study the general case when the terminals have arbitrary demands. Our main contribution is a polynomial time (1.5+ϵ)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(1.5+\epsilon )$$\end{document}-approximation algorithm for the UCVRP on trees. This is the first improvement upon the 2-approximation algorithm more than 30 years ago. Our approximation ratio is essentially best possible, since it is NP-hard to approximate the UCVRP on trees to better than a 1.5 factor. [ABSTRACT FROM AUTHOR]

Relaxation and rounding approaches became a standard and extremely versatile tool for constrained submodular function maximization. One of the most common rounding techniques in this context are contention resolution schemes. Such schemes round a fractional point by first rounding each coordinate independently, and then dropping some elements to reach a feasible set. Also the second step, where elements are dropped, is typically randomized. This leads to an additional source of randomization within the procedure, which can complicate the analysis. We suggest a different, polyhedral viewpoint to design contention resolution schemes, which avoids to deal explicitly with the randomization in the second step. This is achieved by focusing on the marginals of a dropping procedure. Apart from avoiding one source of randomization, our viewpoint allows for employing polyhedral techniques. Both can significantly simplify the construction and analysis of contention resolution schemes. We show how, through our framework, one can obtain an optimal monotone contention resolution scheme for bipartite matchings, which has a balancedness of 0.4762. So far, only very few results are known about optimality of monotone contention resolution schemes. Our contention resolution scheme for the bipartite case also improves the lower bound on the correlation gap for bipartite matchings. Furthermore, we derive a monotone contention resolution scheme for matchings that significantly improves over the previously best one. More precisely, we obtain a balancedness of 0.4326, improving on a prior 0.1997-balanced scheme. At the same time, our scheme implies that the currently best lower bound on the correlation gap for matchings is not tight. Our results lead to improved approximation factors for various constrained submodular function maximization problems over a combination of matching constraints with further constraints. [ABSTRACT FROM AUTHOR]

The goal of scenario reduction is to approximate a given discrete distribution with another discrete distribution that has fewer atoms. We distinguish continuous scenario reduction, where the new atoms may be chosen freely, and discrete scenario reduction, where the new atoms must be chosen from among the existing ones. Using the Wasserstein distance as measure of proximity between distributions, we identify those n-point distributions on the unit ball that are least susceptible to scenario reduction, i.e., that have maximum Wasserstein distance to their closest m-point distributions for some prescribed m < n . We also provide sharp bounds on the added benefit of continuous over discrete scenario reduction. Finally, to our best knowledge, we propose the first polynomial-time constant-factor approximations for both discrete and continuous scenario reduction as well as the first exact exponential-time algorithms for continuous scenario reduction. [ABSTRACT FROM AUTHOR]

In a Stackelberg Pricing Game a distinguished player, the leader, chooses prices for a set of items, and the other players, the followers, each seek to buy a minimum cost feasible subset of the items. The goal of the leader is to maximize her revenue, which is determined by the sold items and their prices. Most previously studied cases of such games can be captured by a combinatorial model where we have a base set of items, some with fixed prices, some priceable, and constraints on the subsets that are feasible for each follower. In this combinatorial setting, Briest et al. and Balcan et al. independently showed that the maximum revenue can be approximated to a factor of H k ∼ log k , where k is the number of priceable items. Our results are twofold. First, we strongly generalize the model by letting the follower minimize any continuous function plus a linear term over any compact subset of R ≥ 0 n ; the coefficients (or prices) in the linear term are chosen by the leader and determine her revenue. In particular, this includes the fundamental case of linear programs. We give a tight lower bound on the revenue of the leader, generalizing the results of Briest et al. and Balcan et al. Besides, we prove that it is strongly NP-hard to decide whether the optimum revenue exceeds the lower bound by an arbitrarily small factor. Second, we study the parameterized complexity of computing the optimal revenue with respect to the number k of priceable items. In the combinatorial setting, given an efficient algorithm for optimal follower solutions, the maximum revenue can be found by enumerating the 2 k subsets of priceable items and computing optimal prices via a result of Briest et al., giving time O (2 k | I | c) where |I| is the input size. Our main result here is a W[1]-hardness proof for the case where the followers minimize a linear program, ruling out running time f (k) | I | c unless FPT = W [ 1 ] and ruling out time | I | o (k) under the Exponential-Time Hypothesis. [ABSTRACT FROM AUTHOR]

The truncated singular value decomposition (SVD), also known as the best low-rank matrix approximation with minimum error measured by a unitarily invariant norm, has been applied to many domains such as biology, healthcare, among others, where high-dimensional datasets are prevalent. To extract interpretable information from the high-dimensional data, sparse truncated SVD (SSVD) has been used to select a handful of rows and columns of the original matrix along with the best low-rank approximation. Different from the literature on SSVD focusing on the top singular value or compromising the sparsity for the seek of computational efficiency, this paper presents a novel SSVD formulation that can select the best submatrix precisely up to a given size to maximize its truncated Ky Fan norm. The fact that the proposed SSVD problem is NP-hard motivates us to study effective algorithms with provable performance guarantees. To do so, we first reformulate SSVD as a mixed-integer semidefinite program, which can be solved exactly for small- or medium-sized instances within a branch-and-cut algorithm framework with closed-form cuts and is extremely useful for evaluating the solution quality of approximation algorithms. We next develop three selection algorithms based on different selection criteria and two searching algorithms, greedy and local search. We prove the approximation ratios for all the approximation algorithms and show that all the ratios are tight when the number of rows or columns of the selected submatrix is no larger than half of the data matrix, i.e., our derived approximation ratios are unimprovable. Our numerical study demonstrates the high solution quality and computational efficiency of the proposed algorithms. Finally, all our analysis can be extended to row-sparse PCA. [ABSTRACT FROM AUTHOR]

Motivated by the well known "four-thirds conjecture" for the traveling salesman problem (TSP), we study the problem of uniform covers. A graph G = (V , E) has an α -uniform cover for TSP (2EC, respectively) if the everywhere α vector (i.e., { α } E ) dominates a convex combination of incidence vectors of tours (2-edge-connected spanning multigraphs, respectively). The polyhedral analysis of Christofides' algorithm directly implies that a 3-edge-connected, cubic graph has a 1-uniform cover for TSP. Sebő asked if such graphs have (1 - ϵ) -uniform covers for TSP for some ϵ > 0 . Indeed, the four-thirds conjecture implies that such graphs have 8 9 -uniform covers. We show that these graphs have 18 19 -uniform covers for TSP. We also study uniform covers for 2EC and show that the everywhere 15 17 vector can be efficiently written as a convex combination of 2-edge-connected spanning multigraphs. For a weighted, 3-edge-connected, cubic graph, our results show that if the everywhere 2 3 vector is an optimal solution for the subtour elimination linear programming relaxation for TSP, then a tour with weight at most 27 19 times that of an optimal tour can be found efficiently. Node-weighted, 3-edge-connected, cubic graphs fall into this category. In this special case, we can apply our tools to obtain an even better approximation guarantee. An essential ingredient in our proofs is decompositions of graphs (e.g., cycle covers) that cover small-cardinality cuts an even (nonzero) number of times. Another essential tool we use is half-integral tree augmentation, which is known to have a small integrality gap. To extend our approach to input graphs that are 2-edge-connected, we present a procedure to decompose a point in the subtour elimination polytope into spanning, connected subgraphs that cover each 2-edge cut an even number of times. Using this decomposition, we obtain a 17 12 -approximation algorithm for minimum weight 2-edge-connected spanning subgraphs on subcubic, node-weighted graphs. [ABSTRACT FROM AUTHOR]

In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal, so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for k ≥ 3 is APX-hard. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrák (Proceedings of the forty-sixth annual ACM symposium on theory of computing, STOC, 2014) while the best known inapproximability result due to Angelidakis et al. (Integer programming and combinatorial optimization, IPCO, 2017) rules out efficient algorithms to achieve an approximation factor less than 1.2 under the unique games conjecture (UGC). In this work, we improve the lower bound to 1.20016 under UGC by constructing an integrality gap instance for the CKR relaxation. The CKR relaxation embeds the graph into a simplex and it is known that its integrality gap translates to inapproximability under UGC. A technical challenge in improving the integrality gap has been the lack of geometric tools to understand higher-dimensional simplices. Our instance is a non-trivial 3-dimensional instance that overcomes this technical challenge. We analyze the gap of the instance by viewing it as a convex combination of 2-dimensional instances and a uniform 3-dimensional instance. We believe that this technique could be exploited further to construct instances with larger integrality gap. One of the ingredients of our proof technique is a generalization of a result on Sperner admissible labelings due to Mirzakhani and Vondrák (Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, SODA, 2015) that might be of independent combinatorial interest. [ABSTRACT FROM AUTHOR]

The sum of squares (SoS) hierarchy gives an automatized technique to create a family of increasingly tight convex relaxations for binary programs. There are several problems for which a constant number of rounds of this hierarchy give integrality gaps matching the best known approximation algorithms. For many other problems, however, ad-hoc techniques give better approximation ratios than SoS in the worst case, as shown by corresponding lower bound instances. Notably, in many cases these instances are invariant under the action of a large permutation group. This yields the question how symmetries in a formulation degrade the performance of the relaxation obtained by the SoS hierarchy. In this paper, we study this for the case of the minimum makespan problem on identical machines. Our first result is to show that Ω (n) rounds of SoS applied over the configuration linear program yields an integrality gap of at least 1.0009, where n is the number of jobs. This improves on the recent work by Kurpisz et al. (Math Program 172(1–2):231–248, 2018) that shows an analogous result for the weaker LS + and SA hierarchies. Our result is based on tools from representation theory of symmetric groups. Then, we consider the weaker assignment linear program and add a well chosen set of symmetry breaking inequalities that removes a subset of the machine permutation symmetries. We show that applying 2 O ~ (1 / ε 2) rounds of the SA hierarchy to this stronger linear program reduces the integrality gap to 1 + ε , which yields a linear programming based polynomial time approximation scheme. Our results suggest that for this classical problem, symmetries were the main barrier preventing the SoS / SA hierarchies to give relaxations of polynomial complexity with an integrality gap of 1 + ε . We leave as an open question whether this phenomenon occurs for other symmetric problems. [ABSTRACT FROM AUTHOR]

We consider approximation algorithms for packing integer programs (PIPs) of the form max { ⟨ c , x ⟩ : A x ≤ b , x ∈ { 0 , 1 } n } where A, b and c are nonnegative. We let W = min i , j b i / A i , j denote the width of A which is at least 1. Previous work by Bansal et al. (Theory Comput 8(24):533–565, 2012) obtained an Ω (1 Δ 0 1 / ⌊ W ⌋ ) -approximation ratio where Δ 0 is the maximum number of nonzeroes in any column of A (in other words the ℓ 0 -column sparsity of A). They raised the question of obtaining approximation ratios based on the ℓ 1 -column sparsity of A (denoted by Δ 1 ) which can be much smaller than Δ 0 . Motivated by recent work on covering integer programs (Chekuri and Quanrud, in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1596–1615. SIAM, 2019; Chen et al., in: Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1984–2003. SIAM, 2016) we show that simple algorithms based on randomized rounding followed by alteration, similar to those of Bansal et al. (Theory Comput 8(24):533–565, 2012) (but with a twist), yield approximation ratios for PIPs based on Δ 1 . First, following an integrality gap example from (Theory Comput 8(24):533–565, 2012), we observe that the case of W = 1 is as hard as maximum independent set even when Δ 1 ≤ 2 . In sharp contrast to this negative result, as soon as width is strictly larger than one, we obtain positive results via the natural LP relaxation. For PIPs with width W = 1 + ϵ where ϵ ∈ (0 , 1 ] , we obtain an Ω (ϵ 2 / Δ 1) -approximation. In the large width regime, when W ≥ 2 , we obtain an Ω ((1 1 + Δ 1 / W) 1 / (W - 1)) -approximation. We also obtain a (1 - ϵ) -approximation when W = Ω (log (Δ 1 / ϵ) ϵ 2) . Viewing the rounding algorithms as contention resolution schemes, we obtain approximation algorithms in the more general setting when the objective is a non-negative submodular function. [ABSTRACT FROM AUTHOR]

We show that the classical LP relaxation of the asymmetric traveling salesman path problem (ATSPP) has constant integrality ratio. If ρ ATSP and ρ ATSPP denote the integrality ratios for the asymmetric TSP and its path version, then ρ ATSPP ≤ 4 ρ ATSP - 3 . We prove an even better bound for node-weighted instances: if the integrality ratio for ATSP on node-weighted instances is ρ ATSP N W , then the integrality ratio for ATSPP on node-weighted instances is at most 2 ρ ATSP N W - 1 . Moreover, we show that for ATSP node-weighted instances and unweighted digraph instances are almost equivalent. From this we deduce a lower bound of 2 on the integrality ratio of unweighted digraph instances. [ABSTRACT FROM AUTHOR]

We study the problem of deleting a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. This problem is often called cluster vertex deletion in the literature and admits a straightforward 3-approximation algorithm since it is a special case of the vertex cover problem on a 3-uniform hypergraph. Recently, You, Wang, and Cao described an efficient 5/2-approximation algorithm for the unweighted version of the problem. Our main result is a 9/4-approximation algorithm for arbitrary weights, using the local ratio technique. We further conjecture that the problem admits a 2-approximation algorithm and give some support for the conjecture. This is in sharp contrast with the fact that the similar problem of deleting vertices to eliminate all triangles in a graph is known to be UGC-hard to approximate to within a ratio better than 3, as proved by Guruswami and Lee. [ABSTRACT FROM AUTHOR]

We consider a stochastic variant of the packing-type integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entry of the objective vector by conducting a query, and the task is to find a good solution by conducting a small number of queries. We propose a general framework of adaptive and non-adaptive algorithms for this problem, and provide a unified methodology for analyzing the performance of those algorithms. We also demonstrate our framework by applying it to a variety of stochastic combinatorial optimization problems such as matching, matroid, and stable set problems. [ABSTRACT FROM AUTHOR]

We present a 7 4 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a reduction of any given MAP instance to a collection of well-structured MAP instances such that the approximation guarantee is preserved. Then we present a 7 4 approximation algorithm for a well-structured MAP instance. The algorithm starts with a min-cost 2-edge cover and then applies ear-augmentation steps. We analyze the cost of the ear-augmentations using an approach similar to the one proposed by Vempala and Vetta for the (unweighted) min-size 2-ECSS problem (in: Jansen and Khuller (eds.) Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Proceedings, LNCS 1913, pp.262–273, Springer, Berlin, 2000). [ABSTRACT FROM AUTHOR]

We develop an algorithm for minimax problems that arise in robust optimization in the absence of objective function derivatives. The algorithm utilizes an extension of methods for inexact outer approximation in sampling a potentially infinite-cardinality uncertainty set. Clarke stationarity of the algorithm output is established alongside desirable features of the model-based trust-region subproblems encountered. We demonstrate the practical benefits of the algorithm on a new class of test problems. [ABSTRACT FROM AUTHOR]

In this paper, we propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a (1 - ϵ) -approximate solution with a running time significantly faster than most known exact algorithms. The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. More precisely, we show that we can solve the weighted matroid intersection problem via solving W instances of the unweighted matroid intersection problem, where W is the largest given weight, assuming that all given weights are integral. Furthermore, we can find a (1 - ϵ) -approximate solution via solving O (ϵ - 1 log r) instances of the unweighted matroid intersection problem, where r is the smaller rank of the two given matroids. Our algorithms make use of the weight-splitting approach of Frank (J Algorithms 2(4):328–336, 1981) and the geometric scaling scheme of Duan and Pettie (J ACM 61(1):1, 2014). Our algorithms are simple and flexible: they can be adapted to special cases of the weighted matroid intersection problem, using specialized unweighted matroid intersection algorithms. In addition, we give a further application of our decomposition technique: we solve efficiently the rank-maximal matroid intersection problem, a problem motivated by matching problems under preferences. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) and an integer k ∈ N , we study k -Vertex Separator (resp. k -Edge Separator), where the goal is to remove the minimum number of vertices (resp. edges) such that each connected component in the resulting graph has less than k vertices. We also study k -Path Transversal, where the goal is to remove the minimum number of vertices such that there is no simple path of length k. Our main results are the following improved approximation algorithms. O (log k) -approximation algorithm for k -Vertex Separator that runs in time 2 O (k) n + n O (1) . It improves the simple k-approximation, and runs faster than the lower bound k Ω (OPT) n Ω (1) for exact algorithms assuming the exponential time hypothesis (ETH) when OPT > k . We also prove that there is no n (1 / log log n) c -approximation algorithm that runs in time poly (n , k) assuming the ETH. O (log k) -approximation algorithm for k -Edge Separator that runs in time n O (1) . It improves the best previous graph partitioning algorithm for small k = n o (1) . O (log k) -approximation algorithm for k -Path Transversal that runs in time n O (1) + 2 O (k 3 log k) n 2 log n . Previously, the existence of an (1 - δ) k -approximation algorithm for fixed δ > 0 (even using n f (k) time) was open. [ABSTRACT FROM AUTHOR]

In the last two decades, a steady stream of research has been devoted to studying various computational aspects of the ordered k-median problem, which subsumes traditional facility location problems (such as median, center, p-centrum, etc.) through a unified modeling approach. Given a finite metric space, the objective is to locate k facilities in order to minimize the ordered median cost function. In its general form, this function penalizes the coverage distance of each vertex by a multiplicative weight, depending on its ranking (or percentile) in the ordered list of all coverage distances. While antecedent literature has focused on mathematical properties of ordered median functions, integer programming methods, various heuristics, and special cases, this problem was not studied thus far through the lens of approximation algorithms. In particular, even on simple network topologies, such as trees or line graphs, obtaining non-trivial approximation guarantees is an open question. The main contribution of this paper is to devise the first provably-good approximation algorithms for the ordered k-median problem. We develop a novel approach that relies primarily on a surrogate model, where the ordered median function is replaced by a simplified ranking-invariant functional form, via efficient enumeration. Surprisingly, while this surrogate model is Ω (n Ω (1)) -hard to approximate on general metrics, we obtain an O (log n) -approximation for our original problem by employing local search methods on a smooth variant of the surrogate function. In addition, an improved guarantee of 2 + ϵ is obtained on tree metrics by optimally solving the surrogate model through dynamic programming. Finally, we show that the latter optimality gap is tight up to an O (ϵ) term. [ABSTRACT FROM AUTHOR]

In this paper, we study the performance of static solutions in two-stage adjustable robust packing linear optimization problem with uncertain constraint coefficients. Such problems arise in many important applications such as revenue management and resource allocation problems where demand requests have uncertain resource requirements. The goal is to find a two-stage solution that maximizes the worst case objective value over all possible realizations of the second-stage constraints from a given uncertainty set. We consider the case where the uncertainty set is column-wise and constraint-wise (any constraint describing the set involve entries of only a single column or a single row). This is a fairly general class of uncertainty sets to model constraint coefficient uncertainty. We show that the two-stage adjustable robust problem is Ω(logn)-hard to approximate. On the positive side, we show that a static solution is an O(logn·min(logΓ,log(m+n)))-approximation for the two-stage adjustable robust problem where m and n denote the numbers of rows and columns of the constraint matrix and Γ is the maximum possible ratio of upper bounds of the uncertain constraint coefficients. Therefore, for constant Γ, surprisingly the performance bound for static solutions and therefore, the adaptivity gap matches the hardness of approximation for the adjustable problems. Furthermore, in general the static solution provides nearly the best efficient approximation for the two-stage adjustable robust problem. [ABSTRACT FROM AUTHOR]

We study the Unsplittable Flow problem (UFP) on trees with a submodular objective function. The input to this problem is a tree with edge capacities and a collection of tasks, each characterized by a source node, a sink node, and a demand. A subset of the tasks is feasible if the tasks can simultaneously send their demands from the source to the sink without violating the edge capacities. The goal is to select a feasible subset of the tasks that maximizes a submodular objective function. Our main result is an O(klogn)-approximation algorithm for Submodular UFP on trees where k denotes the pathwidth of the given tree. Since every tree has pathwidth O(logn), we obtain an O(log2n) approximation for arbitrary trees. This is the first non-trivial approximation guarantee for the problem, matching the best known approximation ratio for UFP on trees with a linear objective function. Our main technical contribution is a new geometric relaxation for UFP on trees that builds on the recent work of Bonsma et al. (2014, FOCS), Anagnostopoulos et al. (Amazing 2+ϵ approximation for unsplittable flow on a path, SIAM, pp 26-41, 2014) for UFP on paths with a linear objective. Our relaxation is very structured, so it can be combined with the contention resolution framework of Chekuri et al. (2009, STOC). Our approach is robust and extends to several related problems, such as UFP with bag constraints and the Storage Allocation Problem. Additionally, we study the special case of UFP on trees with a linear objective and upward instances where, for each task, the source node is a descendant of the sink node. Such instances generalize UFP on paths. We build on the work of Bansal et al. (A quasi-PTAS for unsplittable flow on line graphs, ACM, pp 721-729, 2006) for UFP on paths and obtain a QPTAS for upward instances when the input data is quasi-polynomially bounded. We complement this result by showing that, unlike the path setting, upward instances are APX-hard if the input data is arbitrary. [ABSTRACT FROM AUTHOR]