On dyadic fractional packings of T-joins
Abdi, A.
, Cornuéjols, G. P. & Palion, Z.
(2022).
On dyadic fractional packings of T-joins.
SIAM Journal on Discrete Mathematics,
36(3), 2445 - 2451.
https://doi.org/10.1137/21M1445260
, Cornuéjols, G. P. & Palion, Z.
(2022).
On dyadic fractional packings of T-joins.
SIAM Journal on Discrete Mathematics,
36(3), 2445 - 2451.
https://doi.org/10.1137/21M1445260
Let G = (V,E) be a graph, and T ⊆ V a nonempty subset of even cardinality. The famous theorem of Edmonds and Johnson on the T-join polyhedron implies that the minimum cardinality of a T-cut is equal to the maximum value of a fractional packing of T-joins. In this paper, we prove that the fractions assigned may be picked as dyadic rationals, i.e. of the form a 2k for some integers a, k ≥ 0.
