Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed)
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed)
}
TY - CHAP
T1 - A faster exact separation algorithm for blossom inequalities
AU - Letchford, A N
AU - Reinelt, G
AU - Theis, D O
N1 - The full version of this paper appeared as: A.N. Letchford, G. Reinelt & D.O. Theis (2008) Odd minimum cut-sets and b-matchings revisited. SIAM J. Discr. Math., 22(4), 1480-1487.
PY - 2004
Y1 - 2004
N2 - In 1982, Padberg and Rao gave a polynomial-time separation algorithm for b-matching polyhedra. The current best known implementations of their separation algorithm run in O(|V|^2|E| log(|V|^2/|E|)) time when there are no edge capacities, but in O(|V||E|^2 log(|V|^2/|E|)) time when capacities are present. We propose a new exact separation algorithm for the capacitated case which has the same running time as for the uncapacitated case. For the sake of brevity, however, we will restrict our introduction to the case of perfect 1-capacitated b-matchings, which includes, for example, the separation problem for perfect 2-matchings. As well as being faster than the Padberg-Rao approach, our new algorithm is simpler and easier to implement.
AB - In 1982, Padberg and Rao gave a polynomial-time separation algorithm for b-matching polyhedra. The current best known implementations of their separation algorithm run in O(|V|^2|E| log(|V|^2/|E|)) time when there are no edge capacities, but in O(|V||E|^2 log(|V|^2/|E|)) time when capacities are present. We propose a new exact separation algorithm for the capacitated case which has the same running time as for the uncapacitated case. For the sake of brevity, however, we will restrict our introduction to the case of perfect 1-capacitated b-matchings, which includes, for example, the separation problem for perfect 2-matchings. As well as being faster than the Padberg-Rao approach, our new algorithm is simpler and easier to implement.
U2 - 10.1007/978-3-540-25960-2_15
DO - 10.1007/978-3-540-25960-2_15
M3 - Chapter (peer-reviewed)
SN - 3-540-22113-1
T3 - Lecture Notes in Computer Science
SP - 19
EP - 52
BT - Integer Programming and Combinatorial Optimization
A2 - Nemhauser, George
A2 - Bienstock, Daniel
PB - Springer
CY - Berlin
T2 - 10th International IPCO Conference
Y2 - 7 June 2004 through 11 June 2004
ER -