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.
| Original language | American English |
|---|---|
| Pages (from-to) | 171-175 |
| Number of pages | 5 |
| Journal | Optimization Letters |
| Volume | 2 |
| Issue number | 2 |
| DOIs | |
| State | Published - Apr 28 2007 |
ASJC Scopus Subject Areas
- Control and Optimization
Keywords
- Network design problems
- Approximation algorithms
- Spanning forests
- Integer programs
Disciplines
- Computer Sciences
Fingerprint
Dive into the research topics of 'An approximation algorithm for network design problems with downwards-monotone demand functions'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS