Végh, László A. (2016) A strongly polynomial algorithm for generalized flow maximization. Mathematics of Operations Research, 42 (1). pp. 179-211. ISSN 0364-765X
|
PDF
- Accepted Version
Download (624kB) | Preview |
Identification Number: https://doi.org/10.1287/moor.2016.0800
Abstract
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.
| Item Type: | Article |
|---|---|
| Official URL: | http://pubsonline.informs.org/journal/moor |
| Additional Information: | © 2016 INFORMS |
| Divisions: | Mathematics |
| Subjects: | Q Science > QA Mathematics |
| Date Deposited: | 13 Mar 2017 11:49 |
| Last Modified: | 20 Sep 2025 01:29 |
| URI: | http://eprintstest.lse.ac.uk/id/eprint/69679 |
Actions (login required)
 |
View Item |
