On uniform k-partition problems Original Research Article

We study various uniform k-partition problems which consist in partitioning m sets, each of cardinality k, into k sets of cardinality m such that each of these sets contains exactly one element from every original set. The problems differ according to the particular measure of “set uniformity” to be optimized. Most problems are polynomial and corresponding solution algorithms are provided. A few of them are proved to be NP-hard. Examples of applications to scheduling and routing problems are also discussed.