×

Facility location with client latencies: LP-based techniques for minimum-latency problems. (English) Zbl 1371.90074

Summary: We introduce a problem that is a common generalization of the uncapacitated facility location (UFL) and minimum latency (ML) problems, where facilities not only need to be opened to serve clients, but also need to be sequentially activated before they can provide service. This abstracts a setting where inventory demanded by customers needs to be stocked or replenished at facilities from a depot or warehouse.
Formally, we are given a set \(\mathcal{F}\) of \(n\) facilities with facility-opening costs, a set \(\mathcal{D}\) of \(m\) clients, and connection costs \(c(i,j)\) specifying the cost of assigning a client \(j\) to a facility \(i\), a root node \(r\) denoting the depot, and a time metric \(d()\) on \(\mathcal{F}\cup\{r\}\). Our goal is to open a subset of facilities, find a path \(P\) starting at \(r\) and spanning the open facilities to activate them, and connecting each client \(j\) to an open facility so as to minimize the total facility opening cost, the total client connection cost, and the total time of arrivals at each facility along \(P\). We call this the minimum latency uncapacitated facility location (MLUFL) problem.
Our main result is an \(O(\log n\max(\log n, \log m))\)-approximation for MLUFL. Via a reduction to the group Steiner tree (GST) problem, we show this result is tight in the sense that any improvement in the approximation guarantee for MLUFL, implies an improvement in the (currently known) approximation factor for GST. We obtain significantly improved constant approximation guarantees for two natural special cases of the problem: (a) Related MLUFL, where the connection costs form a metric that is a scalar multiple of the time metric; (b) Metric uniform MLUFL, where we have metric connection costs and the time-metric is uniform.
Our LP-based methods are fairly versatile and are easily adapted with minor changes to yield approximation guarantees for MLUFL (and ML) in various more general settings, such as (i) the setting where the latency-cost of a client is a function (of bounded growth) of the delay faced by the facility to which it is connected; and (ii) the \(k\)-route version, where we can dispatch \(k\) vehicles in parallel to activate the open facilities.
Our LP-based understanding of MLUFL also offers some LP-based insights into ML. We obtain two natural LP-relaxations for ML with constant integrality gap, which we believe shed new light upon the problem and offer a promising direction for obtaining improvements for ML.

MSC:

90B80 Discrete location and assignment
68W25 Approximation algorithms
90C05 Linear programming
90C35 Programming involving graphs or networks

Software:

