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.

We give improved approximations for two metric Traveling Salesman Problem (TSP) variants. In Ordered TSP (OTSP) we are given a linear ordering on a subset of nodes o1,. .., ok. The TSP solution must have that o i+1 is visited at some point after Oi for each 1 ≤ i ≤ k. This is the special case of Precedence- Constrained TSP (PTSP) in which the precedence constraints are given by a single chain on a subset of nodes. In k-Person TSP Path (k-TSPP), we are given pairs of nodes (s1, t1), …, (sk, tk ). The goal is to find an si-ti path with minimum total cost such that every node is visited by at least one path.

We study the classic (Uncapacitated) Facility Location problem on Unit Disk Graphs (UDGs). For a given point set P in the plane, the unit disk graph UDG(P) on P has vertex set P and an edge between two distinct points p, q ∈ P if and only if their Euclidean distance |pq| is at most 1. The weight of the edge pq is equal to their distance |pq|. An instance of {Facility Location} on UDG(P) consists of a set C ⊆ P of clients and a set F ⊆ P of facilities, each having an opening cost f_i. The goal is to pick a subset F' ⊆ F to open while minimizing ∑_{i ∈ F'} f_i + ∑_{v ∈ C} d(v,F'), where d(v,F') is the distance of v to nearest facility in F' through UDG(P). In this paper, we present the first Quasi-Polynomial Time Approximation Schemes (QPTAS) for the problem. While approximation schemes are well-established for facility location problems on sparse geometric graphs (such as planar graphs), there is a lack of such results for dense graphs. Specifically, prior to this study, to the best of our knowledge, there was no approximation scheme for any facility location problem on UDGs in the general setting.

The act of telling stories is a fundamental part of what it means to be human. This work introduces the concept of narrative information, which we define as the overlap in information space between a story and the items that compose the story. Using contrastive learning methods, we show how modern artificial neural networks can be leveraged to distill stories and extract a representation of the narrative information. We then demonstrate how evolutionary algorithms can leverage this to extract a set of narrative template curves and how these-in tandem with a novel curve-fitting algorithm we introduce-can reorder music albums to automatically induce stories in them. In doing so, we give statistically significant evidence that (1) these narrative information template curves are present in existing albums and that (2) people prefer an album ordered through one of these learned template curves over a random one. The premises of our work extend to any form of (largely) independent media, and as evidence, we also show that our method works with image data.

Abstract. We investigate the complexity of solving stable or perturbation-resilient instances of [Formula: see text]-means and [Formula: see text]-median clustering in fixed-dimensional Euclidean metrics (or more generally doubling metrics). The notion of stable or perturbation-resilient instances was introduced by Bilu and Linial [ Are stable instances easy?, 2010] and Awasthi, Blum, and Sheffet [ Stability yields a PTAS for k-median and k-means clustering, IEEE Computer Society, Washington, DC, 2010]. In our context, we say a [Formula: see text]-means instance is [Formula: see text]-stable if there is a unique optimum solution which remains unchanged if distances are (nonuniformly) stretched by a factor of at most [Formula: see text]. Stable clustering instances have been studied to explain why heuristics such as Lloyd’s algorithm perform well in practice. In this work we show that for any fixed [Formula: see text], [Formula: see text]-stable instances of [Formula: see text]-means in doubling metrics, which include fixed-dimensional Euclidean metrics, can be solved in polynomial time. More precisely, we show a natural multiswap local-search algorithm in fact finds the optimum solution for [Formula: see text]-stable instances of [Formula: see text]-means and [Formula: see text]-median in a polynomial number of iterations. We complement this result by showing that it is essentially tight: when the dimension [Formula: see text] is part of the input there is a fixed [Formula: see text] such that there is not even a PTAS for [Formula: see text]-stable [Formula: see text]-means in [Formula: see text] with [Formula: see text] unless NP = RP. To do this, we consider a robust property of CSPs: call an instance stable if there is a unique optimum solution [Formula: see text] and for any other solution [Formula: see text], the number of unsatisfied clauses is proportional to the Hamming distance between [Formula: see text] and [Formula: see text]. Dinur, Goldreich, and Gur have already shown stable QSAT is hard to approximate for some constant [Formula: see text] [ 20 ]. Recently, Paradise [ Comput. Complexity, 30 (2021), 1] extended this to the setting with bounded variable occurrence. More specifically, this implies that stable QSAT with bounded variable occurrence is APX-hard. Given this, we consider “stability-preserving” reductions to prove our hardness for stable [Formula: see text]-means. Such reductions seem to be more fragile and intricate than standard [Formula: see text]-reductions and may be of further use to demonstrate other stable optimization problems are hard to solve.

