von neumann algorithm

Examples with Decreasing Largest Inscribed Ball for Deterministic Rescaling Algorithms

  • Dan Li
  • Tamás Terlaky
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    Recently, Pena and Soheili presented a deterministic rescaling perceptron algorithm and proved that it solves a feasible perceptron problem in $O(m^2n^2\log(\rho^{-1}))$ perceptron update steps, where $\rho$ is the radius of the largest inscribed ball. The original stochastic rescaling perceptron algorithm of Dunagan and Vempala is based on systematic increase of $\rho$, while the proof of … Read more

    A Polynomial Column-wise Rescaling von Neumann Algorithm

  • Dan Li
  • Cornelis Roos
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    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 … Read more