Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/11466
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Soares, João | - |
dc.date.accessioned | 2009-09-16T14:44:30Z | - |
dc.date.available | 2009-09-16T14:44:30Z | - |
dc.date.issued | 2000 | - |
dc.identifier.citation | Pré-Publicações DMUC. 00-38 (2000) | en_US |
dc.identifier.uri | https://hdl.handle.net/10316/11466 | - |
dc.description.abstract | This report presents an algorithm that finds an -feasible solution relatively to some constraints of a linear program. The algorithm is a first-order feasible directions method with constant stepsize that attempts to find the minimizer of an exponential penalty function. When embedded with bisection search, the algorithm allows for the approximated solution of linear programs. The running time of our algorithm depends polynomially on 1/ and a parameter width introduced by Plotkin, Shmoys and Tardos in [3] and it is especially interesting when the direction finding (linear) subproblem is considered easy and amenable to reoptimization. We present applications of this framework to the Held and Karp bound on the traveling salesman problem and to a class of hard 0-1 linear programs. Computational results are expected to complement this report in the forthcoming revised version. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Centro de Matemática da Universidade de Coimbra | en_US |
dc.rights | openAccess | en_US |
dc.title | A first-order E-approximation algorithm for large linear programs | en_US |
dc.type | preprint | en_US |
item.fulltext | Com Texto completo | - |
item.openairecristype | http://purl.org/coar/resource_type/c_816b | - |
item.languageiso639-1 | en | - |
item.openairetype | preprint | - |
item.cerifentitytype | Publications | - |
item.grantfulltext | open | - |
Appears in Collections: | FCTUC Matemática - Artigos em Revistas Nacionais |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
A first-order E-approximation algorithm for large linear programs.pdf | 151.5 kB | Adobe PDF | View/Open |
Page view(s)
292
checked on Oct 22, 2024
Download(s)
45
checked on Oct 22, 2024
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.