MINIMIZING A LINEAR MULTIPLICATIVE-TYPE FUNCTION UNDER NETWORK FLOW CONSTRAINTS

Authors
KUNO T UTSUNOMIYA T
Citation
T. Kuno et T. Utsunomiya, MINIMIZING A LINEAR MULTIPLICATIVE-TYPE FUNCTION UNDER NETWORK FLOW CONSTRAINTS, Operations research letters, 20(3), 1997, pp. 141-148
Citations number
22
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research letters → ACNP
ISSN journal
01676377
Volume
20
Issue
3
Year of publication
1997
Pages
141 - 148
Database
ISI
SICI code
0167-6377(1997)20:3<141:MALMFU>2.0.ZU;2-V
Abstract
In this paper, we consider a special class of nonconvex network flow p roblems, whose objective function is a product of two affine functions . This problem arises when one tries to send as much flow as possible in an ordinary two-terminal network at the minimum possible cost. We w ill show that a primal-dual algorithm can generate a globally optimal solution in pseudo-polynomial time and a globally epsilon-optimal solu tion in polynomial time. (C) 1997 Elsevier Science B.V.