Algoritmos de Aproximação para o Problema de Extensão de Quadrados Latinos Diagonais
Resumo
Neste trabalho, estudamos o problema de extensão de quadrados latinos restrito a quadrados latinos diagonais. Para tal problema, apresentamos três algoritmos de aproximação adaptados da literatura: um algoritmo guloso, um algoritmo baseado em emparelhamento, e uma busca local.Referências
Chlebík, M. e Chlebíková, J. (2006). Complexity of approximating bounded variants of optimization problems. Theoretical Computer Science, 354(3):320–338.
Colbourn, C. J. (1984). The complexity of completing partial latin squares. Discrete Applied Mathematics, 8(1):25–30.
Cygan, M. (2013). Improved approximation for 3-dimensional matching via bounded pathwidth local search. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 509–518, Los Alamitos, CA, USA. IEEE Computer Society.
Fürer, M. e Yu, H. (2014). Approximating the k-set packing problem by local improvements. In Fouilhoux, P., Gouveia, L. E. N., Mahjoub, A. R., e Paschos, V. T., editors, Combinatorial Optimization, pages 408–420, Cham. Springer International Publishing.
Garey, M. R. e Johnson, D. S. (1979). Computers and intractability, volume 174. freeman San Francisco.
Gomes, C. P., Regis, R. G., e Shmoys, D. B. (2004). An improved approximation algorithm for the partial latin square extension problem. Operations Research Letters, 32(5):479–484.
Hajirasouliha, I., Jowhari, H., Kumar, R., e Sundaram, R. (2007). On completing latin squares. In Thomas, W. e Weil, P., editors, STACS 2007, pages 524–535, Berlin, Heidelberg. Springer Berlin Heidelberg.
Haraguchi, K. e Ono, H. (2015). How simple algorithms can solve latin square completion-type puzzles approximately. Journal of Information Processing, 23(3):276–283.
Hilton, A. J. W. (1973). On double diagonal and cross latin squares. Journal of the London Mathematical Society, s2-6(4):679–689.
Hilton, A. J. W. (1974). Some simple constructions for double diagonal latin squares. Sankhyā: The Indian Journal of Statistics, Series B, pages 215–229.
Holyer, I. (1981). The NP-completeness of some edge-partition problems. SIAM Journal on Computing, 10(4):713–717.
Keedwell, A. D. e Dénes, J. (2015). Latin squares and their applications. Elsevier.
Kumar, S. R., Russell, A., e Sundaram, R. (1999). Approximating latin square extensions. Algorithmica, 24(2):128–138.
Colbourn, C. J. (1984). The complexity of completing partial latin squares. Discrete Applied Mathematics, 8(1):25–30.
Cygan, M. (2013). Improved approximation for 3-dimensional matching via bounded pathwidth local search. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 509–518, Los Alamitos, CA, USA. IEEE Computer Society.
Fürer, M. e Yu, H. (2014). Approximating the k-set packing problem by local improvements. In Fouilhoux, P., Gouveia, L. E. N., Mahjoub, A. R., e Paschos, V. T., editors, Combinatorial Optimization, pages 408–420, Cham. Springer International Publishing.
Garey, M. R. e Johnson, D. S. (1979). Computers and intractability, volume 174. freeman San Francisco.
Gomes, C. P., Regis, R. G., e Shmoys, D. B. (2004). An improved approximation algorithm for the partial latin square extension problem. Operations Research Letters, 32(5):479–484.
Hajirasouliha, I., Jowhari, H., Kumar, R., e Sundaram, R. (2007). On completing latin squares. In Thomas, W. e Weil, P., editors, STACS 2007, pages 524–535, Berlin, Heidelberg. Springer Berlin Heidelberg.
Haraguchi, K. e Ono, H. (2015). How simple algorithms can solve latin square completion-type puzzles approximately. Journal of Information Processing, 23(3):276–283.
Hilton, A. J. W. (1973). On double diagonal and cross latin squares. Journal of the London Mathematical Society, s2-6(4):679–689.
Hilton, A. J. W. (1974). Some simple constructions for double diagonal latin squares. Sankhyā: The Indian Journal of Statistics, Series B, pages 215–229.
Holyer, I. (1981). The NP-completeness of some edge-partition problems. SIAM Journal on Computing, 10(4):713–717.
Keedwell, A. D. e Dénes, J. (2015). Latin squares and their applications. Elsevier.
Kumar, S. R., Russell, A., e Sundaram, R. (1999). Approximating latin square extensions. Algorithmica, 24(2):128–138.
Publicado
06/08/2023
Como Citar
CHAGAS, Vítor G.; MIYAZAWA, Flávio K..
Algoritmos de Aproximação para o Problema de Extensão de Quadrados Latinos Diagonais. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 119-123.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230101.
