Monotonizing linear programs with up to two
nonzeroes per column
Abstract
Linear programming problems with up to two nonzeroes per column in
the constraint matrix are shown equivalent to generalized network
flow problem. The transformation is applied for solving the
maximum cut problem, the $b$-matching problem in strongly
polynomial time and for approximation algorithms for certain
integer versions of the problem.
Download Information
Click on the following title to view and download the paper in PostScript format.
- Monotonizing linear programs with
up to two nonzeroes per column(12 pages, 99 KB)
- Dorit S. Hochbaum. Manuscript (2003), For published version see Operations
Research Letters 2003
hochbaum@ieor.berkeley.edu
6/3/03