# A strongly polynomial algorithm for generalized flow maximization

arXiv: https://arxiv.org/abs/1307.6809 · HTML: https://mlsanity.com/paper/1307.6809/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jul 2013.

## Built on by (most cited first, 1 of 1)

- [A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning](https://mlsanity.com/paper/2212.03008/) (2022)

## Abstract (arXiv)

A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique, called continuous scaling. The main measure of progress is that within a strongly polynomial number of steps, an arc can be identified that must be tight in every dual optimal solution, and thus can be contracted. As a consequence of the result, we also obtain a strongly polynomial algorithm for the linear feasibility problem with at most two nonzero entries per column in the constraint matrix.