Premium
Construction of efficient tree networks: The pipeline problem
Author(s) -
Zadeh N.
Publication year - 1973
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230030102
Subject(s) - mathematical optimization , pipeline (software) , sorting , regular polygon , tree (set theory) , mathematics , convex function , function (biology) , concave function , computer science , minimum cost flow problem , flow network , combinatorics , algorithm , geometry , evolutionary biology , biology , programming language
It is observed that sample cost functions for the pipeline problem [1] are discretely convex, i.e., their graphs are discrete subsets of graphs of convex functions. As a result, it is shown that the pipeline problem may be attacked by using either a minimum cost flow approach, or a combination of dynamic programming and sorting. Problems with concave cost functions are shown to be relatively easy. Even for problems which are neither convex nor concave, it is shown that in certain instances, only a subset of the data for each cost function is relevant. Error bounds are presented when approximations to the original cost functions are used. Results obtained in [4] for a related problem are summarized.