Optimization Online


A Polynomial Column-wise Rescaling von Neumann Algorithm

Dan Li(dal207***at***lehigh.edu)
Kees Roos(C.Roos***at***tudelft.nl )
Tamás Terlaky(terlaky***at***lehigh.edu)

Abstract: Recently Chubanov proposed a method which solves homogeneous linear equality systems with positive variables in polynomial time. Chubanov's method can be considered as a column-wise rescaling procedure. We adapt Chubanov's method to the von Neumann problem, and so we design a polynomial time column-wise rescaling von Neumann algorithm. This algorithm is the first variant of the von Neumann algorithm with polynomial complexity

Keywords: Linear feasibility problem, Rescaling, von Neumann algorithm, Chubanov's method, Polynomial complexity

Category 1: Linear, Cone and Semidefinite Programming

Citation: Manuscript, Lehigh University, TU Delft, June 2015

Download: [PDF]

Entry Submitted: 06/28/2015
Entry Accepted: 06/28/2015
Entry Last Modified: 06/28/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society