The authors consider a family of subsets of a finite set, each of cardinality n, as feasible solutions of a combinatorial optimization problem. Using weights associated with the elements of the given finite set, k-sum optimization problems and k-sum deviation problems are defined. The authors show that such problems can be solved efficiently if the n-sum problem can be solved efficiently. If the family F is the base system of a matroid, the k-sum optimization problem can be solved by a greedy algorithm. The solutions of k-sum optimization problems are used to give a new characterization of matroids. The k-sum spanning tree problem is also considered. Using an algorithm to obtain minimax spanning trees, a decomposition algorithm is proposed to solve such problems. This decomposition algorithm can also be used to improve the efficiency of most of the known minimum spanning tree algorithms.
