
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Bicriteria Network Optimization Problems
Naoki KATOH
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E75A
No.3
pp.321329 Publication Date: 1992/03/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: INVITED PAPER (Special Section on the 4th Karuizawa Workshop on Circuits and Systems) Category: Keyword: network algorithms, multiobjective program,
Full Text: PDF>>
Summary:
This paper presents a survey on bicriteria network optimization problems. When there are two conflicting criteria that evaluate the solution, the bicriteria optimization is to find a solution for which these criteria are both acceptably satisfied. Standard approaches to these problems are to combine these two criteria into an aggregated single criterion. Among such problems, this paper first deals with the case in which the aggregated objective function, denoted h(f_{1}(x), f_{2}(x)), is convex in original two objectives f_{1}(x) and f_{2}(x), and, as its special case, it reviews a strongly polynomial algorithm for the bicriteria minimumcost circulation problem. It then discusses the case in which h is concave and demonstrates that a parametric approach is effective for this case. Several interesting applications in network optimization that belong to this class are also introduced. Finally we deal with the minimum range problems which seek to find a solution such that weights of the components used in the solution are most uniform. We shall present efficient algorithms for solving these problems arised in network optimization.

