A polynomial projection-type algorithm for linear programming

László A. Végh and Giacomo Zambelli

LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library

Abstract: We propose a simple O([n5/logn]L)O([n5/logn]L) algorithm for linear programming feasibility, that can be considered as a polynomial-time implementation of the relaxation method. Our work draws from Chubanov’s “Divide-and-Conquer” algorithm (Chubanov, 2012), with the recursion replaced by a simple and more efficient iterative method. A similar approach was used in a more recent paper of Chubanov (2013).

Keywords: Linear programming; Polynomial-time algorithms; Relaxation method (search for similar items in EconPapers)
JEL-codes: J1 (search for similar items in EconPapers)
Date: 2014-01-01
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Published in Operations Research Letters, 1, January, 2014, 42(1), pp. 91-96. ISSN: 0167-6377

Downloads: (external link)
http://eprints.lse.ac.uk/55610/ Open access version. (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:ehl:lserod:55610

Access Statistics for this paper

More papers in LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library LSE Library Portugal Street London, WC2A 2HD, U.K.. Contact information at EDIRC.
Bibliographic data for series maintained by LSERO Manager ().