Location Games and Bounds for Median Problems
We consider a two-person zero-sum game in which the maximizer selects a point in a given bounded planar region, the minimizer selects K points in that region,.and the payoff is the distance from the maximizer's location to the minimizer's location closest to it. In a variant of this game,...
Main Authors: | , |
---|---|
Format: | Working Paper |
Language: | en_US |
Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
Online Access: | http://hdl.handle.net/1721.1/5368 |
_version_ | 1811079743076827136 |
---|---|
author | Haimovich, Mordecai Magnanti, Thomas L. |
author_facet | Haimovich, Mordecai Magnanti, Thomas L. |
author_sort | Haimovich, Mordecai |
collection | MIT |
description | We consider a two-person zero-sum game in which the maximizer selects a point in a given bounded planar region, the minimizer selects K points in that region,.and the payoff is the distance from the maximizer's location to the minimizer's location closest to it. In a variant of this game, the maximizer has the privilege of restricting the game to any subset of the given region. We evaluate/approximate the values (and the saddle point strategies) of these games for K = 1 as well as for K + , thus obtaining tight upper bounds (and worst possible demand distributions) for K-median problems. |
first_indexed | 2024-09-23T11:19:50Z |
format | Working Paper |
id | mit-1721.1/5368 |
institution | Massachusetts Institute of Technology |
language | en_US |
last_indexed | 2024-09-23T11:19:50Z |
publishDate | 2004 |
publisher | Massachusetts Institute of Technology, Operations Research Center |
record_format | dspace |
spelling | mit-1721.1/53682019-04-12T08:17:19Z Location Games and Bounds for Median Problems Haimovich, Mordecai Magnanti, Thomas L. We consider a two-person zero-sum game in which the maximizer selects a point in a given bounded planar region, the minimizer selects K points in that region,.and the payoff is the distance from the maximizer's location to the minimizer's location closest to it. In a variant of this game, the maximizer has the privilege of restricting the game to any subset of the given region. We evaluate/approximate the values (and the saddle point strategies) of these games for K = 1 as well as for K + , thus obtaining tight upper bounds (and worst possible demand distributions) for K-median problems. 2004-05-28T19:36:03Z 2004-05-28T19:36:03Z 1985-01 Working Paper http://hdl.handle.net/1721.1/5368 en_US Operations Research Center Working Paper;OR 133-85 1162655 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
spellingShingle | Haimovich, Mordecai Magnanti, Thomas L. Location Games and Bounds for Median Problems |
title | Location Games and Bounds for Median Problems |
title_full | Location Games and Bounds for Median Problems |
title_fullStr | Location Games and Bounds for Median Problems |
title_full_unstemmed | Location Games and Bounds for Median Problems |
title_short | Location Games and Bounds for Median Problems |
title_sort | location games and bounds for median problems |
url | http://hdl.handle.net/1721.1/5368 |
work_keys_str_mv | AT haimovichmordecai locationgamesandboundsformedianproblems AT magnantithomasl locationgamesandboundsformedianproblems |