안형찬

Archive of posts with tag '안형찬'

  • Hyung-Chan An (안형찬), LP-based Algorithms for Capacitated Facility Location
    LP-based Algorithms for Capacitated Facility Location
    Hyung-Chan An (안형찬)
    Department of Computer Science, Yonsei University, Seoul
    2016/4/6 Wed 4PM-5PM (Room 3433 of Bldg. E6-1)
    Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to and evolved from algorithms for this problem. Unfortunately, this collection of powerful algorithmic techniques had not yet been applicable to the more general capacitated facility location problem. In fact, all of the known algorithms with good performance guarantees were based on a single technique, local search, and no linear programming relaxation was known to efficiently approximate the problem.
    In this paper, we present a linear programming relaxation with constant integrality gap for capacitated facility location. We demonstrate that the fundamental theories of multi-commodity flows and matchings provide key insights that lead to the strong relaxation. 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.
    Joint work with Mohit Singh and Ola Svensson.
    Tags:

  • Hyung-Chan An, Improving Christofides’ Algorithm for the s-t Path TSP
    Improving Christofides’ Algorithm
    for the s-t Path TSP
    Hyung-Chan An
    EPFL, Lausanne, Switzerland
    2013/05/24 Friday 4PM-5PM
    ROOM 3433
    We present a deterministic (1+√5)/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints; Hoogeveen showed that the natural variant of Christofides’ algorithm is a 5/3-approximation algorithm for this problem, and this asymptotically tight bound in fact had been the best approximation ratio known until now. We modify this algorithm so that it chooses the initial spanning tree based on an optimal solution to the Held-Karp relaxation rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides’ algorithm variant. Our algorithm also proves an upper bound of (1+√5)/2 on the integrality gap of the path-variant Held-Karp relaxation. The techniques devised in this paper can be applied to other optimization problems as well: these applications include improved approximation algorithms and improved LP integrality gap upper bounds for the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP.</p>

    This is joint work with Bobby Kleinberg and David Shmoys.

    Tags:

Monthly Archives