|
|||||
|
|
On the orthogonal Latin squares polytope |
|
| Authors: | G. Appa I. Mourtos J.C.M. Janssen |
| Affiliation: | a Operational Research Department, London School of Economics and Political Science, Houghton Street, London WC2A2AE, UK b Department of Informatics, Technological Educational Institute (T.E.I.) of Athens, Ag. Spyridonos Str., 12210 Egaleo, Athens, Greece c Department of Economics, University of Patras, Rio 26500, Patras, Greece d Department of Mathematics and Statistics, Dalhousie University, Halifax NS, Canada B3H 3J5 |
| Abstract: | Since 1782, when Euler addressed the question of existence of a pair of orthogonal Latin squares (OLS) by stating his famous conjecture, these structures have remained an active area of research. In this paper, we examine the polyhedral aspects of OLS. In particular, we establish the dimension of the OLS polytope, describe all cliques of the underlying intersection graph and categorize them into three classes. Two of these classes are shown to induce facet-defining inequalities of Chvátal rank two. For each such class, we provide a polynomial separation algorithm of the lowest possible complexity. |
| Keywords: | Orthogonal Latin squares Polyhedral combinatorics Clique facets |
| 本文献已被 ScienceDirect 等数据库收录！ | |