CEC Faculty Articles

Title

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

Document Type

Article

Date

3-1-2008

Publication Title

Optimization Letters

ISSN or ISBN

1862-4472

Volume

2

Issue

2

First Page

171

Last Page

175

Description

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.

DOI

10.1007/s11590-007-0051-8