Facility Dispersion Problems Under Capacity and Cost Constraints

Daniel J. Rosenkrantz (), Giri K. Tayi () and S.S. Ravi ()
Additional contact information
Daniel J. Rosenkrantz: University at Albany—State University of New York
Giri K. Tayi: University at Albany—State University of New York
S.S. Ravi: University at Albany—State University of New York

Journal of Combinatorial Optimization, 2000, vol. 4, issue 1, No 2, 7-33

Abstract: Abstract The MAX-MIN dispersion problem, which arises in the placement of undesirable facilities, involves selecting a specified number of sites among a set of potential sites so as to maximize the minimum distance between any pair of selected sites. We consider different versions of this dispersion problem where each potential site has an associated storage capacity and a storage cost. A typical problem in this context is to choose a subset of potential sites so that the total capacity of the chosen sites is at least a given value, the total storage cost is within the specified budget and the minimum distance between any pair of chosen sites is maximized. Since these constrained optimization problems are NP-hard in general, we consider whether there are efficient approximation algorithms for them with good performance guarantees. Our results include approximation algorithms for some versions, approximation schemes for some geometric versions and polynomial algorithms for special cases. We also present results that bring out the intrinsic difficulty of obtaining near-optimal solutions to some versions.

Keywords: dispersion; storage capacity; storage cost; optimization; polynomial algorithm; approximation scheme (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009802105661 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:4:y:2000:i:1:d:10.1023_a:1009802105661

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009802105661

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().