An approximation algorithm for network design problems with downwards-monotone demand functions
ISSN or ISBN
Building on an existing 2-approximate algorithm for the class of network design problems with downwards-monotone demand functions, many of which are NP-hard, we present an algorithm that produces solutions that are at least as good as and typically better than solutions produced by the existing algorithm.
Laszlo, Michael J. and Mukherjee, Sumitra, "An approximation algorithm for network design problems with downwards-monotone demand functions" (2008). CEC Faculty Articles. 4.