VRP
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Archer A, Levin A, Williamson D (2008) A faster, better approximation algorithm for the minimum latency problem. SIAM J. Comput. 37(5):1472-1498. CrossRef · Zbl 1181.68326
[2] Azar Y, Gamzu I, Yin X (2009) Multiple intents re-ranking. Proc. 41st Annual ACM Sympos. Theory Comput., STOC ’09 (ACM, New York), 669-678. CrossRef · Zbl 1304.68037
[3] Bang-Jensen J, Frank A, Jackson B (1995) Preserving and increasing local edge-connectivity in mixed graphs. SIAM J. Discrete Math. 8(2):155-178. CrossRef · Zbl 0835.05039
[4] Bansal N, Gupta A, Krishnaswamy R (2010) A constant factor approximation algorithm for generalized min-sum set cover. Proc. 21st Annual Sympos. Discrete Algorithms, SODA ’10 (SIAM, Philadelphia), 1539-1545. CrossRef · Zbl 1288.68254
[5] Bienstock D, Goemans M, Simchi-Levi D, Williamson D (1993) A note on the prize collecting traveling salesman problem. Math. Program. 59(1):413-420. CrossRef · Zbl 0793.90089
[6] Blum A, Chalasani P, Coppersmith D, Pulleyblank B, Raghavan P, Sudan M (1994) The minimum latency problem. Proc. 26th Annual ACM Sympos. Theory Comput., STOC ’94 (ACM, New York), 163-171. CrossRef · Zbl 1345.90073
[7] Chakrabarty D, Swamy C (2011) Facility location with client latencies: Linear-programming based approximation algorithms for minimum latency problems. Günlük O, Woeginger GJ, eds. Proc. 15th Internat. Conf. Integer Programming Combinatorial Optim., IPCO ’11 (Springer, Berlin), 92-103. · Zbl 1339.90193
[8] Charikar M, Chekuri C, Goel A, Guha S (1998) Rounding via trees: Deterministic approximation algorithms for Group Steiner Trees and k-median. Proc. 30th Annual ACM Sympos. Theory Comput., STOC ’98 (ACM, New York), 114-123. CrossRef · Zbl 1028.68223
[9] Chaudhuri K, Godfrey PB, Rao S, Talwar K (2003) Paths, trees and minimum latency tours. Proc. 44th Annual IEEE Sympos. Foundations Comput. Sci., FOCS ’03. (IEEE Computer Society, Washington, DC, 36-45. CrossRef
[10] Chekuri C, Korula N, Pál M (2008) Improved algorithms for orienteering and related problems. Proc. 19th Annual Sympos. Discrete Algorithms, SODA ’08 (SIAM, Philadelphia), 661-670. · Zbl 1192.90162
[11] Eisenbrand F, Grandoni F, Rothvoß T, Schäfer G (2008) Approximating connected facility location problems via random facility sampling and core detouring. Proc. 19th Annual Sympos. Discrete Algorithms, SODA ’08 (SIAM, Philadelphia), 1174-1183. · Zbl 1192.90103
[12] Fakcharoenphol J, Harrelson C, Rao S (2007) The k-traveling repairman problem. ACM Trans. Alg. 3(4):Article 40. · Zbl 1176.90492
[13] Fakcharoenphol J, Rao S, Talwar K (2003) A tight bound on approximating arbitrary metrics by tree metrics. Proc. 35th Annual ACM Sympos. Theory Comput., STOC ’03 (ACM, New York), 448-455. CrossRef · Zbl 1192.68977
[14] Feige U, Lovász L, Tetali P (2004) Approximating min sum set cover. Algorithmica 40(4):219-234. CrossRef · Zbl 1082.68126
[15] Garg N, Konjevod G, Ravi R (2000) A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms 37(1):66-84. CrossRef · Zbl 0962.68136
[16] Goemans M, Bertsimas D (1993) Survivable networks, linear programming relaxations and the parsimonious property. Math. Programming 60(1):145-166. CrossRef · Zbl 0790.90072
[17] Goemans M, Kleinberg J (1996) An improved approximation ratio for the minimum latency problem. Proc. 7th Annual Sympos. Discrete Algorithms, SODA ’96 (SIAM, Philadelphia), 152-158. · Zbl 0845.90122
[18] Gupta A, Kleinberg J, Kumar A, Rastogi R, Yener B (2001) Provisioning a virtual private network: A network design problem for multicommodity flow. Proc. 33rd Ann. ACM Sympos. Theory Comput., STOC ’01 (ACM, New York), 389-398. CrossRef · Zbl 1323.68014
[19] Gupta A, Krishnaswamy R, Nagarajan V, Ravi R (2010) Approximation algorithms for optimal decision trees and adaptive TSP problems. Proc. 37th Internat. Colloquium Conf. Automata, Languages and Programming, ICALP ’10 (Springer, Berlin), 690-701. CrossRef · Zbl 1288.68267
[20] Halperin E, Krauthgamer R (2003) Polylogarithmic inapproximability. Proc. 35th Annual ACM Sympos. Theory Comput., STOC ’03 (ACM, New York), 585-594. CrossRef · Zbl 1192.68321
[21] Li S (2011) A 1.488-approximation for the uncapacitated facility location problem. Proc. 38th Internat. Colloquium Conf. Automata, Languages and Programming, ICALP ’11 (Springer, Berlin), 77-88. CrossRef · Zbl 1334.68301
[22] Lin JH, Vitter JS (1992) -approximations with minimum packing constraint violation. Proc. 24th Annual ACM Sympos. Theory Comput., STOC ’92 (ACM, New York), 771-782. CrossRef
[23] Jain K, Mahdian M, Salavatipour M (2003) Packing Steiner trees. Proc. 14th Annual Sympos. Discrete Algorithms, SODA ’03 (SIAM, Philadelphia), 266-274. · Zbl 1094.68612
[24] Mirchandani P, Francis R, eds. (1990) Discrete Location Theory (John Wiley & Sons, New York).
[25] Nagarajan V (2009) Approximation Algorithms for Sequencing Problems. Unpublished doctoral dissertation, Tepper School of Business, Carnegie Mellon University, Pittsburgh.
[26] Post I, Swamy C (2015) Linear-programming based techniques for multi-vehicle minimum latency problems. Proc. 26th SODA, 512-531. · Zbl 1371.90027
[27] Ravi R, Selman FS (1999) Approximation algorithms for the traveling purchaser problem and its variants in network design. Proc. 7th Annual Eur. Sympos. Algorithms, ESA ’99 (Springer, Berlin), 29-40. CrossRef · Zbl 0946.90007
[28] Shmoys D, Levi R, Swamy C (2004) Facility location with service installation costs. Proc. 15th Annual Sympos. Discrete Algorithms, SODA ’04 (SIAM, Philadelphia), 1081-1090. · Zbl 1318.90044
[29] Shmoys DB, Tardos É, Aardal KI (1997) Approximation algorithms for facility location problems. Proc. 29th Annual ACM Sympos. Theory Comput., STOC ’97 (ACM, New York), 265-274. CrossRef · Zbl 0962.68008
[30] Shmoys D, Williamson D (1990) Analyzing the Held-Karp TSP bound: A monotonicity property with application. Inf. Process. Lett. 35(6):281-285. CrossRef · Zbl 0698.68050
[31] Swamy C (2014) Improved approximation algorithms for matroid and knapsack median problems and applications. Jansen K, Rolim J, Devanur N, Moore C, eds. Proc. 17th Internat. Workshop Approximation Algorithms Combinatorial Optim. Problems, APPROX ’14 (Dagstuhl Publishing, Wadern, Germany), 403-418.
[32] Swamy C, Kumar A (2004) Primal-dual algorithms for connected facility location problems. Algorithmica 40(4):245-269. CrossRef · Zbl 1108.90026
[33] Toth P, Vigo D, eds. (2002) The Vehicle Routing Problem (SIAM, Philadelphia). CrossRef
[34] Wolsey L (1980) Heuristic analysis, linear programming and branch and bound. Math. Programming Stud. 13:121-134. CrossRef · Zbl 0442.90061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.