The Packing Chromatic Number of the Infinite Square Grid is 15
Created by
Haebom
저자
Bernardo Subercaseaux, Marijn J. H. Heule
개요
무한대 정사각형 격자의 패킹 채색 수를 결정하는 것은 2002년 제시된 이후 미해결 문제였습니다. 본 논문은 이 문제에 대한 답으로 패킹 채색 수가 15임을 증명합니다. 이는 기존 최고 성능 방법보다 약 100배 향상된 결과이며, 새로운 제약 조건 인코딩 및 대칭성 깨기 방법을 통해 달성되었습니다. 새로운 방법들의 정확성 검증을 위해 불만족 증명을 이용하여 신뢰할 수 있는 핵심 부분을 직접 인코딩의 정확성으로 축소하였습니다.
시사점, 한계점
•
시사점: 무한대 정사각형 격자의 패킹 채색 수 문제를 15라는 값으로 해결, 기존 알고리즘 성능을 크게 향상시키는 새로운 제약 조건 인코딩 및 대칭성 깨기 방법 제시.
•
한계점: 새로운 방법들의 복잡성으로 인해, 방법의 정확성 검증에 대한 의존성이 존재 (직접 인코딩의 정확성에 의존).