Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems
作者:
PunnenAbraham P.,
NairK. P. K.,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1995)
卷期:
Volume 46,
issue 4
页码: 499-506
ISSN:0160-5682
年代: 1995
DOI:10.1057/jors.1995.68
出版商: Taylor&Francis
关键词: integer programming;minmax problems;polynomial algorithms;transportation problem
数据来源: Taylor
摘要:
AbstractWe consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.
点击下载:
PDF (2649KB)
返 回