|
|||||
|
|
On uniform k-partition problems |
|
| Authors: | Paolo Dell&#x Olmo, Pierre Hansen, Stefano Pallottino,Giovanni Storchi |
| Affiliation: | aDipartimento di Statistica, Probabilità e Statistiche Applicate, Università di Roma“La Sapienza”, P.le Aldo Moro 5, 00185 Roma, Italy bGERAD and École des Hautes Etudes Commerciales, 3000, Chemin de la Côte-Sainte-Catherine Montréal, Qué., Canada H3T 2A7 cDipartimento di Informatica, Università di Pisa, Via F. Buonarroti 2, 56127 Pisa, Italy dDipartimento di Statistica, Probabilità e Statistiche Applicate, Università di Roma “La Sapienza”, P.le Aldo Moro 5, 00185 Roma, Italy |
| 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. |
| Keywords: | Partition Matrix permutation Algorithms Complexity |
| 本文献已被 ScienceDirect 等数据库收录！ | |