×

On the completability of incomplete orthogonal Latin rectangles. (English) Zbl 1333.05043

Summary: We address the problem of completability for 2-row orthogonal Latin rectangles \((\mathrm{OLR2})\). Our approach is to identify all pairs of incomplete 2-row Latin rectangles that are not completable to an \(\mathrm{OLR2}\) and are minimal with respect to this property; i.e., we characterize all circuits of the independence system associated with \(\mathrm{OLR2}\). Since there can be no polytime algorithm generating the clutter of circuits of an arbitrary independence system, our work adds to the few independence systems 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 a set of \((n - 1)\) incomplete \(\mathrm{MOLR2}\) is NP-complete.

MSC:

05B15 Orthogonal arrays, Latin squares, Room squares
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Appa, G.; Magos, D.; Mourtos, I., On multi-index assignment polytopes, Linear Algebra Appl., 416, 224-241 (2006) · Zbl 1102.90038
[2] Colbourn, C. J., The complexity of completing partial latin squares, Discrete Appl. Math., 8, 25-30 (1984) · Zbl 0538.05013
[3] Djordjevic, I. B.; Vasic, B., Combinatorial constructions of optical orthogonal codes for OCDMA systems, IEEE Commun. Lett., 8, 6, 391-393 (2004)
[5] Euler, R., On the completability of incomplete Latin squares, European J. Combin., 31, 2, 535-552 (2010) · Zbl 1201.05016
[6] Euler, R.; Oleksik, P., When is an incomplete 3xn latin rectangle completable?, Discuss. Math. Graph Theory, 33, 1, 57-69 (2013) · Zbl 1290.05040
[7] Gessel, I. M., Counting Latin rectangles, Bull. Amer. Math. Soc., 16, 79-82 (1987) · Zbl 0617.05015
[8] Hall, M., An existence theorem for Latin squares, Bull. Amer. Math. Soc., 51, 387-388 (1945) · Zbl 0060.02801
[9] Kou, Y.; Lin, S.; Fossorier, M., Low-density parity-check codes based on finite geometries: A discovery and new results, IEEE Trans. Inform. Theory, 47, 2711-2736 (2001) · Zbl 1015.94015
[10] Kurtas, E.; Vasic, B.; Kuznetsov, A., Design and analysis of low-density parity-check codes for applications to perpendicular recording channels, (Wiley Encyclopedia of Telecommunications (2003), J. Wiley & Sons: J. Wiley & Sons New York)
[11] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Generating all maximal independent sets: NP-hardness and polynomial-time algorithms, SIAM J. Comput., 9, 558-565 (1980) · Zbl 0445.68054
[12] Laywine, C. F.; Mullen, G. L., Discrete Mathematics Using Latin Squares (1998), J. Wiley & Sons: J. Wiley & Sons New York · Zbl 0957.05002
[13] McKay, B. D.; Wanless, I. M., On the number of Latin squares, Ann. Comb., 9 (2005), 335-326 · Zbl 1073.05013
[14] Padberg, M. W., On the facial structure of set packing polyhedra, Math. Program., 5, 199-215 (1973) · Zbl 0272.90041
[15] Popovski, P.; Yomo, H., The antipackets can increase the achievable throughput of a wireless multihop network, IEEE Int. Conf. Commun. (2006)
[16] Ryser, H. J., Combinatorial Mathematics (1963), Mathematical Association of America · Zbl 0112.24806
[17] Salehi, J. A., Code division multiple-access techniques in optical fiber networks. I. Fundamental principles, IEEE Trans. Commun., 37, 824-833 (1989)
[18] Stones, D. S., The many formulae for the number of Latin rectangles, Electron. J. Combin., 17, 1, 46 (2010) · Zbl 1193.05042
[19] Stork, F.; Uetz, M., On the generation of circuits and minimal forbiden sets, Math. Program., 102, 185-203 (2005)
[20] Vasic, B.; Kurtas, E. M.; Kuznetsov, A. V., LDPC codes based on mutually orthogonal latin rectangles and their application in perpendicular magnetic recording, IEEE Trans. Magn., 38, 5, 2346-2348 (2002)
[22] Zhang, S.; Liew, S. C.; Lam, P. P., Hot topic: Physical-layer network coding, (The Annual International Conference on Mobile Computing and Networking (2006)), 358-365
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.