ON COMBINED MINMAX-MINSUM OPTIMIZATION

In this paper we present a modification of Minoux's algorithm for solv ing the combined minmax-minsum combinatorial optimization problem (MMC OP) in view of improving its average performance. Computational result s are presented which establish the superiority of the modified algori thm over the existing algorithms. We then study the relationship betwe en the optimal solutions of MMCOP and an associated minsum problem in the context of matroids. Further, we introduce combined minmax-minsum linear programming problem (MMLP). MMLP can be transformed into a line ar program with additional constraints and variables. We present an ef ficient simplex based algorithm to solve MMLP which treats these addit ional constraints implicitly. Our computational results show that the proposed algorithm performs better than the simplex method used direct ly on a linear program equivalent to MMLP.