Abstract | ||
---|---|---|
We consider the problem of locating, on a network, n new facilities that interact with m existing facilities. In addition, pairs of new facilities interact. This problem, the multimedian location problem on a network, is known to be NP-hard. We give a new integer programming formulation of this problem, and show that its linear programming relaxation provides a lower bound that is superior to the bound provided by a previously published formulation. We also report results of computational testing with both formulations. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1023/A:1020755231275 | Annals OR |
Keywords | Field | DocType |
location on networks,median problem,lower bound | Discrete mathematics,Mathematical optimization,Upper and lower bounds,Integer programming,Cutting stock problem,Linear programming relaxation,1-center problem,Mathematics | Journal |
Volume | Issue | ISSN |
110 | 1-4 | 1572-9338 |
Citations | PageRank | References |
0 | 0.34 | 12 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ranganath Nuggehalli | 1 | 2 | 0.72 |
Timothy J. Lowe | 2 | 377 | 39.67 |
James E. Ward | 3 | 54 | 7.09 |