Algorithms for a Network Design Problem With Crossing Supermodular Demands

Date Added: Jan 2010
Format: PDF

This paper presents algorithms for a class of directed network design problems. The network design problem is to find a minimum cost sub graph such that for each vertex set S there are at least f(S) arcs leaving the set S. In the last 10 years general techniques have been developed for designing approximation algorithms for undirected network design problems. Recently the author gave a 2-approximation algorithm for the case when the function f is weakly supermodular. There has been very little progress made on directed network design problems. The main techniques used for the undirected problems do not have simple extensions to the directed case.