POLYNOMIAL ALGORITHMS FOR A CLASS OF DISCRETE MINMAX LINEAR-PROGRAMMING PROBLEMS

We consider the problem of obtaining integer solutions to a minmax lin ear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved i n polynomial time. For this restricted class of problems two polynomia l time algorithms are suggested, one of which is strongly polynomial w henever its continuous analogue and an associated linear programming p roblem can be solved by a strongly polynomial algorithm. Our algorithm s can also be used to obtain integer solutions for the minmax transpor tation problem with an inequality budget constraint. The equality cons trained version of this problem is shown to be NP-complete. We also pr ovide some new insights into the solution procedures for the continuou s minmax linear programming problem.