12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > A faster exact separation algorithm for blossom...
View graph of relations

« Back

A faster exact separation algorithm for blossom inequalities

Research output: Contribution in Book/Report/ProceedingsChapter (peer-reviewed)

Published

Publication date2004
Host publicationInteger Programming and Combinatorial Optimization : Proceedings of the 10th International IPCO Conference
EditorsGeorge Nemhauser, Daniel Bienstock
Place of publicationBerlin
PublisherSpringer
Pages19-52
Number of pages34
ISBN (Print)3-540-22113-1
Original languageEnglish

Conference

Conference 10th International IPCO Conference
CountryUnited States
CityNew York
Period7/06/0411/06/04

Publication series

NameLecture Notes in Computer Science
Volume3064

Conference

Conference 10th International IPCO Conference
CountryUnited States
CityNew York
Period7/06/0411/06/04

Abstract

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.

Bibliographic note

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.