Abstract: | We say that a polyhedronP satisfies weak integral decomposition if whenever an integral vector is the sum ofk vectors inP it is also the sum ofk integral vectors inP. This property is related to rounding results for packing and covering problems. We study the property and two related properties,
and give results concerning integral polymatroids, totally unimodular matrices and network flows, pairs of strongly-base-orderable
matroids, and branchings in directed graphs. |