An approximation algorithm for network design problems with downwards-monotone demand functions

作者：Laszlo Michael^*; Mukherjee Sumitra

来源：Optimization Letters, 2008, 2(2): 171-175.

DOI：10.1007/s11590-007-0051-8

• Network design problems
• Approximation algorithms
• Spanning forests
• Integer programs

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.

• 出版日期2008-3
• 单位东南大学