On the completability of orthogonal Latin rectangles

Gautam Appa Reinhardt Euler 1, * Anastasia Kouvela Dimitris Magos Ioannis Mourtos
* Auteur correspondant
1 Lab-STICC_UBO_CACS_MOCS
UBO - Université de Brest, Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
Abstract : We address the problem of completability for 2-row orthogonal Latin rectangles (OLR2). The approach is to identify all incomplete pairs of 2-row Latin rectangles that are not completable to an OLR2 and are minimal with respect to this property; i.e., we characterize all circuits of the independence system associated with OLR2. Since there can be no polytime algorithm generating the clutter of circuits of an arbitrary independence system, our work adds to the few such cases for which that clutter is fully described. The result has a direct polyhedral implication; it gives rise to inequalities that are valid for the polytope associated with orthogonal Latin squares and thus planar multi-dimensional assignment. A complexity result is also at hand: completing an incomplete set of (n-1) MOLR2 is NP-complete.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2016, 339 (6), pp.1771-1794
Liste complète des métadonnées

http://hal.univ-brest.fr/hal-01220159
Contributeur : Reinhardt Euler <>
Soumis le : dimanche 25 octobre 2015 - 14:16:31
Dernière modification le : mardi 16 janvier 2018 - 15:54:23

Identifiants

  • HAL Id : hal-01220159, version 1

Citation

Gautam Appa, Reinhardt Euler, Anastasia Kouvela, Dimitris Magos, Ioannis Mourtos. On the completability of orthogonal Latin rectangles. Discrete Mathematics, Elsevier, 2016, 339 (6), pp.1771-1794. 〈hal-01220159〉

Partager

Métriques

Consultations de la notice

100