Greedy Packing of Nested Rings: Placement Rules, a Golden Counterexample, and a Tribonacci Floor

기술 요약: 중첩된 고리의 탐욕적 패킹 (Greedy Packing of Nested Rings)

문제 정의
본 논문은 공통된 너비 $w$를 가진 환형(annuli, 고리)을 압축된 컨테이너("팬", pan) 안에 패킹하는 문제를 조사한다. 이때 고리들이 더 큰 고리의 구멍 내부로 중첩되어 들어가는 것을 허용한다. 연구는 두 가지 경쟁적인 목적 함수에 초점을 맞춘다: 배치된 고리의 개수(기수, cardinality)를 최대화하는 것과, 고리와 컨테이너 사이의 총 접촉 면적을 최대화하는 것이다. 이 두 목적 함수는 접촉 면적이 반지름에 대해 초가법적(superadditive)인 반면, 기수는 그렇지 않기 때문에 서로 상충한다.

핵심 질문은 내림차순 탐욕 알고리즘(반지름이 큰 것부터 작은 순서로 처리)이 사용되는 특정 컨테이너 선택 규칙(예: best-fit, worst-fit 또는 random)에 관계없이, 사전식 순서상 최대(lexicographically maximal)인 실행 가능한 고리 집합을 찾는 것이 보장되는 조건을 결정하는 것이다. 이 성질을 **배치 무관성(placement obliviousness)**이라 부른다. 본 논문은 탐욕 알고리즘이 실패하게 만드는 기하학적 및 조합론적 구조를 규명하고, $\rho$(현재 반지름에 대한 이후의 작은 반지름들의 합의 최대 비율)라는 정확한 임계값을 찾고자 한다.

방법론
저자는 엄밀한 기하학적 분석, 조합 최적화, 그리고 형식 검증을 결합한 하이브리드 접근 방식을 채택한다:

