On k-sum optimization

On k-sum optimization

0.00 Avg rating0 Votes
Article ID: iaor19972005
Country: Netherlands
Volume: 18
Issue: 5
Start Page Number: 233
End Page Number: 236
Publication Date: Mar 1996
Journal: Operations Research Letters
Authors: ,
Abstract:

The k-sum optimization problem (KSOP) is the combinatorial problem of finding a solution such that the sum of the weights of the k largest weighted elements of the solution is as small as possible, KSOP simultaneously generalizes both bottleneck and minsum problems. The authors show that KSOP can be solved in polynomial time whenever an associated minsum problem can be solved in polynomial time. Further they show that if the minsum problem is solvable by a polynomial time •-approximation scheme then KSOP can also be solved by a polynomial time •-approximation scheme.

Reviews

Required fields are marked *. Your email address will not be published.