We present a \(O(\log k)\) -approximation for both the edge-weighted and node-weighted versions of Directed Steiner Tree in planar graphs where \( k \) is the number of terminals. We extend our approach to Multi-Rooted Directed Steiner Tree , in which we get a \(O(R+\log k)\) -approximation for planar graphs for which \( R \) is the number of roots.

We give the first constant-factor approximation algorithm for quasi-bipartite instances of Directed Steiner Tree on graphs that exclude fixed minors. In particular, for $K_r$-minor-free graphs our approximation guarantee is $O(r\cdot\sqrt{\log r})$ and, further, for planar graphs our approximation guarantee is 20. Our algorithm uses the primal-dual scheme. We employ a more involved method of determining when to buy an edge while raising dual variables since, as we show, the natural primal-dual scheme fails to raise enough dual value to pay for the purchased solution. As a consequence, we also demonstrate integrality gap upper bounds on the standard cut-based linear programming relaxation for the Directed Steiner Tree instances we consider.

We present an O(log k)-approximation for both the edge-weighted and node-weighted versions of Directed Steiner Tree in planar graphs where k is the number of terminals. We extend our approach to Multi-Rooted Directed Steiner Tree, in which we get a O(R+log k)-approximation for planar graphs for where R is the number of roots.

k-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approximate within a factor of 1.93, even in the plane, if one insists the dependence on k in the running time be polynomial. Without this restriction, a classic algorithm yields a 2^{O((klog k)/{epsilon})}dn-time (1+epsilon)-approximation for Euclidean k-center, where d is the dimension. In this work, we give a faster algorithm for small dimensions: roughly speaking an O^*(2^{O((1/epsilon)^{O(d)} k^{1-1/d} log k)})-time (1+epsilon)-approximation. In particular, the running time is roughly O^*(2^{O((1/epsilon)^{O(1)}sqrt{k}log k)}) in the plane. We complement our algorithmic result with a matching hardness lower bound. We also consider a well-studied generalization of k-center, called Non-uniform k-center (NUkC), where we allow different radii clusters. NUkC is NP-hard to approximate within any factor, even in the Euclidean case. We design a 2^{O(klog k)}n^2 time 3-approximation for NUkC, and a 2^{O((klog k)/epsilon)}dn time (1+\epsilon)-approximation for Euclidean NUkC. The latter time bound matches the bound for k-center.

We give an improved approximation algorithm for two related clustering problems. In the Minimum Sum of Radii clustering problem (MSR), we are to select k balls in a metric space to cover all points while minimizing the sum of the radii of these balls. In the Minimum Sum of Diameters clustering problem (MSD), we are to simply partition the points of a metric space into k parts while minimizing the sum of the diameters of these parts. We present a 3.389-approximation for MSR and a 6.546-approximation for MSD, improving over their respective 3.504 and 7.008 approximations developed by Charikar and Panigrahy (2001). In particular, our guarantee for MSD is better than twice our guarantee for MSR. Our approach refines a so-called bipoint rounding procedure of Charikar and Panigrahy’s algorithm by considering centering balls at some points that were not necessarily centers in the bipoint solution. This added versatility enables the analysis of our improved approximation guarantees. We also provide an alternative approach to finding the bipoint solution using a straightforward LP rounding procedure rather than a primal-dual algorithm.

We investigate a genre of vehicle-routing problems (VRPs), that we call max-reward VRPs, wherein nodes located in a metric space have associated rewards that depend on their visiting times, and we seek a path that earns maximum reward. A prominent problem in this genre is deadline TSP, where nodes have deadlines and we seek a path that visits all nodes by their deadlines and earns maximum reward. Our main result is a constant-factor approximation for deadline TSP running in time O(n^O(log(nΔ))) in metric spaces with integer distances at most Δ. This is the first improvement over the approximation factor of O(log n) due to Bansal et al. [N. Bansal et al., 2004] in over 15 years (but is achieved in super-polynomial time). Our result provides the first concrete indication that log n is unlikely to be a real inapproximability barrier for deadline TSP, and raises the exciting possibility that deadline TSP might admit a polytime constant-factor approximation. At a high level, we obtain our result by carefully guessing an appropriate sequence of O(log (nΔ)) nodes appearing on the optimal path, and finding suitable paths between any two consecutive guessed nodes. We argue that the problem of finding a path between two consecutive guessed nodes can be relaxed to an instance of a special case of deadline TSP called point-to-point (P2P) orienteering. Any approximation algorithm for P2P orienteering can then be utilized in conjunction with either a greedy approach, or an LP-rounding approach, to find a good set of paths overall between every pair of guessed nodes. While concatenating these paths does not immediately yield a feasible solution, we argue that it can be covered by a constant number of feasible solutions. Overall our result therefore provides a novel reduction showing that any α-approximation for P2P orienteering can be leveraged to obtain an O(α)-approximation for deadline TSP in O(n^O(log nΔ)) time. Our results extend to yield the same guarantees (in approximation ratio and running time) for a substantial generalization of deadline TSP, where the reward obtained by a client is given by an arbitrary non-increasing function (specified by a value oracle) of its visiting time. Finally, we discuss applications of our results to variants of deadline TSP, including settings where both end-nodes are specified, nodes have release dates, and orienteering with time windows.

