go-v.orgdoi

An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming

Clóvis C. Gonzaga, Michael J. Todd · SIAM Journal on Optimization · 1992

  • DOI 10.1137/0802017
  • Publisher Society for Industrial and Applied Mathematics
  • Type article
  • Issued 1992

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

SIAM Journal on Optimization · Society for Industrial and Applied Mathematics · article · 1992

Abstract

An algorithm based on reducing a suitable potential function for linear programming is described. At each iteration, separate scalings are applied to the primal and dual problems, and a step is taken in either the primal or the dual space. It is shown that a constant reduction can always be achieved, leading to a bound of $O(n^{1/2} L)$ iterations. Moreover, it is also shown that a reduction of $\Omega (n^{1/4} )$ can usually be obtained, so that $O(n^{1/4} L)$ iterations are expected to suffice. Finally, it is proved that no general algorithm taking either primal or dual steps and guaranteeing the reduction of such a potential function can achieve R-order of convergence greater than one.

Open the resolved locator · 10.1137/0802017

Metadata licence: OpenAlex metadata (CC0)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 04:44 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://doi.org/10.1137/0802017
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.