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.
CSI7611 Approximation Algorithms (Yonsei University, Spring 2016)
CS4820 Introduction to Analysis of Algorithms (Cornell University, Summer 2012)
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. Invited to a special issue of SIAM Journal on Computing. [slides (long)] [slides (short)]
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]
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.H.-C. An, R. Kleinberg, and D. B. Shmoys. Improving Christofides' algorithm for the s-t path TSP. In STOC 2012: Proceedings of the 44th ACM Symposium on Theory of Computing, pages 875-886, 2012. Presented in a single-track session of STOC 2012. Finalist of George E. Nicholson 2013 Student Paper Competition. [slides (long)] [slides (short)]
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.H.-C. An, R. D. Kleinberg, and D. B. Shmoys. Approximation algorithms for the bottleneck asymmetric traveling salesman problem. In APPROX 2010: Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 1-11, 2010.
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.
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.H.-C. An, A polynomial-time algorithm to find optimal path decompositions of trees. Journal of Korea Information Science Society, 34(5):195-201, 2007.
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| log2 |V|)-time algorithm for the case where the input tree is unit-weighted.