Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1030.90094
Benczúr, András A.
Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems. (English)
[J] Discrete Appl. Math. 129, No.2-3, 233-262 (2003). ISSN 0166-218X

Summary: In their seminal paper, Frank and Jordán 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.\par 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 different from that of an independent recent result of Frank. It finds covers of partially ordered sets that satisfy natural abstract properties slightly extending those in Frank and Jordán. The algorithm resembles primal--dual 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 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 (REDUCE step).

MSC 2000:: *90C27 Combinatorial programming
68W05 Nonnumerical algorithms
68R10 Graph theory in connection with computer science

Keywords: optimization problems; edge augmentation

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]