Approximation Algorithms for Certain Network Improvement Problems

Sven O. Krumke (), Madhav V. Marathe (), Hartmut Noltemeier, R. Ravi () and S. S. Ravi ()
Additional contact information
Sven O. Krumke: Konrad-Zuse-Zentrum für Informationstechnik Berlin
Madhav V. Marathe: Madhav V. Marathe, Los Alamos National Laboratory
Hartmut Noltemeier: University of Würzburg
R. Ravi: Carnegie Mellon University
S. S. Ravi: University at Albany–SUNY

Journal of Combinatorial Optimization, 1998, vol. 2, issue 3, No 4, 257-288

Abstract: Abstract We study budget constrained network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an edge weighted graph G = (V, E), in the edge based upgrading model, it is assumed that each edge e of the given network also has an associated function ce (t) that specifies the cost of upgrading the edge by an amount t. A reduction strategy specifies for each edge e the amount by which the length ℓ(e) is to be reduced. In the node based upgrading model, a node v can be upgraded at an expense of c(v). Such an upgrade reduces the delay of each edge incident on v. For a given budget B, the goal is to find an improvement strategy such that the total cost of reduction is at most the given budget B and the cost of a subgraph (e.g. minimum spanning tree) under the modified edge lengths is the best over all possible strategies which obey the budget constraint. After providing a brief overview of the models and definitions of the various problems considered, we present several new results on the complexity and approximability of network improvement problems.

Keywords: Complexity; NP-hardness; Approximation Algorithms (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009798010579 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:2:y:1998:i:3:d:10.1023_a:1009798010579

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009798010579

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().