Monday, 16:15 - 16:40 h, Room: H 3021


Tom McCormick
A primal-dual algorithm for weighted abstract cut packing

Coauthor: Britta Peis


Hoffman and Schwartz 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, 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 by Martens and McCormick for WAF, in that both algorithms depend on a relaxation by a scalar parameter, and then need to solve an unweighted "restricted'' subproblem. 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.


Talk 3 of the invited session Mon.3.H 3021
"Equilibria and combinatorial structures" [...]
Cluster 2
"Combinatorial optimization" [...]


  Online lending company provides a wide range of ways to get money by means of Tennessee Loans Online. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.