9 citations · 26 across the 13 of their papers we have counts for
13 papers
Improved Algorithms for Bounded-Degree (Subset) Traveling Salesman Problems
Jongseo Lee, Jaehyeok Kwak, Hyung-Chan An
We present improved algorithms for several bounded-degree traveling salesman problems. In the bounded-degree traveling salesman path problem (BDTSPP), given a weighted graph G=(V,E…
Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis
Yongho Shin, Changyeol Lee, Gukryeol Lee +1
In this paper, we present improved learning-augmented algorithms for the multi-option ski rental problem. Learning-augmented algorithms take ML predictions as an added part of the…
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…
A Formal Approach to Power Optimization in CPSs with Delay-Workload Dependence Awareness
Hyung-Chan An, Hoeseok Yang, Soonhoi Ha
The design of cyber-physical systems (CPSs) faces various new challenges that are unheard of in the design of classical real-time systems. Power optimization is one of the major de…
Dynamic Facility Location via Exponential Clocks
Hyung-Chan An, Ashkan Norouzi-Fard, Ola Svensson
The \emph{dynamic facility location problem} is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evo…
LP-Based Algorithms for Capacitated Facility Location
Hyung-Chan An, Mohit Singh, Ola Svensson
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 t…
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…
Improving Christofides' Algorithm for the s-t Path TSP
Hyung-Chan An, Robert Kleinberg, David B. Shmoys
We present a deterministic (1+sqrt(5))/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecifie…
A Diameter-Revealing Proof of the Bondy-Lovász Lemma
Hyung-Chan An, Robert Kleinberg
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…
LP-Based Approximation Algorithms for Traveling Salesman Path Problems
Hyung-Chan An, David B. Shmoys
This paper has been merged into 1110.4604.