We investigate the complexity of solving stable or perturbation-resilient instances of k-means and k-median clustering in fixed dimension Euclidean metrics (or more generally doubling metrics). The notion of stable or perturbation resilient instances was introduced by Bilu and Linial [2010] and Awasthi, Blum, and Sheffet [2012]. In our context, we say a k-MEANS instance is α-stable if there is a unique optimum solution which remains unchanged if distances are (non-uniformly) stretched by a factor of at most α. Stable clustering instances have been studied to explain why heuristics such as Lloyd's algorithm perform well in practice. In this work we show that for any fixed ∊ > 0, (1 + ∊)-stable instances of k-MEANS in doubling metrics, which include fixed-dimensional Euclidean metrics, can be solved in polynomial time. More precisely, we show a natural multi-swap local-search algorithm in fact finds the optimum solution for (1 + ∊)-stable instances of k-MEANS and k-median in a polynomial number of iterations. We complement this result by showing that under a plausible PCP hypothesis this is essentially tight: that when the dimension d is part of the input, there is a fixed ∊0 > 0 such there is not even a PTAS for (1 + ∊0)-stable k-MEANS in ℝd unless NP=RP. To do this, we consider a robust property of CSPs; call an instance stable if there is a unique optimum solution x* and for any other solution x’, the number of unsatisfied clauses is proportional to the Hamming distance between x* and x’. Dinur, Goldreich, and Gur have already shown stable QSAT is hard to approximation for some constant Q [16], our hypothesis is simply that stable QSAT with bounded variable occurrence is also hard (there is in fact work in progress to prove this hypothesis). Given this hypothesis, we consider “stability-preserving” reductions to prove our hardness for stable k-MEANS. Such reductions seem to be more fragile and intricate than standard L-reductions and may be of further use to demonstrate other stable optimization problems are hard to solve.

Clustering problems are well studied in a variety of fields, such as data science, operations research, and computer science. Such problems include variants of center location problems, k -median and k -means to name a few. In some cases, not all data points need to be clustered; some may be discarded for various reasons. For instance, some points may arise from noise in a dataset or one might be willing to discard a certain fraction of the points to avoid incurring unnecessary overhead in the cost of a clustering solution. We study clustering problems with outliers. More specifically, we look at uncapacitated facility location (UFL), k - median , and k - means . In these problems, we are given a set X of data points in a metric space δ(., .), a set C of possible centers (each maybe with an opening cost), maybe an integer parameter k , plus an additional parameter z as the number of outliers. In uncapacitated facility location with outliers, we have to open some centers, discard up to z points of X , and assign every other point to the nearest open center, minimizing the total assignment cost plus center opening costs. In k - median and k - means , we have to open up to k centers, but there are no opening costs. In k - means , the cost of assigning j to i is δ 2 ( j , i ). We present several results. Our main focus is on cases where δ is a doubling metric (this includes fixed dimensional Euclidean metrics as a special case) or is the shortest path metrics of graphs from a minor-closed family of graphs. For uniform-cost UFL with outliers on such metrics, we show that a multiswap simple local search heuristic yields a PTAS. With a bit more work, we extend this to bicriteria approximations for the k - median and k - means problems in the same metrics where, for any constant ϵ > 0, we can find a solution using (1 + ϵ) k centers whose cost is at most a (1 + ϵ)-factor of the optimum and uses at most z outliers. Our algorithms are all based on natural multiswap local search heuristics. We also show that natural local search heuristics that do not violate the number of clusters and outliers for k - median (or k - means ) will have unbounded gap even in Euclidean metrics. Furthermore, we show how our analysis can be extended to general metrics for k - means with outliers to obtain a (25 + ϵ, 1 + ϵ)-approximation: an algorithm that uses at most (1 + ϵ) k clusters and whose cost is at most 25 + ϵ of optimum and uses no more than z outliers.

This paper presents a solution to the problem posed in the ACM SIGSPATIAL GIS Cup 2018, namely to identify all upstream features---nodes and edges existing on simple paths between starting points and controllers---in a given spatial network. Our approach is based primarily on a two-sweep depth-first search which decomposes a graph into its biconnected components prior to collecting the upstream features. Our algorithm runs in linear time in the size of the graph and, in practice, is able to solve large instances with millions of features within seconds on an ordinary personal laptop, identifying features if and only if they are upstream.

