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.