Integer Rounding for Polymatroid and Branching Optimization Problems
Authors:
- S. BaumSBS. Baum
- Jr. L. E. TrotterJTJr. L. E. Trotter
- 1 December 1981
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 2 (4) , 416-425
Abstract
Where matrix $M\geqq 0$ and vector $w\geqq 0$ have rational entries, define $r^* (w) = \max \{ 1 \cdot y:yM\leqq w,y\geqq 0 \}$, $z^* (w) = \max \{ 1 \cdot y:yM\leqq w,y\geqq 0,y\,{\text{integral}} \}$. Integer round-down holds for M if, for all integral $w\geqq 0$ , $\lfloor r^* (w) \rfloor = z^* (w)$. Similarly, when $\lceil r_* (w) \rceil = z_* (w)$ for all integral $w\geqq 0$, where $r_* (w) = \min \{ 1 \cdot y:yM\leqq w,y\geqq 0 \}$, $z_* (w) = \min \{ 1 \cdot y:yM\geqq w,y\geqq 0,y \,{\text{integral}} \}$, integer round-up holds for M. The integer round-down and round-up properties are shown to hold for certain matrices related to integral polymatroids and branchings in directed graphs.
Keywords
This publication has 14 references indexed in Scilit:
- Finite checkability for integer rounding properties in combinatorial programming problemsMathematical Programming, 1982
- Cyclic Scheduling via Integer Programs with Circular OnesOperations Research, 1980
- Unnetworks, with Applications to Idle Time SchedulingManagement Science, 1978
- Integer Rounding and Polyhedral Decomposition for Totally Unimodular Systems1978
- Blocking pairs of polyhedra arising from network flowsJournal of Combinatorial Theory, Series B, 1975
- Anti-blocking polyhedraJournal of Combinatorial Theory, Series B, 1972
- Matroids and the greedy algorithmMathematical Programming, 1971
- Blocking and anti-blocking pairs of polyhedraMathematical Programming, 1971
- Transversals and matroid partitionJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965
- Minimum partition of a matroid into independent subsetsJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965