A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem

Eugene L. Lawler
Additional contact information
Eugene L. Lawler: University of California, Berkeley

Management Science, 1972, vol. 18, issue 7, 401-405

Abstract: A general procedure is presented for computing the best, 2nd best,..., Kth best solutions to a given discrete optimization problem. If the number of computational steps required to find an optimal solution to a problem with n(0, 1) variables is c(n), then the amount of computation required to obtain the if best solutions is O(K nc (n)). The procedure specializes to published procedures of Murty and of Yen for the assignment problem and the shortest path problem, respectively. A method is presented for reducing the required amount of storage by a factor of n, compared with the algorithms of Murty and of Yen. It is shown how the K shortest (loopless) paths in an n-node network with positive and negative arcs can be computed with an amount of computation which is O(Kn 3 ). This represents an improvement by a factor of n, compared with Yen's algorithm.

Date: 1972
References: Add references at CitEc
Citations: View citations in EconPapers (30)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.18.7.401 (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:ormnsc:v:18:y:1972:i:7:p:401-405

Access Statistics for this article

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