On the Approximability of Some Network Design Problems

Download Now Date Added: Jan 2010
Format: PDF

Approximation algorithms have had much success in the area of network design, with both combinatorial and linear-programming based techniques leading to many constant factor approximation algorithms. Despite these successes, several basic network design problems have eluded the quest for constant-factor approximations, with the current best approximation guarantees being logarithmic or worse. Moreover, none of the previously-known hardness results precludes the possibility of constant-factor approximation algorithms for these problems.