**I am looking for motivated students who are interested in pursing a graduate degree or internship in the area of approximation algorithms and combinatorial optimization. If interested, please contact me via e-mail.**

Yonsei University

50 Yonsei-ro, Seodaemun-gu

Seoul 03722

Korea (Republic of)

CSI7611 Approximation Algorithms (Yonsei University, Spring 2016)

CS4820 Introduction to Analysis of Algorithms (Cornell University, Summer 2012)

- Approximation algorithms
- Others

H.-C. An, A. Norouzi-Fard, and O. Svensson. Dynamic facility location via exponential clocks. In SODA 2015: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 708-721, 2015.

We present a new LP-rounding algorithm for facility location problems, which yields the first constant approximation algorithm for the dynamic facility location problem. This problem is a generalization of the classic facility location problem, proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. Our algorithm, based on competing exponential clocks, exhibits several properties that distinguish our approach from previous LP-roundings for facility location problems. We demonstrate that these properties enable us to apply our new algorithm to the dynamic problem.

H.-C. An, M. Singh, and O. Svensson. LP-based algorithms for capacitated facility location. In FOCS 2014: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, pages 256-265, 2014.(Journal version) H.-C. An, M. Singh, and O. Svensson. LP-based algorithms for capacitated facility location. SIAM Journal on Computing,

Linear programming (LP) has played a key role in the study of algorithms for combinatorial optimization problems. In particular, a variety of LP-based methodologies have been applied to and evolved from the uncapacitated facility location problem. Unfortunately, this collection of powerful techniques had not yet been applicable to the more general capacitated facility location problem. In this paper, we present a linear programming relaxation with constant integrality gap for capacitated facility location. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding.

H.-C. An, A. Bhaskara, C. Chekuri, S. Gupta, V. Madan, and O. Svensson. Centrality of trees for capacitated k-center. In IPCO 2014: Proceedings of the 17th Conference on Integer Programming and Combinatorial Optimization, pages 52-63, 2014. This paper merges two independent works, one by the 1st, 2nd & 6th authors and the other by the 3rd, 4th & 5th. [slides](Journal version) H.-C. An, A. Bhaskara, C. Chekuri, S. Gupta, V. Madan, and O. Svensson. Centrality of trees for capacitated k-center. Mathematical Programming Series B, 154(1-2), pages 29-53, 2015.

There is a large discrepancy in our understanding of uncapacitated and capacitated versions of network location problems. This paper aims to bridge this discrepancy, by presenting a simple algorithm for the capacitated *k*-center problem. Our algorithm has a clean analysis that allows us to prove an improved approximation ratio of 9, narrowing down the integrality gap of the standard LP relaxation to either 7, 8, or 9. We present extensions of our techniques to related problems, and also give evidence to show that more powerful preprocessing could lead to better algorithms, by giving an approximation algorithm that beats the integrality gap for instances where all non-zero capacities are uniform.

(Journal version) H.-C. An, R. Kleinberg, and D. B. Shmoys. Improving Christofides' algorithm for the s-t path TSP. Journal of the ACM, 62(5), pages 34:1-34:28, 2015.

We present a deterministic (1+√5)/2-approximation algorithm for the *s*-*t* path TSP for an arbitrary metric. Given a symmetric metric cost between *n* vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints. The present result surpasses the 20-year-old barrier of 5/3 originating from Hoogeveen's analysis of the natural path-variant of Christofides' algorithm. The present techniques can be applied to other optimization problems as well: these applications include the prize-collecting *s*-*t* path problem and the unit-weight graphical metric *s*-*t* path TSP.

We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between *n* vertices, the problem is to find a Hamiltonian cycle that minimizes its *bottleneck* (or maximum-length edge) cost. We achieve an *O*(log *n* / log log *n*) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on the result of Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi to obtain this guarantee.

H.-C. An, H. Yang, and S. Ha. A formal approach to power optimization in CPSs with delay-workload dependence awareness. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,

The interaction between the cyber and physical components of CPSs induces delay-workload dependence, creating the unique challenge of power optimization with delay-workload dependence awareness. In this paper, we identify this challenge and present the first formal and comprehensive model to enable rigorous investigations on this topic. We propose a simple power management policy, and show that this policy achieves a best possible notion of optimality. We also experimentally validate the efficiency of our policy.

H.-C. An, R. Kleinberg. A diameter-revealing proof of the Bondy-Lovász Lemma. Available online at http://arxiv.org/abs/1111.6561, 2011.We present a strengthened version of a lemma due to Bondy and Lovász. This lemma establishes the connectivity of a certain graph whose nodes correspond to the spanning trees of a 2-vertex-connected graph, and implies the *k*=2 case of the Győri-Lovász Theorem on partitioning of *k*-vertex-connected graphs. Our strengthened version constructively proves an asymptotically tight *O*(|*V*|^{2}) bound on the worst-case diameter of this graph of spanning trees.

We present an *O*(|*V*|^{2})-time algorithm to find a minimum terminal path decomposition of a tree. A minimum terminal path decomposition is a partition of a tree into edge-disjoint terminal-to-terminal paths that minimizes the weight of the longest path. Additionally, we give an *O*(|*V*| log^{2} |*V*|)-time algorithm for the case where the input tree is unit-weighted.

- Finalist, George E. Nicholson 2013 Student Paper Competition. INFORMS, 2013.
- Departmental Best Thesis Award, Department of Computer Science, Cornell University, 2012.
- Excellence Award (최우수상), Seoul National University, 2006.
- Silver Medal (ranked 8th; recognized as Asian Champions), ACM International Collegiate Programming Contest World Finals, 2001. As a team representing Seoul National University.
- Bronze Medal, International Olympiad in Informatics, 1997.
- Bronze Medal, International Olympiad in Informatics, 1996.