Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem

Gerard Cornuejols, George L. Nemhauser and Laurence A. Wolsey
Additional contact information
Gerard Cornuejols: Carnegie-Mellon University, Pittsburgh, Pennsylvania
George L. Nemhauser: Cornell University, Ithaca, New York
Laurence A. Wolsey: University of Louvain, Louvain-La-Neuve, Belgium

Operations Research, 1980, vol. 28, issue 4, 847-858

Abstract: We consider a location problem whose mathematical formulation is max s { z ( S ): S ⊆ N , | S | = K }, where z ( S ) = ∑ i ∈ I max j ∈ s c ij and C = ( c ij ) is any non-negative m × n matrix with row index set I and column index set N . We show that any procedure which uses matrix C only to calculate values of the function z ( S ) cannot, with a number of values polynomial in n , guarantee to find an optimal solution. However when C is the edge-vertex incidence matrix of a graph, we show that if n is suitably large and K is fixed or does not grow too rapidly with n , the K vertices of largest degree nearly always constitute an optimal solution.

Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.28.4.847 (application/pdf)

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:inm:oropre:v:28:y:1980:i:4:p:847-858

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().