Multicommodity facility location

ABSTRACT

Multicommodity facility location refers to the extension of facility location to allow for different clients having demand for different goods, from among a finite set of goods. This leads to several optimization problems, depending on the costs of opening facilities (now a function of the commodities it serves). In this paper, we introduce and study some variants of multicommodity facility location, and provide approximation algorithms and hardness results for them.

REFERENCES

• 1: Sanjeev Arora , Madhu Sudan, Improved low-degree testing and its applications, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.485-495, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258642]
• 2: Vijay Arya , Naveen Garg , Rohit Khandekar , Kamesh Munagala , Vinayaka Pandit, Local search heuristic for k-median and facility location problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.21-29, July 2001, Hersonissos, Greece [doi>10.1145/380752.380755]
• 3: M. L. Balinski. On finding integer solutions to linear programs. In Proc. IBM Scientific Computing Symposium on Combinatorial Problems, 225--248, 1966.
• 4: M. Charikar, J. Naor and B. Scheiber. Resource optimization in QoS multicast routing of real-time multimedia. In Proceedings of IEEE INFOCOM, 1518--1527, 2000.
• 5: Sudipto Guha , Samir Khuller, Greedy strikes back: improved facility location algorithms, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.649-657, January 25-27, 1998, San Francisco, California, United States
• 6: Magnús M. Halldórsson, Approximating k-Set Cover and Complementary Graph Coloring, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.118-131, June 03-05, 1996
• 7: Amit Kumar , Anupam Gupta , Tim Roughgarden, A Constant-Factor Approximation Algorithm for the Multicommodity, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.333, November 16-19, 2002
• 8: Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
• 9: Mohammad Mahdian , Yinyu Ye , Jiawei Zhang, Improved Approximation Algorithms for Metric Facility Location Problems, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.229-242, September 17-21, 2002
• 10: A. Meyerson, Online Facility Location, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.426, October 14-17, 2001
• 11: M. Pál , É. Tardos , T. Wexler, Facility Location with Nonuniform Hard Capacities, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.329, October 14-17, 2001
• 12: Ravi Ramamoorthi , Amitabh Sinha, Integrated Logistics: Approximation Algorithms Combining Facility Location and Network Design, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.212-229, May 27-29, 2002
• 13: David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
• 14: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001