Cooperative facility location games

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cooperative facility location games

Full text

Pdf (928 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 76 - 85

Year of Publication: 2000

ISBN:0-89871-453-2

Authors

Michel X. Goemans	Department of Mathematics, Room 2-351, M.I.T., Cambridge, MA and C.O.R.E., Louvain-la-Neuve, Belgium
Martin Skutella	TU Berlin, Fachbereich Mathematik, MA 6-1, Straβe des 17, Juni 136, 10623 Berlin, Germany and C.O.R.E., Louvain-la-Neuve, Belgium

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 36, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. L. Balinski. Integer programming: Methods, uses, computation. Management Science, 12:253- 313, 1965.
	2	Amotz Bar-Noy , Sudipto Guha , Joseph (Seffi) Naor , Baruch Schieber, Approximating the throughput of multiple machines under real-time scheduling, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.622-631, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301420]
	3	P. Chardaire. On the core of facility location games. Manuscript.
	4	Fabián A. Chudak, Improved Approximation Algorithms for Uncapitated Facility Location, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.180-194, June 22-24, 1998
	5	G. Cornu6jols, G. L. Nemhauser, and L. A. Wolsey. The uncapacitated facility location problem, in P. Mirchandani and R. Francis, editors, Discrete Location Theory, pages 119 - 17 I. John Wiley and Sons, Inc., New York, 1990.
	6	M. Gr0tschel, L. Lov~z, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, Berlin, 1988.
	7	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
	8	A. Kolen. Solving covering problems and the uncapacitated plant location problem on trees. European Journal of Operational Research, 12:266- 278, 1983.
	9	J. Krarup and O. Bilde. Plant location, set covering and economic lot size: an O(mn)-algorithm for structured problems. In L. Collatz and W. Wetterling, editors, Numerische Methoden bei Optimierungsaufgaben - Band 3 (Optimierkng bei graphentheoretischen und ganzzahligen Problemen), volume 36 of International series of numerical mathematics, pages 155-180. Birkhaeuser Verlag, 1977.
	10	P. B. Mirchandani and P. L. Francis, editors. Discrete Location Theory. John Wiley & Sons, 1990.
	11	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	12	H. Moulin. Cooperative Microeconomics: A Game-Theoretic Introduction. Princeton University Press, 1995.
	13	George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
	14	A. Oudjit. Median Locations on Deterministic and Probabilistic Multidimensional Net;vorks. PhD thesis, Rensselaer Polytechnic Institute, Troy, New York, 1981.
	15	M. Padberg. Linear Optimization and Extensions. Springer, Berlin, 1995.
	16	A. Tamir. On the core of cost allocation games defined on location problems. Transportation Science, 27:81 - 86, 1992.
	17	Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

CITED BY 13

	Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Decision Support Systems, v.39 n.1, p.11-22, March 2005
	Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Proceedings of the 4th ACM conference on Electronic commerce, p.108-114, June 09-12, 2003, San Diego, CA, USA
	Nicole Immorlica , Mohammad Mahdian , Vahab S. Mirrokni, Limitations of cross-monotonic cost sharing schemes, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	R. C. Chakinala , A. Kumarasubramanian , K. A. Laing , R. Manokaran , C. Pandu Rangan , R. Rajaraman, Playing push vs pull: models and algorithms for disseminating dynamic data in networks, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Qizhi Fang , Maocheng Cai , Xiaotie Deng, Total balancedness condition for Steiner tree games, Discrete Applied Mathematics, v.127 n.3, p.555-563, 01 May 2003
	Kamal Jain , Vijay Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.364-372, July 2001, Hersonissos, Greece
	Xiaotie Deng , Qizhi Fang , Xiaoxun Sun, Finding nucleolus of flow game, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.124-131, January 22-26, 2006, Miami, Florida
	Evangelos Markakis , Amin Saberi, On the core of the multicommodity flow game, Proceedings of the 4th ACM conference on Electronic commerce, p.93-97, June 09-12, 2003, San Diego, CA, USA
	Evangelos Markakis , Amin Saberi, On the core of the multicommodity flow game, Decision Support Systems, v.39 n.1, p.3-10, March 2005
	Byung-Gon Chun , Kamalika Chaudhuri , Hoeteck Wee , Marco Barreno , Christos H. Papadimitriou , John Kubiatowicz, Selfish caching in distributed systems: a game-theoretic analysis, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Ning Chen , Xiaotie Deng , Xiaoming Sun, On complexity of single-minded auction, Journal of Computer and System Sciences, v.69 n.4, p.675-687, December 2004
	Kamal Jain , Mohammad Mahdian , Evangelos Markakis , Amin Saberi , Vijay V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, Journal of the ACM (JACM), v.50 n.6, p.795-824, November 2003
	Yoshio Okamoto, Traveling salesman games with the Monge property, Discrete Applied Mathematics, v.138 n.3, p.349-369, 15 April 2004