Abstract
We show that if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and the dual problems, given an optimal solution for one of the problems, then there exists a strongly polynomial algorithm for the general linear programming problem. On the other hand, we give a strongly polynomial time algorithm that finds such a basis, given any pair of optimal solutions (not necessarily basic) for the primal and the dual problems. Such an algorithm is needed when one is using an interior point method and is interested in finding a basis which is both primal- and dual-optimal. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Keywords
Dual (grammatical number)Basis (linear algebra)Linear programmingMathematical optimizationInterior point methodMathematicsPolynomialComputer scienceTime complexityAlgorithm
Affiliated Institutions
Related Publications
Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art
A survey of the significant developments in the field of interior point methods for linear programming is presented, beginning with Karmarkar's projective algorithm and concentr...
Commentary—Theory and Practice for Interior-Point Methods
The last decade has been a fascinating time for researchers interested in linear programming and its extensions. It opened with Narendra Karmarkar's theoretical paper on the com...
Commentary—Progress in Linear Programming
There is little doubt that barrier methods are now indispensable tools in the solution of large-scale linear programming problems. However, it is our opinion that the results of...
Fast Algorithms for Geometric Traveling Salesman Problems
This paper describes efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets. We describe implementations of a dozen starting heur...
Commentary—Interior-Point Methods: Algorithms and Formulations
The paper by Lustig, Marsten, and Shanno (LMS) gives an excellent presentation of the current state of the art for interior-point methods (as represented by their OB1 code) as i...
Publication Info
- Year
- 1991
- Type
- article
- Volume
- 3
- Issue
- 1
- Pages
- 63-65
- Citations
- 101
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
101
OpenAlex
14
Influential
74
CrossRef
Cite This
Nimrod Megiddo
(1991).
On Finding Primal- and Dual-Optimal Bases.
INFORMS Journal on Computing
, 3
(1)
, 63-65.
https://doi.org/10.1287/ijoc.3.1.63
Identifiers
- DOI
- 10.1287/ijoc.3.1.63