Clustering problems are well-studied in a variety of fields such as data science, operations research, and computer science. Such problems include variants of centre location problems, k-median, and k-means to name a few. In some cases, not all data points need to be clustered; some may be discarded for various reasons. For instance, some points may arise from noise in a data set or one might be willing to discard a certain fraction of the points to avoid incurring unnecessary overhead in the cost of a clustering solution. We study clustering problems with outliers. More specifically, we look at UNCAPACITATED FACILITY LOCATION (UFL), k-MEDIAN, and k-MEANS. In these problems, we are given a set χ of data points in a metric space δ(.,.), a set C of possible centres (each maybe with an opening cost), maybe an integer parameter k, plus an additional parameter z as the number of outliers. In UNCAPACITATED FACILITY LOCATION with outliers, we have to open some centres, discard up to z points of χ and assign every other point to the nearest open centre, minimizing the total assignment cost plus centre opening costs. In k-MEDIAN and k-MEANS, we have to open up to k centres but there are no opening costs. In k-MEANS, the cost of assigning j to i is δ2(j, i). We present several results. Our main focus is on cases where δ is a doubling metric (this includes fixed dimensional Euclidean metrics as a special case) or is the shortest path metrics of graphs from a minor-closed family of graphs. For UNIFORM-COST UFL with outliers on such metrics we show that a multiswap simple local search heuristic yields a PTAS. With a bit more work, we extend this to bicriteria approximations for the k-MEDIAN and k-MEANS problems in the same metrics where, for any constant ε > 0, we can find a solution using (1 + ε)k centres whose cost is at most a (1 + ε)-factor of the optimum and uses at most z outliers. Our algorithms are all based on natural multiswap local search heuristics. We also show that natural local search heuristics that do not violate the number of clusters and outliers for k-MEDIAN (or k-MEANS) will have unbounded gap even in Euclidean metrics. Furthermore, we show how our analysis can be extended to general metrics for k-MEANS with outliers to obtain a (25 + ε, 1 + ε)-approximation: an algorithm that uses at most (1 + ε)k clusters and whose cost is at most 25 + ε of optimum and uses no more than z outliers.

We study the problem of automatically and efficiently generating itineraries for users who are on vacation. We focus on the common case, wherein the trip duration is more than a single day. Previous efficient algorithms based on greedy heuristics suffer from two problems. First, the itineraries are often unbalanced, with excellent days visiting top attractions followed by days of exclusively lower-quality alternatives. Second, the trips often re-visit neighborhoods repeatedly in order to cover increasingly low-tier points of interest. Our primary technical contribution is an algorithm that addresses both these problems by maximizing the quality of the worst day. We give theoretical results showing that this algorithm»s competitive factor is within a factor two of the guarantee of the best available algorithm for a single day, across many variations of the problem. We also give detailed empirical evaluations using two distinct datasets:(a) anonymized Google historical visit data and(b) Foursquare public check-in data. We show first that the overall utility of our itineraries is almost identical to that of algorithms specifically designed to maximize total utility, while the utility of the worst day of our itineraries is roughly twice that obtained from other approaches. We then turn to evaluation based on human raters who score our itineraries only slightly below the itineraries created by human travel experts with deep knowledge of the area.

We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimum-load k-facility location (ML k FL) problem, which is defined as follows. We have a set F of facilities, a set C of clients, and an integer k ≥ 0. Assigning client j to a facility f incurs a connection cost d ( f , j ). The goal is to open a set F ⊆ F of k facilities and assign each client j to a facility f ( j )∈ F so as to minimize max f ∈ F ∑ j ∈ C : f ( j )= f d ( f , j ); we call ∑ j ∈ C : f ( j )= f d ( f , j ) the load of facility f . This problem was studied under the name of min-max star cover in References [3, 7], who (among other results) gave bicriteria approximation algorithms for ML k FL for when F = C . ML k FL is rather poorly understood, and only an O ( k )-approximation is currently known for ML k FL, even for line metrics . Our main result is the first polytime approximation scheme (PTAS) for ML k FL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that ML k FL is strongly NP -hard on line metrics. We also devise a quasi-PTAS for ML k FL on tree metrics. ML k FL turns out to be surprisingly challenging even on line metrics and resilient to attack by a variety of techniques that have been successfully applied to facility-location problems. For instance, we show that (a) even a configuration-style LP-relaxation has a bad integrality gap and (b) a multi-swap k -median style local-search heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack ML k FL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near-optimal solution possessing some nice structural properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP) encoding of the problem and argue that a MILP-solution minimizing a certain potential function possesses the desired structure and then use a rounding algorithm for the generalized-assignment problem to “transfer” this structure to the rounded integer solution. Complementing this, we show that these structural properties enable one to find such a structured solution via dynamic programming.

