9 citations · 14 across the 4 of their papers we have counts for
5 papers
Making Three Out of Two: Three-Way Online Correlated Selection
Yongho Shin, Hyung-Chan An
Two-way online correlated selection (two-way OCS) is an online algorithm that, at each timestep, takes a pair of elements from the ground set and irrevocably chooses one of the two…
Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
Hyung-Chan An, Robert Kleinberg, David B. Shmoys
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…
Online Graph Matching Problems with a Worst-Case Reassignment Budget
Yongho Shin, Kangsan Kim, Seungmin Lee +1
In the online bipartite matching with reassignments problem, an algorithm is initially given only one side of the vertex set of a bipartite graph; the vertices on the other side ar…
Constant-Factor Approximation Algorithms for Parity-Constrained Facility Location Problems
Kangsan Kim, Yongho Shin, Hyung-Chan An
Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the probl…
Centrality of Trees for Capacitated k-Center
Hyung-Chan An, Aditya Bhaskara, Ola Svensson
There is a large discrepancy in our understanding of uncapacitated and capacitated versions of network location problems. This is perhaps best illustrated by the classical k-center…