A Polynomially Bounded Algorithm for a Nonlinear Network Allocation Problem

T. R. Elken, H. T. Freedman and A. E. Gibson
Additional contact information
T. R. Elken: Bell Laboratories, Whippany, New Jersey
H. T. Freedman: AT&T, New York
A. E. Gibson: AT&T Long Lines, Bedminster, New Jersey

Management Science, 1981, vol. 27, issue 9, 1054-1066

Abstract: This paper presents an algorithm for determining the optimal allocation to demand points when the distribution system is a capacitated arborescence of N arcs and the cost (return) functions are convex (concave). It is proved that the algorithm generates an optimal solution by solving at most N(N + 1)/2 single-constraint subproblems. If the cost functions allow the Lagrange multiplier for the subproblems to be evaluated in polynomial time, then this is a polynomial algorithm. The analysis is motivated by the problem of allocating spare capacity in the loop plant portion of telephone networks.

Keywords: networks/graphs:; flow; algorithms (search for similar items in EconPapers)
Date: 1981
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.27.9.1054 (application/pdf)

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:inm:ormnsc:v:27:y:1981:i:9:p:1054-1066

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().