Article ID: | iaor20001722 |
Country: | Germany |
Volume: | 84 |
Issue: | 3 |
Start Page Number: | 519 |
End Page Number: | 527 |
Publication Date: | Jan 1999 |
Journal: | Mathematical Programming |
Authors: | Szigeti Z. |
Keywords: | hypergraphs |
The hypergraph augmentation problem is to augment a hypergraph by hyperedges to meet prescribed local connectivity requirements. We provide here a minimax theorem for this problem. The result is derived from the degree constrained version of the problem by a standard method. We shall construct the required hypergraph for the latter problem by a greedy type algorithm. A similar minimax result will be given for the problem of augmenting a hypergraph by weighted edges (hyperedges of size two with weights) to meet prescribed local connectivity requirements. Moreover, a special case of an earlier result of Schrijver on supermodular colourings shall be derived from our theorem.