- PrevTheory of Computation 23.09.19
- NextDependable Computing 23.09.19
Research
Lab
Combinatorial OptimizationLab
Prof. Hyung-Chan An
Engineering Hall 4, Room D713
Lab Introduction
Combinatorial Optimization Lab conducts research in the design and analysis of algorithms, particularly for combinatorial optimization problems. Decisions are being made continuously and ubiquitously, ranging from long-term business decisions to split-second scheduling of processes on a computer. The theory of combinatorial optimization enables us to formulate the search of optimal decisions in these situations as concrete mathematical problems. Primary research topics of the lab include the design of approximation algorithms and online algorithms for combinatorial optimization, and the application of these algorithms to optimization problems arising in practice. Approximation algorithms are efficient algorithms that find near-optimal solutions with provable performance guarantees; online algorithms produce their outputs "in real time" without waiting to read the entire input. These algorithms, naturally, can be deployed to address practical optimization problems that can sometimes be intractable. The lab actively engages in international collaboration with outstanding researchers from outside Korea. Its research results are published in prestigious venues in theoretical computer science.
Research field
Algorithm design Combinatorial optimization Approximation algorithms Online algorithms Theoretical computer science Computational applications of optimization techniquesRepresentative Papers
- 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.