1. 기하학적 분석: 논문은 데카르트의 원 정리(Descartes' circle theorem), 벽 접점 원들에 대한 각도 분리 기준, 그리고 "행(row)" 구성(지름을 따라 공을 배치하는 방식)을 포함한 디스크 패킹의 특성을 활용한다. 주요 도구로는 "행 레마(row lemma, Lemma 3)"와 세 개 이상의 디스크를 패킹하는 한계를 정의하는 특정 "포켓(pocket)" 구성(Descartes pockets)이 포함된다.
2. 조합론적 축소: 문제는 기하학적 층(형제 패킹의 실행 가능성)과 조합론적 층(고리의 선택)으로 분해된다. 저자는 초증가 반지름(superincreasing radii) 조건(각 반지름이 이전의 모든 반지름 합보다 큰 경우) 하에서 조합론적 층이 사소해지며, 이 경우 문제가 모든 초가법적 목적 함수에 대해 최적인 선택 탐욕 문제로 축소됨을 증명한다.
3. 교환 논증(Exchange Arguments): 배치 무관성을 증명하기 위해 저자는 "부모 정렬(parent alignment)" 기법을 사용한다. 만약 탐욕적 실행이 최적의 증거(witness)와 다르다면, 가장 큰 불일치 고리의 배치를 교체하고 비워진 공간에 밀려난 작은 고리들을 재삽입함으로써 실행 가능성을 유지하며 새로운 증거를 구성할 수 있음을 보여준다.
4. 형식 검증: 논문은 계산적 검증에 크게 의존한다. 저장소에는 대수적 항등식, 다항식 부등식, 특정 기하학적 인증을 정형화한 122개의 Lean 정리가 포함되어 있다. 매개변수 공간을 탐색하고 반례를 생성하기 위해 수치적 체크가 사용되지만, 저자는 수치적 결과가 서술된 증명이나 형식적 인증을 대체할 수 없음을 명시한다.

주요 기여 및 결과

• 초가법적 이분법 (정리 6): 초증가 반지름 조건 하에서, 선택 탐욕 알고리즘은 모든 양수이며 엄격히 증가하는 초가법적 목적 함수(접촉 면적 포함)에 대해 최적이다. 그러나 초가법적이지 않은 기수의 경우, 초증가 반지름 조건에서도 반례가 존재한다.
• 초증가 반지름 하에서의 배치 무관성 (정리 9): 반지름가 초증가하는 경우, 실행 가능한 컨테이너를 선택하는 모든 규칙은 사전식 순서상 최대인 실행 가능한 집합을 산출한다. 이는 임의의 컨테이너 모양과 치수에서도 성립한다.
• $n=4$에서의 날카로운 경계 (정리 13): 배치 무관성은 세 개의 고리까지는 무조건적으로 성립하지만, 네 개의 고리에서는 실패한다. 논문은 "쌍둥이 인스턴스(twin instances, 정리 14)"를 구축하여, 관측 가능한 상태(컨테이너 용량, 점유물, 유입되는 고리)가 두 가지 서로 다른 문제 인스턴스에 대해 동일함에도 불구하고, 결정적인 고리에 대한 최적의 배치가 서로 다름을 보여준다. 이는 어떤 결정론적 상태 기반 규칙도 보편적으로 성공할 수 없으며, 무작위 규칙 또한 최소 $1/2$의 확률로 실패함을 증명한다.
• 황금 임계값 ($\tau = \phi$):
  • 가법 모델 (Additive Model): 가법 대리 모델의 임계값은 정확히 $\rho = 1$이다.
  • 기하학적 모델 (디스크): 논문은 디스크 컨테이너에 대한 정확한 전역 임계값이 황금비 $\phi \approx 1.618$임을 증명한다.
  • 반례: $\rho = \phi + 3\varepsilon$에서 배치 무관성이 실패하는 네 개의 고리 인스턴스로 구성된 "황금 가족(golden family)"을 구축한다. 이는 트리보나치 상수 $T \approx 1.839$라는 자연스러운 추측을 반박한다.
  • 보편적 보장 (정리 22): $\rho \le \phi$인 평면 디스크의 임의의 유한 인벤토리(inventory)에 대해, 모든 내림차순 탐욕 실행은 사전식 순서상 최대 집합을 반환한다. 이는 독립적인 구멍 반지름을 가진 경우에도 성립한다.
• 트리보나치 바닥 (The Tribonacci Floor): 전역 임계값은 $\phi$이지만, 논문은 강직한(rigid) 기하학적 구성과 관련된 특정 블록된 교환(blocked exchanges) 클래스에서 $\rho$의 하한이 정확히 트리보나치 상수 $T$인 "강직한 하위 집단(rigid subfamily)"의 네 개 고리 반례를 식별한다.
• 정사각형 팬 (Square Pans): 정사각형 컨테이너의 경우, 논문은 특정 대수적 가족으로부터 유도된 상한 $\tau_{\square} \le Y \approx 1.6845$를 설정한다. 정사각형에 대한 정확한 전역 임계값은 여전히 미해결 과제로 남아 있다.
• 차원성: $d \ge 2$인 구형 컨테이너에 대한 결과는 차원 축소 레마를 통해 평면의 사례로부터 전이된다. 배치 무관성은 모든 차원에서 최대 세 개의 고리까지 성립하며, 네 개에서 실패한다. 별도의 논증을 통해 황금 임계값 보장은 모든 차원의 최대 다섯 개 고리까지 확장된다.
• 독립적인 구멍과 면적: 독립적인 구멍 반지름의 경우, $\rho \le \kappa < 1$일 때 정확한 면적 보장 계수가 $\min(1, \kappa^{-2} - 1)$임을 증명하며, 최적성 임계값은 $1/\sqrt{2}$에서 날카롭게 결정된다.

의의 및 주장
본 논문은 휴리스틱 접근법을 넘어 정확한 임계값과 불가능성 결과를 제공함으로써 중첩된 고리의 탐욕적 패킹에 관한 구조적 질문을 해결했다고 주장한다.

• 탐욕의 최적성: $\rho \le \phi$ 조건 하에서, 모든 내림차순 탐욕 실행은 사전식 순서상 최대인 실행 가능한 집합을 반환함(배치 무관성)을 확립한다. 면적 최대화의 경우, 공통 너비와 초증가 반지름 조건이 추가로 요구된다.
• 기하학적 vs 조합론적: 본 연구는 문제의 난이도를 기하학적 층(일반적으로 NP-hard)과 초증가 조건을 통해 해결된 조합론적 층으로 분리한다.
• 추측 반박: 트리보나치 상수가 보편적 임계값이라는 추측을 명시적으로 반박하며, 대신 일반적인 경우의 올바른 경계는 황금비임을 보여주는 동시에, 강직한 사례를 제외한 특정 하위 집단에서의 바닥은 트리보나치 상수임을 밝힌다.
• 엄밀한 검증: 저자는 자신의 결과가 단순한 수치적 또는 휴리스틱 연구와 구별되는, 서술된 기하학적 증명과 Lean을 통한 정형화된 대수적 인증의 결합에 의해 뒷받침됨을 강조한다.

논문은 디스크에 대한 전역 임계값이 $\phi$로 확정되었으나, 정사각형 팬에 대한 정확한 임계값, 강직한 사례를 넘어선 특수 중첩 교환 가족의 정확한 하한, 그리고 전체 입력에 대한 완전한 접근 권한이 허용될 때의 최적 배치를 찾는 계산 복잡도 등에 관한 미해결 과제가 남아 있다고 결론짓는다.