We consider scheduling problems in which jobs need to be processed through a (shared) network of machines. The network is given in the form of a graph the edges of which represent the machines. We are also given a set of jobs, each specified by its processing time and a path in the graph. Every job needs to be processed in the order of edges specified by its path. We assume that jobs can wait between machines and preemption is not allowed; that is, once a job is started being processed on a machine, it must be completed without interruption. Every machine can only process one job at a time. The makespan of a schedule is the earliest time by which all the jobs have finished processing. The flow time (a.k.a. the completion time) of a job in a schedule is the difference in time between when it finishes processing on its last machine and when the it begins processing on its first machine. The total flow time (or the sum of completion times) is the sum of flow times (or completion times) of all jobs. Our focus is on finding schedules with the minimum sum of completion times or minimum makespan. In this paper, we develop several algorithms (both approximate and exact) for the problem both on general graphs and when the underlying graph of machines is a tree. Even in the very special case when the underlying network is a simple star, the problem is very interesting as it models a biprocessor scheduling with applications to data migration.

We pursue a study of the Generalized Demand Matching problem, a common generalization of the b-Matching and Knapsack problems. Here, we are given a graph with vertex capacities, edge profits, and asymmetric demands on the edges. The goal is to find a maximum-profit subset of edges so the demands of chosen edges do not violate the vertex capacities. This problem is APX-hard and constant-factor approximations are already known. Our main results fall into two categories. First, using iterated relaxation and various filtering strategies, we show with an efficient rounding algorithm that if an additional matroid structure M is given and we further only allow sets that are independent in M, the natural LP relaxation has an integrality gap of at most 25/3. This can be further improved in various special cases, for example we improve over the 15-approximation for the previously- studied Coupled Placement problem [Korupolu et al. 2014] by giving a 7-approximation. Using similar techniques, we show the problem of computing a minimum-cost base in M satisfying vertex capacities admits a (1,3)-bicriteria approximation: the cost is at most the optimum and the capacities are violated by a factor of at most 3. This improves over the previous (1,4)-approximation in the special case that M is the graphic matroid over the given graph [Fukanaga and Nagamochi, 2009]. Second, we show Demand Matching admits a polynomial-time approximation scheme in graphs that exclude a fixed minor. If all demands are polynomially-bounded integers, this is somewhat easy using dynamic programming in bounded-treewidth graphs. Our main technical contribution is a sparsification lemma that allows us to scale the demands of some items to be used in a more intricate dynamic programming algorithm, followed by some randomized rounding to filter our scaled-demand solution to one whose original demands satisfy all constraints.

The most well-known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly $k$-means: given a set of data points and a parameter $k$, select $k$ centers and partition the data points into $k$ clusters around these centers so that the sum of squares of distances of the points to their cluster center is minimized. Typically these data points lie in Euclidean space $\mathbb{R}^d$ for some $d\geq 2$. $k$-means and the first algorithms for it were introduced in the 1950s. Over the last six decades, hundreds of papers have studied this problem and different algorithms have been proposed for it. The most commonly used algorithm in practice is known as Lloyd--Forgy, which is also referred to as “the” $k$-means algorithm, and various extensions of it often work very well in practice. However, they may produce solutions whose cost is arbitrarily large compared to the optimum solution. Kanungo et al. [ Comput. Geom., 28 (2004), pp. 89--112] analyzed a very simple local search heuristic to get a polynomial-time algorithm with approximation ratio $9+\epsilon$ for any fixed $\epsilon>0$ for $k$-means in Euclidean space. Finding an algorithm with a better worst-case approximation guarantee has remained one of the biggest open questions in this area, in particular, whether one can get a true polynomial-time approximation scheme (PTAS) for fixed dimension Euclidean space. We settle this problem by showing that a simple local search algorithm provides a PTAS for $k$-means for $\mathbb{R}^d$ for any fixed $d$. More precisely, for any error parameter $\epsilon>0$, the local search algorithm that considers swaps of up to $\rho=d^{O(d)}\cdot{\epsilon}^{-O(d/\epsilon)}$ centers at a time will produce a solution using exactly $k$ centers whose cost is at most a $(1+\epsilon)$-factor greater than the optimum solution. Although the algorithm is not practical due to the large polynomial running time, it settles the approximability of this important problem. Our analysis extends very easily to the more general settings where we want to minimize the sum of $q$th powers of the distances between data points and their cluster centers (instead of sum of squares of distances as in $k$-means) for any fixed $q\geq 1$ and where the metric may not be Euclidean but still has fixed doubling dimension. Finally, our techniques also extend to other classic clustering problems. We provide the first demonstration that local search yields a PTAS for uncapacitated facility location and the generalization of $k$-median to the setting with nonuniform opening costs in doubling metrics.

