Hyung Chan An

This person is no longer with EPFL

About
Privacy
Disclaimer

Graph Chatbot

Related publications (5)

Dynamic Facility Location via Exponential Clocks

Ola Nils Anders Svensson, Hyung Chan An, Ashkan Norouzi Fard

The dynamic facility location 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. The generalization lies in that the distance ...

Association for Computing Machinery2017

LP-Based Algorithms For Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

Linear programming (LP) 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 me ...

Society for Industrial and Applied Mathematics2017

Improving Christofides' Algorithm for the s-t Path TSP

Hyung Chan An

We present a deterministic (1+root 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 t ...

Assoc Computing Machinery2015

Centrality of trees for capacitated -center

Ola Nils Anders Svensson, Hyung Chan An, Aditya Bhaskara

We consider the capacitated -center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) locations (called centers) and assign each ...

Springer Heidelberg2015

LP-Based Algorithms for Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

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 methodo ...

IEEE2014

Page 1 of 1