On optimal strategies for upgrading networks

PDF Version Also Available for Download.

Description

We study {ital budget constrained optimal 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 {ital G(V,E)}, in the {ital edge based upgrading model}, it is assumed that each edge {ital e} of the given network has an associated function {ital c(e)} that specifies for each edge {ital e} the amount by which the length {ital l(e)} is to be reduced. In the {ital node based upgrading model} a node {ital v} can be upgraded at an expense of cost {ital ... continued below

Physical Description

25 p.

Creation Information

Krumke, S. O.; Noltemeier, H.; Marathe, M. V.; Ravi, S. S.; Ravi, R. & Sundaram, R. July 2, 1996.

Context

This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided by UNT Libraries Government Documents Department to Digital Library, a digital repository hosted by the UNT Libraries. More information about this article can be viewed below.

Who

People and organizations associated with either the creation of this article or its content.

Authors

  • Krumke, S. O.
  • Noltemeier, H. Wuerzburg Univ. (Germany). Dept. of Computer Science
  • Marathe, M. V. Los Alamos National Lab., NM (United States)
  • Ravi, S. S. State Univ. of New York, Albany, NY (United States). Dept. of Computer Science
  • Ravi, R. Carnegie-Mellon Univ., Pittsburgh, PA (United States). Graduate School of Industrial Administration
  • Sundaram, R. Massachusetts Inst. of Tech., Cambridge, MA (United States)

Sponsor

Publisher

Provided By

UNT Libraries Government Documents Department

Serving as both a federal and a state depository library, the UNT Libraries Government Documents Department maintains millions of items in a variety of formats. The department is a member of the FDLP Content Partnerships Program and an Affiliated Archive of the National Archives.

Contact Us

What

Descriptive information to help identify this article. Follow the links below to find similar items on the Digital Library.

Description

We study {ital budget constrained optimal 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 {ital G(V,E)}, in the {ital edge based upgrading model}, it is assumed that each edge {ital e} of the given network has an associated function {ital c(e)} that specifies for each edge {ital e} the amount by which the length {ital l(e)} is to be reduced. In the {ital node based upgrading model} a node {ital v} can be upgraded at an expense of cost {ital (v)}. Such an upgrade reduces the cost of each edge incident on {ital v} by a fixed factor {rho}, where 0 < {rho} < 1. For a given budget, {ital B}, the goal is to find an improvement strategy such that the total cost of reduction is a most the given budget {ital 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. Define an ({alpha},{beta})-approximation algorithm as a polynomial-time algorithm that produces a solution within {alpha} times the optimal function value, violating the budget constraint by a factor of at most {Beta}. The results obtained in this paper include the following 1. We show that in general the problem of computing optimal reduction strategy for modifying the network as above is {bold NP}-hard. 2. In the node based model, we show how to devise a near optimal strategy for improving the bottleneck spanning tree. The algorithms have a performance guarantee of (2 ln {ital n}, 1). 3. for the edge based improvement problems we present improved (in terms of performance and time) approximation algorithms. 4. We also present pseudo-polynomial time algorithms (extendible to polynomial time approximation schemes) for a number of edge/node based improvement problems when restricted to the class of treewidth-bounded graphs.

Physical Description

25 p.

Notes

OSTI as DE96014461

Source

  • 8. annual Association for Computing Machinery (ACM)-Society for Industrial and Applied Mathematics (SIAM) symposium on discrete algorithms, New Orleans, LA (United States), 5-7 Jan 1997

Language

Item Type

Identifier

Unique identifying numbers for this article in the Digital Library or other systems.

  • Other: DE96014461
  • Report No.: LA-UR--96-2719
  • Report No.: CONF-970142--1
  • Grant Number: W-7405-ENG-36
  • Office of Scientific & Technical Information Report Number: 435321
  • Archival Resource Key: ark:/67531/metadc676505

Collections

This article is part of the following collection of related materials.

Office of Scientific & Technical Information Technical Reports

What responsibilities do I have when using this article?

When

Dates and time periods associated with this article.

Creation Date

  • July 2, 1996

Added to The UNT Digital Library

  • July 25, 2015, 2:20 a.m.

Description Last Updated

  • May 20, 2016, 3:04 p.m.

Usage Statistics

When was this article last used?

Yesterday: 0
Past 30 days: 0
Total Uses: 3

Interact With This Article

Here are some suggestions for what to do next.

Start Reading

PDF Version Also Available for Download.

Citations, Rights, Re-Use

Krumke, S. O.; Noltemeier, H.; Marathe, M. V.; Ravi, S. S.; Ravi, R. & Sundaram, R. On optimal strategies for upgrading networks, article, July 2, 1996; New Mexico. (digital.library.unt.edu/ark:/67531/metadc676505/: accessed September 23, 2017), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.