Budgeted Red-Blue Median is a generalization of classic k-Median in that there are two sets of facilities, say R and B, that can be used to serve clients located in some metric space. The goal is to open kr facilities in R and kb facilities in B for some given bounds kr, kb and connect each client to their nearest open facility in a way that minimizes the total connection cost. We extend work by Hajiaghayi, Khandekar, and Kortsarz [2012] and show that a multipleswap local search heuristic can be used to obtain a (5 + epsilon)-approximation for Budgeted RedBlue Median for any constant epsilon > 0. This is an improvement over their single swap analysis and beats the previous best approximation guarantee of 8 by Swamy [2014]. We also present a matching lower bound showing that for every p >= 1, there are instances of Budgeted Red-Blue Median with local optimum solutions for the p-swap heuristic whose cost is 5 + Omega(1/p) times the optimum solution cost. Thus, our analysis is tight up to the lower order terms. In particular, for any epsilon > 0 we show the single-swap heuristic admits local optima whose cost can be as bad as 7 - epsilon times the optimum solution cost.

We study some linear programming relaxations for the Unsplittable Flow problem on trees (UFP-Tree). Inspired by results obtained by Chekuri, Ene, and Korula for Unsplittable Flow on paths (UFP-Path), we present a relaxation with polynomially many constraints that has an integrality gap bound of O(log n * min(log m, log n)) where n denotes the number of tasks and m denotes the number of edges in the tree. This matches the approximation guarantee of their combinatorial algorithm and is the first demonstration of an efficiently-solvable relaxation for UFP-Tree with a sub-linear integrality gap. The new constraints in our LP relaxation are just a few of the (exponentially many) rank constraints that can be added to strengthen the natural relaxation. A side effect of how we prove our upper bound is an efficient O(1)-approximation for solving the rank LP. We also show that our techniques can be used to prove integrality gap bounds for similar LP relaxations for packing demand-weighted subtrees of an edge-capacitated tree. On the other hand, we show that the inclusion of all rank constraints does not reduce the integrality gap for UFP-Tree to a constant. Specifically, we show the integrality gap is Omega(sqrt(log n)) even in cases where all tasks share a common endpoint. In contrast, intersecting instances of UFP-Path are known to have an integrality gap of O(1) even if just a few of the rank 1 constraints are included. We also observe that applying two rounds of the Lovász-Schrijver SDP procedure to the natural LP for UFP-Tree derives an SDP whose integrality gap is also O(log n * min(log m, log n)).

We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimum-load k-facility location (MLkFL) problem, which is defined as follows. We have a set F of facilities, a set C of clients, and an integer k > 0. Assigning client j to a facility f incurs a connection cost d(f, j). The goal is to open a set F' of k facilities, and assign each client j to a facility f(j) in F' so as to minimize maximum, over all facilities in F', of the sum of distances of clients j assigned to F' to F'. We call this sum the load of facility f. This problem was studied under the name of min-max star cover in [6, 2], who (among other results) gave bicriteria approximation algorithms for MLkFL for when F = C. MLkFL is rather poorly understood, and only an O(k)-approximation is currently known for MLkFL, even for line metrics. Our main result is the first polynomial time approximation scheme (PTAS) for MLkFL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that MLkFL is strongly NP-hard on line metrics. We also devise a quasi-PTAS for MLkFL on tree metrics. MLkFL turns out to be surprisingly challenging even on line metrics, and resilient to attack by the variety of techniques that have been successfully applied to facility-location problems. For instance, we show that: (a) even a configuration-style LP-relaxation has a bad integrality gap; and (b) a multi-swap k-median style local-search heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack MLkFL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near-optimal solution possessing some nice structural properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP) encoding the problem, and argue that a MILP-solution minimizing a certain potential function possesses the desired structure, and then use a rounding algorithm for the generalized-assignment problem to "transfer" this structure to the rounded integer solution. Complementing this, we show that these structural properties enable one to find such a structured solution via dynamic programming.

We consider vehicle-routing problems (VRPs) that incorporate the notion of regret of a client, which is a measure of the waiting time of a client relative to its shortest-path distance from the depot. Formally, we consider both the additive and multiplicative versions of, what we call, the regret-bounded vehicle routing problem (RVRP). In these problems, we are given an undirected complete graph G = ({r} ∪ V,E) on n nodes with a distinguished root (depot) node r, edge costs {cuv} that form a metric, and a regret bound R. Given a path P rooted at r and a node v ∈ P, let cP(v) be the distance from r to v along P. The goal is to find the fewest number of paths rooted at r that cover all the nodes so that for every node v covered by (say) path P: (i) its additive regret cP(v) -- crv, with respect to P is at most R in additive-RVRP; or (ii) its multiplicative regret, cP(v)/crv, with respect to P is at most R in multiplicative-RVRP.

