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.
On the uniform k-partition problems / Dell'Olmo, Paolo; Hansen, P.; Pallottino, S.; Storchi, G.. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 150:(2001), pp. 121-139. [10.1016/j.dam.2005.02.013]
On the uniform k-partition problems
DELL'OLMO, Paolo;
2001
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.