The k-sum optimization problem (KSOP) is the combinatorial problem of
finding a solution such that the sum of the weights or the ii largest
weighted elements of the solution is as small as possible. KSOP simult
aneously generalizes both bottleneck and minsum problems. We show that
KSOP can be solved in polynomial time whenever an associated minsum p
roblem can be solved in polynomial time. Further we show that if the m
insum problem is solvable by a polynomial time epsilon-approximation s
cheme then KSOP can also be solved by a polynomial time epsilon-approx
imation scheme.