The Constrained Bottleneck Problem in Networks

O. Berman, D. Einav and G. Handler
Additional contact information
O. Berman: University of Massachusetts, Boston, Massachusetts
D. Einav: Tel-Aviv University, Tel-Aviv, Israel
G. Handler: Stanford University, Stanford, California

Operations Research, 1990, vol. 38, issue 1, 178-181

Abstract: We consider problems on networks that are captured by two performance measures. One performance measure is any general cost function of a solution; the other is a bottleneck measure that describes the worst (maximum cost) component of the solution. The paper contains algorithms to solve three problems. In one problem, we minimize the bottleneck subject to a constraint on the generalized cost. In the second problem, we minimize the generalized cost subject to a constraint on the bottleneck. In the third problem, we consider the two criteria simultaneously and find all the Pareto optimum solutions. The major result is that the introduction of the bottleneck measure changes the complexity of the original (general cost) problem by a factor which is at most linear in the number of links.

Keywords: algorithms; multiple criteria algorithms for multiple criteria problems on networks; networks: multiple criteria problems on networks (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.38.1.178 (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:38:y:1990:i:1:p:178-181

Access Statistics for this article

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