Matroid theory
Matroid-constrained number partitioning is a variant of the multiway number partitioning problem, in which the subsets in the partition should be independent sets of a matroid. The input to this problem is a set "S" of items, a positive integer "m", and some "m" matroids over the same set "S". The goal is to partition "S" into "m" subsets, such that each subset "i" is an independent set in matroid "i". Subject to this constraint, some objective function should be minimized, for example, minimizing the largest sum item sizes in a subset. In a more general variant, each of the "m" matroids has a weight function, which assigns a weight to each element of the ground-set. Various objective functions have been considered. For each of the three operators max,min,sum, one can use this operator on the weights of items in each subset, and on the subsets themselves. All in all, there are 9 possible objective functions, each of which can be maximized or minimized.
Special cases.
Some important special cases of matroid-constrainted partitioning problems are:
General matroid constraints.
General matroid constraints were first considered by Burkard and Yao. They showed that minimizing (sum,max) can be done in polynomial time by a greedy algorithm for a subclass of matroids, which includes partition matroids. Hwang and Rothblum presented an alternative sufficient condition.
Wu and Yao presented an approximation algorithm for minimizing (max,sum) with general matroid constraints.
Abbassi, Mirrokni and Thakur present an approximation algorithm for a problem of "diversity maximization" under matroid constraints.
Kawase, Kimura, Makino and Sumita show that the maximization problems can be reduced to minimization problems. Then, they analyze seven minimization problems:
Related problems.
Matroid partitioning is a different problem, in which the number of parts "m" is not fixed. There is a single matroid, and the goal is to partition its elements into a smallest number of independent sets.
References.
 ;templatestyles src="Reflist/styles.css" / ;