|
In their seminal paper, Frank and Jordán show that a large class of
optimization problems including certain directed graph augmentation
ones fall into the class of covering supermodular functions
over pairs of sets. They also give an algorithm for such problems,
however that relies on the ellipsoid method. Prior to our result, combinatorial algorithms
existed only for the 0-1 valued problem. Our key result is a
combinatorial algorithm for the general problem that includes
directed vertex or S-T connectivity augmentation. The algorithm is
based on the second author's previous algorithm for the 0-1 valued
case.
Our algorithm uses a primal-dual scheme for finding covers of
partially ordered sets that satisfy natural abstract properties as in
Frank and Jordán. For an initial (possibly greedy) cover the
algorithm searches for witnesses for the necessity of each element in
the cover. If no two (weighted) witnesses have a common cover, the
solution is optimal. As long as this is not the case, the witnesses
are gradually exchanged by smaller ones. Each witness change defines
an appropriate change in the solution; these changes are finally
unwound in a shortest path manner to obtain a solution of size one
less.
Bibtex entry:
| AUTHOR | = | {Bencz{\'u}r A., Andr{\'a}s and V{\'e}gh, L{\'a}szl{\'o}}, |
| TITLE | = | {Primal-dual approach for directed vertex connectivity augmentation and generalizations}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2005}, |
| NUMBER | = | {TR-2005-06} |