We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time s i , an end time t i , a demand d i > 0, and a profit p i > 0. A task, if accepted, requires d i units of “bandwidth” from time s i to t i and accrues a profit of p i . For every time t , we are also specified the available bandwidth c t , and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints. We present the first polynomial time O (log n ) approximation algorithm for this problem. This significantly advances the state of the art, as no polynomial time o ( n ) approximation was known previously. Previous results for this problem were known only in more restrictive settings; in particular, either the instance satisfies the so-called “no-bottleneck” assumption: max i d i ≤ min t c t , or the ratio of both maximum to minimum demands and maximum to minimum capacities are polynomially (or quasi-polynomially) bounded in n . Our result, on the other hand, does not require these assumptions. Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an Ω( n ) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.

We consider the mobile facility location (MFL) problem. We are given a set of facilities and clients located in a common metric space G = (V, c). The goal is to move each facility from its initial location to a destination (in V) and assign each client to the destination of some facility so as to minimize the sum of the movement-costs of the facilities and the client-assignment costs. This abstracts facility-location settings where one has the flexibility of moving facilities from their current locations to other destinations so as to serve clients more efficiently by reducing their assignment costs. We give the first local-search based approximation algorithm for this problem and achieve the best-known approximation guarantee. Our main result is (3 + ε)-approximation for this problem for any constant ε > 0 using local search. The previous best guarantee for MFL was an 8-approximation algorithm due to Friggstad and Salavatipour [12] based on LP-rounding. Our guarantee matches the best-known approximation guarantee for the k-median problem. Since there is an approximation-preserving reduction from the k-median problem to MFL, any improvement of our result would imply an analogous improvement for the k-median problem. Furthermore, our analysis is tight (up to o(1) factors) since the tight example for the local-search based 3-approximation algorithm for k-median can be easily adapted to show that our local-search algorithm has a tight approximation ratio of 3. Our results extend to the weighted generalization wherein each facility i has a non-negative weight wi and the movement cost for i is wi times the distance traveled by i. In contrast to the k-median problem, the local search procedure that moves, at each step, a constant number of facilities (to chosen destinations) and assigns each client to the nearest destination, is known to have an unbounded locality gap. Our local-search algorithm is a natural and simple variant, where we only select the destinations of the facilities in each step and optimally rematch the facilities to these destinations (which might entail moving all facilities). One of the chief novelties in the analysis is that in order to generate a suitable collection of local-search moves whose resulting inequalities yield the desired bound on the cost of a local-optimum, we define a tree-like structure that (loosely speaking) functions as a “recursion tree”, using which we spawn off local-search moves by exploring this tree to a constant depth.

We study integrality gaps and approximability of three closely related problems on directed graphs with edge lengths that satisfy the triangle inequality. Given two specified vertices $s$ and $t$, two of these problems ask to find an $s$-$t$ path in the graph visiting all other vertices. In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total length of this path. In the directed latency problem, the objective is to minimize the sum of the latencies of the vertices, where the latency of a vertex $v$ is the distance from $s$ to $v$ along the path. The third problem that we study is the $k$-person ATSPP, in which the goal is to find $k$ paths from $s$ to $t$, of minimum total length, such that every vertex is on at least one of these paths. All of these problems are NP-hard. The best known approximation algorithms for ATSPP had ratio $O(\log n)$ [C. Chekuri and M. Pal, Theory Comput., 3 (2007), pp. 197--209], [U. Feige and M. Singh, “Improved approximation ratios for traveling salesperson tours and paths in directed graphs,” in Proceedings of the 10th APPROX, 2007, pp. 107--118] until the recent result that improves it to $O(\log n/\log \log n)$ [A. Asadpour et al., “An $O(\log n/\log \log n)$-approximation algorithm for the asymmetric traveling salesman problem,” in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 379--389], [U. Feige and M. Singh, “Improved approximation ratios for traveling salesperson tours and paths in directed graphs,” in Proceedings of the 10th APPROX, 2007, pp. 107--118]. However, the best known bound on the integrality gap of any linear programming relaxation for ATSPP is only $O(\sqrt{n})$. For directed latency, the best previously known approximation algorithm has a guarantee of $O(n^{1/2+\epsilon})$ for any constant $\epsilon>0$ [V. Nagarajan and R. Ravi, “The directed minimum latency problem,” in Proceedings of the 11th APPROX, 2008, pp. 193--206]. We present a new algorithm for the ATSPP problem that has an approximation ratio of $O(\log n)$, but whose analysis also upper bounds the integrality gap of the standard LP relaxation of ATSPP by the same factor. This solves an open problem posed in [C. Chekuri and M. Pal, Theory Comput., 3 (2007), pp. 197--209]. We then pursue a deeper study of this linear program and its variations, which leads to an $O(\log n)$-approximation for the directed latency problem, a significant improvement over previously known results. Our result for $k$-person ATSPP is an $O(k^2 \log n)$-approximation that bounds the integrality gap of a linear programming relaxation by the same factor. We are not aware of any previous work on this problem.

