A Polynomial Column-wise Rescaling von Neumann Algorithm

Dan Li(dal207lehigh.edu)
Kees Roos(C.Roostudelft.nl )
Tamás Terlaky(terlakylehigh.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