췐링 판(범성림) 연구실

본 논문은 색상 상관 클러스터링(CCC) 문제에 대해 1.64-근사 알고리즘을 제시하여 기존의 2.15 근사율을 크게 개선합니다. 클러스터 LP 프레임워크를 색상 설정으로 확장한 색상 클러스터 LP 완화와 클러스터 기반 및 탐욕적 피벗 전략을 활용한 반올림 알고리즘을 통해 표준 LP의 정수성 갭 2를 극복합니다.

본 논문은 학습 증강 k-클러스터링을 일반 메트릭으로 확장하여 그래프 구조 및 비유클리드 도메인에 적용 가능하게 합니다. 클러스터 크기 제약을 완화하여 불균형 데이터셋에 대한 유연성을 제공하며, 지수 시간 가설 하에서 (1+α)-근사를 달성하려면 Ω(k/α)개의 쿼리가 필요함을 증명합니다.

본 연구는 대규모 언어모델(LLM)을 활용하여 조합 최적화 문제 인스턴스와 휴리스틱 솔버를 공동 진화시키는 EALG 프레임워크를 제안합니다. 돌연변이 기반 적대적 접근법으로 점진적으로 어려운 문제를 생성하면서 동시에 적응형 알고리즘을 합성합니다. 실험 결과 EALG는 기존 벤치마크보다 훨씬 어려운 인스턴스를 생성하며, 합성된 솔버는 다양한 조합 최적화 작업에서 효과적으로 일반화합니다.

본 논문은 상관 클러스터링의 두 가지 일반화 문제인 색상 상관 클러스터링과 의사거리 가중 상관 클러스터링에 대한 개선된 근사 알고리즘을 제시합니다. LP 기반 피벗팅 기법과 문제별 반올림 함수를 활용하여, 의사거리 가중 문제에서 10/3-근사 알고리즘을, 색상 상관 클러스터링에서 근사비를 2.5에서 2.15로 개선하였습니다.

본 논문은 가중 무방향 그래프에서 차등 프라이버시를 보장하면서 모든 쌍의 거리를 근사하는 문제를 연구합니다. 재귀적으로 분리 가능한 그래프 클래스에 대해 이진 트리 메커니즘을 일반화한 알고리즘을 제안하며, K_h-마이너-프리 그래프에서 Õ(h(nW)^{1/3})의 가법 오차, 격자 그래프에서 Õ(n^{1/4}√W)의 가법 오차를 달성합니다.