The Traveling Salesman Problem (TSP) is a canonical NP-complete problem which is known to be MAX-SNP hard even on (high-dimensional) Euclidean metrics [39]. In order to circumvent this hardness, researchers have been developing approximation schemes for low-dimensional metrics [4, 38] (under different notions of dimension). However, a feature of most current notions of metric dimension is that they are local: the definitions require every neighborhood to be well-behaved. In this paper, we consider the case when the metric is less restricted: it has a few dense regions, but is well-behaved on the average? To this end, we define a global notion of dimension which we call the correlation dimension (denoted by dimC), which generalizes the popular notion of doubling dimension. In fact, the class of metrics with dimC = O(1) not only contains all doubling metrics, but also contains some metrics containing uniform submetrics of size √n. We first show, using a somewhat local argument, that one can solve TSP on these metrics in time 2O(√n); we then take advantage of the global nature of TSP (and the global nature of our definition) to give a (1 + e)-approximation algorithm that runs in sub-exponential time: i.e., in 2O(nΔe-4dimC)-time for every constant 0
This paper presents parallel algorithms for embedding an arbitrary n-point metric space into a distribution of dominating trees with O(log n) expected stretch. Such embedding has proved useful in the design of many approximation algorithms in the sequential setting. We give a parallel algorithm that runs in O(n2 log n) work and O(log2 n) depth---these bounds are independent of Δ = (maxx,y d(x,y))/(minx≠ y d(x,y)), the ratio of the largest to smallest distance. Moreover, when Δ is exponentially bounded (Δ ≤ 2O(n)), our algorithm can be improved to O(n2) work and O(log2 n) depth. Using these results, we give an RNC O(log k)-approximation algorithm for k-median and an RNC O(log n)-approximation for buy-at-bulk network design. The k-median algorithm is the first RNC algorithm with non-trivial guarantees for arbitrary values of k, and the buy-at-bulk result is the first parallel algorithm for the problem.
In this article, we study metrics of negative type , which are metrics ( V , d) such that √d is an Euclidean metric; these metrics are thus also known as ℓ 2 -squared metrics. We show how to embed n -point negative-type metrics into Euclidean space ℓ 2 with distortion D = O (log 3/4 n ). This embedding result, in turn, implies an O (log 3/4 k )-approximation algorithm for the Sparsest Cut problem with nonuniform demands. Another corollary we obtain is that n -point subsets of ℓ 1 embed into ℓ 2 with distortion O (log 3/4 n ).
We consider the problem of makespan minimization on unrelated machines when job sizes are stochastic. The goal is to find a fixed assignment of jobs to machines, to minimize the expected value of the maximum load over all the machines. For the identical-machines special case when the size of a job is the same across all machines, a constant-factor approximation algorithm has long been known. Our main result is the first constant-factor approximation algorithm for the general case of unrelated machines. This is achieved by (i) formulating a lower bound using an exponential-size linear program that is efficiently computable and (ii) rounding this linear program while satisfying only a specific subset of the constraints that still suffice to bound the expected makespan. We also consider two generalizations. The first is the budgeted makespan minimization problem, where the goal is to minimize the expected makespan subject to scheduling a target number (or reward) of jobs. We extend our main result to obtain a constant-factor approximation algorithm for this problem. The second problem involves q-norm objectives, where we want to minimize the expected q-norm of the machine loads. Here we give an [Formula: see text]-approximation algorithm, which is a constant-factor approximation for any fixed q.
Consider an edge-weighted tree T = (V, E, w : E r R+), in which a subset R of the nodes (called the required nodes) are colored red and the remaining nodes in S = V\R are colored black (and called the Steiner nodes). The shortest-path distance according to the edge-weights defines a metric dT on the vertex set V.We now ask the following question: Is it possible to define another weighted tree T* = (R, E*, w* : E* r R+), this time on just the red vertices so that the shortest-path metric dT* induced by T* on the vertices in R is “close” to the metric dT restricted to the red vertices? I.e., does there exist a weighted tree T* = (R, E*, c*) and a (small) constant a such that dT(u, v) ≤ dT* (u, v) ≤ a dT(u, v) for any two red vertices u, v ∈ R?We answer this question in the affirmative, and give a linear time algorithm to obtain a tree T* with a ≤ 8. We also give two applications of this result: an upper bound, in which we show that emulating multicasts using unicasts can be almost as good as general multicasts for certain performance measures; and a lower bound, in which we give a simple combinatorial proof of the fact that the metric generated by a graph of girthg must suffer a distortion of at least O(g) when approximated by a tree.
We consider the online carpooling problem: given n vertices, a sequence of edges arrive over time. When an edge e_t = (u_t, v_t) arrives at time step t, the algorithm must orient the edge either as v_t → u_t or u_t → v_t, with the objective of minimizing the maximum discrepancy of any vertex, i.e., the absolute difference between its in-degree and out-degree. Edges correspond to pairs of persons wanting to ride together, and orienting denotes designating the driver. The discrepancy objective then corresponds to every person driving close to their fair share of rides they participate in.
In this paper, we design efficient algorithms which can maintain polylog(n,T) maximum discrepancy (w.h.p) over any sequence of T arrivals, when the arriving edges are sampled independently and uniformly from any given graph G. This provides the first polylogarithmic bounds for the online (stochastic) carpooling problem. Prior to this work, the best known bounds were O(√{n log n})-discrepancy for any adversarial sequence of arrivals, or O(log log n)-discrepancy bounds for the stochastic arrivals when G is the complete graph.
The technical crux of our paper is in showing that the simple greedy algorithm, which has provably good discrepancy bounds when the arriving edges are drawn uniformly at random from the complete graph, also has polylog discrepancy when G is an expander graph. We then combine this with known expander-decomposition results to design our overall algorithm.
Over the past decade, numerous algorithms have been developed using the fact that the distances in any n-point metric (V, d) can be approximated to within O(log n) by distributions D over trees on the point set V [3, 10]. However, when the metric (V, d) is the shortest-path metric of an edge weighted graph G = (V, E), a natural requirement is to obtain such a result where the support of the distribution D is only over subtrees of G. For a long time, the best result satisfying this stronger requirement was a exp {√log n log log n} distortion result of Alon et al. [1]. In a recent breakthrough, Elkin et al. [9] improved the distortion to O(log2n log log n). (The best lower bound on the distortion is Ω(log n), say, for the n-vertex grid [1].)In this paper, we give a construction that improves the distortion to O(log2n), improving slightly on the EEST construction. The main contribution of this paper is in the analysis: we use an algorithm which is similar to one used by EEST to give a distortion of O(log3n), but using a new probabilistic analysis, we eliminate one of the logarithmic factors. The ideas and techniques we use to obtain this logarithmic improvement seem orthogonal to those used earlier in such situations---e.g., Seymour's decomposition scheme [4, 9] or the cutting procedures of CKR/FRT [5, 10], both which do not seem to give a guarantee of better than O(log2n log log n) for this problem. We hope that our ideas (perhaps in conjunction with some of these others) will ultimately lead to an O(log n) distortion embedding of graph metrics into distributions over their spanning trees.
In the stochastic orienteering problem, we are given a finite metric space, where each node contains a job with some deterministic reward and a random processing time. The processing time distributions are known and independent across nodes. However the actual processing time of a job is not known until it is completely processed. The objective is to compute a nonanticipatory policy to visit nodes (and run the corresponding jobs) so as to maximize the total expected reward, subject to the total distance traveled plus the total processing time being at most a given budget of B. This problem combines aspects of the stochastic knapsack problem with uncertain item sizes as well as the deterministic orienteering problem. In this paper, we consider both nonadaptive and adaptive policies for Stochastic Orienteering. We present a constant-factor approximation algorithm for the nonadaptive version and an O(log log B)-approximation algorithm for the adaptive version. We extend both these results to directed metrics and a more general sequence orienteering problem. Finally, we address the stochastic orienteering problem when the node rewards are also random and possibly correlated with the processing time and obtain an O(log n log B)-approximation algorithm; here n is the number of nodes in the metric. All our results for adaptive policies also bound the corresponding “adaptivity gaps”.
'%3e%3cpath fill='%23012169' d='M0 0v30h60V0z'/%3e%3cpath stroke='%23fff' stroke-width='6' d='m0 0 60 30m0-30L0 30'/%3e%3cpath stroke='%23C8102E' stroke-width='4' d='m0 0 60 30m0-30L0 30' clip-path='url(%23b)'/%3e%3cpath stroke='%23fff' stroke-width='10' d='M30 0v30M0 15h60'/%3e%3cpath stroke='%23C8102E' stroke-width='6' d='M30 0v30M0 15h60'/%3e%3c/g%3e%3c/svg%3e)