Pushdown–reduce: an algorithm for connectivity augmentation and poset covering problems

✍ Scribed by András A. Benczúr

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 557 KB
• Volume: 129
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00570-x

✦ Synopsis

In their seminal paper, Frank and Jordà an show that a large class of optimization problems including certain directed edge 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.

Our main result is a combinatorial algorithm for the restricted covering problem when the supermodular function is 0 -1 valued; the problem includes directed vertex or S -T connectivity augmentation by one. Our algorithm uses an approach completely di erent from that of an independent recent result of Frank. It ÿnds covers of partially ordered sets that satisfy natural abstract properties slightly extending those in Frank and Jordà an. The algorithm resembles primaldual augmenting path algorithms: For an initial (possibly greedy) cover the algorithm searches for witnesses for the necessity of each element in the cover. If no two witness have a common cover, the solution is optimal. As long as this is not the case, the witnesses are gradually exchanged by smaller ones (PUSHDOWN step). Each witness change deÿnes an appropriate change in the solution; these changes are ÿnally unwound in a shortest path manner to obtain a solution of size one less (REDUCE step).