A Primal-Dual Algorithm for Weighted Abstract Cut Packing

摘要

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 abores-cences, 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.