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

Author(s)

Michael J. Laszlo, Nova Southeastern UniversityFollow
Sumitra Mukherjee, Nova Southeastern UniversityFollow

Document Type

Article

Publication Title

Optimization Letters

ISSN

1862-4472

Publication Date

3-1-2008

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.

DOI

10.1007/s11590-007-0051-8

Volume

2

Issue

2

First Page

171

Last Page

175

NSUWorks Citation

Laszlo, Michael J. and Mukherjee, Sumitra, "An approximation algorithm for network design problems with downwards-monotone demand functions" (2008). CCE Faculty Articles. 4.
https://nsuworks.nova.edu/gscis_facarticles/4