안형찬 연구실

본 논문은 계층적 상관 클러스터링 문제를 다루며, 여러 계층의 엣지 가중치와 레이블 정보가 주어질 때 계층 구조를 유지하면서 불일치를 최소화하는 분할을 계산합니다. LP-반올림을 위한 새로운 패러다임을 제시하여 근사 비율을 25.7846으로 개선하였으며, 이는 초메트릭 거리 피팅 문제에도 적용됩니다.

본 논문은 다중 옵션 스키 렌탈 문제에 대한 개선된 학습 증강 알고리즘을 제시합니다. 결정론적 알고리즘의 최적 성능을 증명하는 일치하는 하한을 제공하며, 결정론적 알고리즘의 하한을 초과하는 첫 번째 무작위 학습 증강 알고리즘을 제시합니다.

본 논문은 지능형 교통 시스템의 계산 요구를 충족하기 위해 다중 프로세서 시스템의 산발적 작업 그래프에 맞춘 실시간 스케줄링 기법을 제시합니다. 제안 방법은 마감 기한 기반 접근과 달리 런타임 불확실성 하에서 시스템 유틸리티에 대한 작업의 기여도(가치)를 우선시하며, 실행 가능성 인식 가치 밀도 메트릭을 통해 동적으로 작업을 스케줄합니다. 1, 2, 4개 프로세서에서의 시뮬레이션 결과, 제안 방법은 특히 고부하 시나리오나 제한된 처리 자원 환경에서 획득한 총 가치를 크게 향상시킵니다.

본 논문은 연결된 최소 반경 합 문제를 연구합니다. 시설의 부분집합을 개방하고 모든 클라이언트를 할당한 후 개방된 시설들을 Steiner 트리로 연결하여 할당 거리와 트리 비용의 가중 합을 최소화합니다. LP 완화를 기반으로 한 신중한 클러스터링 절차와 비용 필터링 기법을 통해 5.542-근사 알고리즘을 제시합니다.