In the mobile facility location problem, which is a variant of the classical facility location, each facility and client is assigned to a start location in a metric graph and our goal is to find a destination node for each client and facility such that every client is sent to a node which is the destination of some facility. The quality of a solution can be measured either by the total distance clients and facilities travel or by the maximum distance traveled by any client or facility. As we show in this article (by an approximation-preserving reduction), the problem of minimizing the total movement of facilities and clients generalizes the classical k -median problem. The class of movement problems was introduced by Demaine et al. [2007] where a simple 2-approximation was proposed for the minimum maximum movement mobile facility location problem while an approximation for the minimum total movement variant and hardness results for both were left as open problems. Our main result here is an 8-approximation algorithm for the minimum total movement mobile facility location problem. Our algorithm is obtained by rounding an LP relaxation in five phases. For the minimum maximum movement mobile facility location problem, we show that we cannot have a better than a 2-approximation for the problem, unless P = NP so the simple algorithm proposed by Demaine et al. [2007] is essentially best possible.

We study integrality gaps and approximability of two closely related problems on directed graphs. Given a set V of n nodes in an underlying asymmetric metric and two specified nodes s and t, both problems ask to find an s-t path visiting all other nodes. In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total cost of this path. In the directed latency problem, the objective is to minimize the sum of distances on this path from s to each node. Both of these problems are NP-hard. The best known approximation algorithms for ATSPP had ratio O(log n) [7, 9] until the very recent result that improves it to O(log n/ log log n) [3,9]. However, only abound of for the integrality gap of its linear programming relaxation has been known. For directed latency, the best previously known approximation algorithm has a guarantee of O(n1/2+ε), for any constant ε > 0 [23]. We present a new algorithm for the ATSPP problem that has approximation ratio of O(log n), but whose analysis also bounds the integrality gap of the standard LP relaxation of ATSPP by the same factor. This solves an open problem posed in [7]. We then pursue a deeper study of this LP and its variations and their use in approximating directed latency. Our second major result is an O(log n)-approximation to the directed latency problem. This also places an O(log n) bound on the integrality gap of a new LP relaxation of the latency problem that we introduce.

We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time si, an end time ti, a demand di > 0, and a profit pi > 0. A task, if accepted, requires di units of “bandwidth” from time si to ti and accrues a profit of pi. For every time t, we are also specified the available bandwidth ct, and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints. In this paper, we present the first polynomial-time O(log n)-approximation algorithm for this problem. No polynomial-time o(n)-approximation was known prior to this work. Previous results for this problem were known only in more restrictive settings, in particular, either if the given instance satisfies the so-called “no-bottleneck” assumption: maxi di ≤ mint ct, or else if the ratio of the maximum to the minimum demands and ratio of the maximum to the minimum capacities are polynomially (or quasi-polynomially) bounded in n. Our result, on the other hand, does not require any of these assumptions. Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an Ω(n) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.

In the mobile facility location problem, which is a variant of the classical uncapacitated facility location and k-median problems, each facility and client is assigned to a start location in a metric graph and our goal is to find a destination node for each client and facility such that every client is sent to a node which is the destination of some facility. The quality of a solution can be measured either by the total distance clients and facilities travel or by the maximum distance traveled by any client or facility. As we show in this paper (by an approximation preserving reduction), the problem of minimizing the total movement of facilities and clients generalizes the classical k-median problem. The class of movement problems was introduced by Demaine et al. in SODA 2007, where it was observed a simple 2-approximation for the minimum maximum movement mobile facility location while an approximation for the minimum total movement variant and hardness results for both were left as open problems. Our main result here is an 8-approximation algorithm for the minimum total movement mobile facility location problem. Our algorithm is obtained by rounding an LP relaxation in five phases. We also show that this problem generalizes the classical k-median problem using an approximation preserving reduction. For the minimum maximum movement mobile facility location problem, we show that we cannot have a better than a 2-approximation for the problem, unless P = NP; so the simple algorithm observed in is essentially best possible.