연구
연구실
최적화및응용연구실 지능형 데이터 컴퓨팅
Combinatorial Optimization Lab
담당교수 안형찬
제4공학관 D713호
연구실 소개
최적화및응용 연구실에서는 알고리즘 설계 및 분석 기법을 조합 최적화 문제 중심으로 연구합니다. 이 세상은 밀리초 단위의 CPU 스케줄링에서부터 수십 년을 좌우하는 장기 정책에 이르기까지 다양한 형태의 선택과 결정으로 이루어져 있는데, 조합 최적화 이론은 여러 선택지 중 최적의 선택지를 찾아내는 일을 구체적이고 명확하게 정의된 수학적 문제로 표현해 줍니다. 최적화및응용 연구실에서는 짧은 시간에 최적에 가까운 해를 찾아내는 근사 알고리즘과, 입력의 전체를 보기 전에 출력을 도출하는 온라인 알고리즘을 특히 집중적으로 연구하고 있습니다. 이들 알고리즘을 통해 현실에서 발생하는 난해한 최적화 문제들을 해결할 수 있으므로, 최적화 알고리즘의 응용 또한 함께 연구하고 있습니다. 최적화및응용 연구실은 해외의 우수한 연구자들과 활발한 국제 공동연구를 펼치고 있으며, 연구 결과를 이론 컴퓨터과학 분야의 권위있는 학술지 및 학술대회에 출판하고 있습니다.
연구분야
알고리즘 설계 조합 최적화 근사 알고리즘 온라인 알고리즘 이론 컴퓨터과학 최적화 기법 응용대표 논문
- Shin, Y., & An, H.-C. (2021). Making Three out of Two: Three-Way Online Correlated Selection. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021).
- Kim, K., Shin, Y., & An, H.-C. (2020). Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem. In 31st International Symposium on Algorithms and Computation (ISAAC 2020).
- An, H.-C., Singh, M., & Svensson, O. (2017). LP-based algorithms for capacitated facility location. SIAM Journal on Computing, 46(1), 272-306.