Approximation Algorithms for Problems Combining Facility Location and Network Design

References

• Agrawal A., Klein P., Ravi R. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. (1995) 24:440–456Crossref, Google Scholar
• 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 Sympos. on the Theory of Comput. (2001) Crete, Greece:21–29Crossref, Google Scholar
• Balinski M. L. On finding integer solutions to linear programs. Proc. IBM Scientific Comput. Sympos. on Combin. Problems (1966) 225–248Google Scholar
• Charikar M., Guha S., Shmoys D., Tardos E. A constant-factor approximation algorithm for the k-median problem. Proc. 31st ACM Sympos. on Theory of Comput. (1999) Atlanta, GA:1–10Google Scholar
• Cornuejols G., Nemhauser G., Wolsey L., Mirchandani P., Francis R. The uncapacitated facility location problem. Discrete Location Theory (1990) (Wiley, New York) 119–171Google Scholar
• Goel A., Estrin D. Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk. Proc. 14th ACM-SIAM Sympos. on Discrete Algorithms (2003) Baltimore, MD:499–505Google Scholar
• Goemans M. X., Williamson D. P. A general approximation technique for constrained forest problems. SIAM J. Comput. (1995) 24(2):296–317Crossref, Google Scholar
• Guha S., Meyerson A., Munagala K. Improved combinatorial algorithms for single sink edge installation problems. Proc. 33rd ACM Sympos. on the Theory of Comput. (2001) Crete, Greece:383–388Google Scholar
• Gupta A., Roughgarden A. Simpler and better approximation algorithms for network design. Proc. 35th ACM Sympos. on the Theory of Comput. (2003) San Diego, CA:365–372Crossref, Google Scholar
• Haresamudra B., Taylor G. D., Taha H. A. An interactive approach to locate breakbulk terminals for LTL trucking operations. (1995) . Final research report MBTC-FR-1037, Mack-Blackwell Transportation Center, University of Arkansas, Fayetteville, ARGoogle Scholar
• Hassin R., Ravi R., Salman F. S. Approximation algorithms for a capacitated network design problem. Approximation Algorithms for Combinatorial Optimization (2000) (Springer, Germany) 167–176Lecture Notes in Computer Science, Vol. 1913Crossref, Google Scholar
• Jain K., Vazirani V. V. Primal-dual approximation algorithms for metric facility location and k-median problems. Proc. 40th Ann. IEEE Sympos. on Foundations of Comput. Sci. (1999) New York:2–13Crossref, Google Scholar
• Jain K., Mahdian M., Saberi A. A new greedy approach for facility location problems. Proc. 34th ACM Sympos. on the Theory of Comput. (2002) Montreal, Quebec, Canada:731–740Crossref, Google Scholar
• Korupulu M., Plaxton C., Rajaraman R. Analysis of a local search heuristic for facility location problems. Proc. 9th ACM-SIAM Sympos. on Discrete Algorithms (1998) San Francisco, CA:1–10Google Scholar
• Mahdian M., Ye Y., Zhang J. A 1.52 approximation algorithm for the uncapacitated facility location problem. Approximation Algorithms for Combinatorial Optimization (2002) (Springer, Germany) 229–242Crossref, Google Scholar
• Mansour Y., Peleg D. An approximation algorithm for minimum-cost network design. (1994) . Technical report CS94-22, The Weizman Institute of Science, Rehovot, IsraelGoogle Scholar
• Meyerson A., Munagala K., Plotkin S. Cost-distance: Two metric network design. Proc. 41st Ann. IEEE Sympos. on Foundations of Comput. Sci. (2000) Redondo Beach, CA:624–630Crossref, Google Scholar
• Min H., Current J. R., Schilling D. A. The multiple depot vehicle routing problem with backhauling. J. Bus. Logist. (1992) 13:259–288Google Scholar
• Ravi R. A primal-dual approximation algorithm for the Steiner forest problem. Inform. Processing Lett. (1994) 50(4):185–190Crossref, Google Scholar
• Robins G., Zelikovsky A. Improved Steiner tree approximation in graphs. Proc. 10th ACM-SIAM Sympos. on Discrete Algorithms (1999) Baltimore, MD:770–779Google Scholar
• Salman F. S., Cheriyan J., Ravi R., Subramanian S. Buy-at-bulk network design: Approximating the single-sink edge installation problem. SIAM J. Optim. (2000) 11(3):595–610Crossref, Google Scholar
• Shmoys D., Tardos E., Aardal K. Approximation algorithms for the facility location problem. Proc. 29th ACM Sympos. on the Theory of Comput. (1997) El Paso, TX:265–274Google Scholar