Abstract
We initiate a study of the approximability of integrated logistics problems that combine elements of facility location and the associated transport network design.
In the simplest version, we are given a graph G = (V, E) with metric edge costs c, a set of potential facilities with nonnegative facility opening costs φ, a set of clients D ⊆V (each with unit demand), and a positive integer u (cable capacity). We wish to open facilities and construct a network of cables, such that every client is served by some open facility and all cable capacities are obeyed. The objective is to minimize the sum of facility opening and cable installation costs. With only one zero-cost facility and infinite u, this is the Steiner tree problem, while with unit capacity cables this is the Uncapacitated Facility Location problem. We give a (ρst+ρufl)-approximation algorithm for this problem, where ρp denotes any approximation ratio for problem P.
For an extension when the facilities don’t have costs but no more than p facilities may be opened, we provide a bicriteria approximation algorithm that has total cost at most ρp -median + 2 times the minimum but opens up to 2p facilities.
Finally, for the general version with k different types of cables, we extend the techniques of [Guha, Meyerson, Munagala, STOC 2001] to provide an O(k) approximation.
Supported in part by a research grant from the Carnegie Bosch Institute, CMU, and by an NSF grant CCR-0105548.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, A., Klein, P., Ravi, R.: When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Computing, 24:440–456, 1995.
Andrews, M., Zhang, L.: The access network design problem. Proc. of the 39th Ann. IEEE Symp. on Foundations of Computer Science, pages 42–49, 1998.
Arya, V., Garg, N., Khandekar, R., Pandit, V., Meyerson, A., Munagala, K.: Local search heuristic for k-median and facility location problems. Proc. 33rd ACM Symposium on the Theory of Computing, pages 21–29, 2001.
Awerbuch, B., Azar, Y.: Buy at bulk network design. Proc. 38th Ann. IEEE Symposium on Foundations of Computer Science, pages 542–547, 1997.
Balinski, M.L.: On finding integer solutions to linear programs. Proc. IBM Scientific Computing Symposium on Combinatorial Problems, pages 225–248, 1966.
Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. Proc. 40th Ann. IEEE Symposium on Foundations of Computer Science, pages 378–388, 1999.
Charikar, M., Guha, S., Shmoys, D., Tardos, E.: A constant-factor approximation algorithm for the k-median problem. Proc. 31st ACM Symposium on Theory of Computing, pages 1–10, 1999.
Garg, N., Khandekar, R., Konjevod, G., Ravi, R., Salman, F.S., Sinha, A.: On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem. Proc. 8th Conference on Integer Programming and Combinatorial Optimization, pages 170–184, 2001.
Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, pages 649–657, 1998.
Guha, S., Meyerson, A., Munagala, K.: Hierarchical placement and network design problems. Proc. 41st Ann. IEEE Symposium on Foundations of Computer Science, pages 603–612, 2000.
Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation for the single sink edge installation problems. Proc. 33rd ACM Symposium on the Theory of Computing, pages 383–388, 2001.
Hassin, R., Ravi, R., F.S. Salman, F.S.: Approximation algorithms for a capacitated network design problem. Approximation Algorithms for Combinatorial Optimization, Springer-Verlag Lecture Notes in Computer Science 1913, pages 167–176, 2000.
Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. To appear in Proc. 34th ACM Symposium on the Theory of Computing, 2002.
Jain, K., Vazirani, V.V.: Primal-dual approximation algorithms for metric facility location and k-median problems. Proc. 40th Ann. IEEE Symposium on Foundations of Computer Science, pages 2–13, 1999.
Karger, D., Minkoff, M.: Building Steiner trees with incomplete global knowledge. Proc. 41st Ann. IEEE Symposium on Foundations of Computer Science, pages 613–623, 2000.
Korupulu, M., Plaxton, C., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, pages 1–10, 1998.
Mahdian, M., Ye, Y., Zhang, J.: A 1.52 approximation algorithm for the uncapacitated facility location problem. Manuscript, 2001.
Ravi, R.: A primal-dual approximation algorithm for the Steiner Forest Problem. Information Processing Letters 50(4): 185–190, 1994.
Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. Proc. 10th ACM-SIAM Symposium on Discrete Algorithms, pages 770–779, 1999.
Salman, F.S., Cheriyan, J., Ravi, R., Subramanian, S.: Buy-at-bulk network design: Approximating the single-sink edge installation problem. SIAM Journal on Optimization, 11:3, 595–610, 2000.
Shmoys, D., Tardos, E., Aardal, K.: Approximation algorithms for the facility location problem. Proc. 29th ACM Symposium on the Theory of Computing, pages 265–274, 1997.
Sviridenko, M.: A 1.582 approximation algorithm for the metric uncapacitated facility location problem. Proc. 9th Conference on Integer Programming and Combinatorial Optimization (2002), LNCS 2337, Springer Verlag, this volume.
Talwar, K.: Single sink buy-at-bulk LP has constant integrality gap. Proc. 9th Conference on Integer Programming and Combinatorial Optimization (2002), LNCS 2337, Springer Verlag, this volume.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ravi, R., Sinha, A. (2002). Integrated Logistics: Approximation Algorithms Combining Facility Location and Network Design. In: Cook, W.J., Schulz, A.S. (eds) Integer Programming and Combinatorial Optimization. IPCO 2002. Lecture Notes in Computer Science, vol 2337. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47867-1_16
Download citation
DOI: https://doi.org/10.1007/3-540-47867-1_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43676-8
Online ISBN: 978-3-540-47867-6
eBook Packages: Springer Book Archive