k-sum optimization problems (Q916568): Difference between revisions

Given a family F of subsets of a finite set, where each subset S is of cardinality n and a weight is associated to each element of S, the k-sum optimization problem (denoted by SUM(k)) is to find an S such that the sum of k maximal weights associated with S is minimized. In an equivalent manner k-sum deviation problems are defined. k-sum optimization problems can be solved efficiently if the corresponding n-sum problems are efficiently solvable. An alternative characterization of matroids is given: F is the base system of a matroid if and only if every optimal solution of SUM(n) is also an optimal solution of SUM(1) for arbitrary weights. As a special case the k-sum spanning tree problem is solved by a decomposition algorithm. Finally k-sum deviation problems are shown to be solvable efficiently whenever a related minsum problem is efficiently solvable.