2011 | OriginalPaper | Chapter
A Primal-Dual Algorithm for Weighted Abstract Cut Packing
Authors : S. Thomas McCormick, Britta Peis
Published in: Integer Programming and Combinatoral Optimization
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Hoffman and Schwartz [13] developed the Lattice Polyhedron model and proved that it is totally dual integral (TDI), and so has integral optimal solutions. The model generalizes many important combinatorial optimization problems such as polymatroid intersection, cut covering polyhedra, min cost aborescences, etc., but has lacked a combinatorial algorithm. The problem can be seen as the blocking dual of Hoffman’s Weighted Abstract Flow (WAF) model [11], or as an abstraction of ordinary Shortest Path and its cut packing dual, so we call it Weighted Abstract Cut Packing (WACP). We develop the first combinatorial algorithm for WACP, based on the Primal-Dual Algorithm framework. The framework is similar to that used in [14] for WAF, in that both algorithms depend on a relaxation by a scalar parameter, and then need to solve an unweighted “restricted” subproblem. The subroutine to solve WACP’s restricted subproblem is quite different from the corresponding WAF subroutine. The WACP subroutine uses an oracle to solve a restricted abstract cut packing/shortest path subproblem using greedy cut packing, breadth-first search, and an update that achieves complementary slackness. This plus a standard scaling technique yields a polynomial combinatorial algorithm.