An approximation algorithm for network design problems with downwards-monotone demand functions |
| |
| Authors: | Michael Laszlo Sumitra Mukherjee |
| |
| Affiliation: | (1) Graduate School of Computer and Information Sciences, Nova Southeastern University, Fort Lauderdale, FL 33314, USA |
| |
| Abstract: | 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. |
| |
| Keywords: | Network design problems Approximation algorithms Spanning forests Integer programs |
| 本文献已被 SpringerLink 等数据库收录！ |
