Source author record

Hyung-Chan An

Hyung-Chan An appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Other Computer Science

Catalog footprint

What is connected

7works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Online Graph Matching Problems with a Worst-Case Reassignment Budget

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 are revealed to the algorithm one by one, along with its incident edges. The algorithm is required to maintain a matching in the current graph, where the algorithm revises the matching after each vertex arrival by reassigning vertices. Bernstein, Holm, and Rotenberg showed that an online algorithm can maintain a matching of maximum cardinality by performing amortized $O(\log^2 n)$ reassignments per arrival. In this paper, we propose to consider the general question of how requiring a non-amortized hard budget $k$ on the number of reassignments affects the algorithms' performances, under various models from the literature. We show that a simple, widely-used algorithm is a best-possible deterministic algorithm for all these models. For the unweighted maximum-cardinality problem, the algorithm is a $(1-\frac{2}{k+2})$-competitive algorithm, which is the best possible for a deterministic algorithm both under vertex arrivals and edge arrivals. Applied to the load balancing problem, this yields a bifactor online algorithm. For the weighted problem, which is traditionally studied assuming the triangle inequality, we show that the power of reassignment allows us to lift this assumption and the algorithm becomes a $\frac{1}{2}$-competitive algorithm for $k=4$, improving upon the $\frac{1}{3}$ of the previous algorithm without reassignments. We show that this also is a best-possible deterministic algorithm.

preprint2016arXiv

A Formal Approach to Power Optimization in CPSs with Delay-Workload Dependence Awareness

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 design goals that is witnessing such new challenges. The presence of interaction between the cyber and physical components of a CPS leads to dependence between the time delay of a computational task and the amount of workload in the next iteration. We demonstrate that it is essential to take this delay-workload dependence into consideration in order to achieve low power consumption. In this paper, we identify this new 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. In fact, we show that the optimal power consumption is attained in a "steady-state" operation and a simple policy of finding and entering this steady state suffices, which can be quite surprising considering the added complexity of this problem. Finally, we validated the efficiency of our policy with experiments.

preprint2014arXiv

Dynamic Facility Location via Exponential Clocks

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 evolving social/infrastructure networks. The generalization lies in that the distance metric between clients and facilities changes over time. This leads to a trade-off between optimizing the classic objective function and the "stability" of the solution: there is a switching cost charged every time a client changes the facility to which it is connected. While the standard linear program (LP) relaxation for the classic problem naturally extends to this problem, traditional LP-rounding techniques do not, as they are often sensitive to small changes in the metric resulting in frequent switches. We present a new LP-rounding algorithm for facility location problems, which yields the first constant approximation algorithm for the dynamic facility location problem. Our algorithm installs competing exponential clocks on the clients and facilities, and connect every client by the path that repeatedly follows the smallest clock in the neighborhood. The use of exponential clocks gives rise to several properties that distinguish our approach from previous LP-roundings for facility location problems. In particular, we use \emph{no clustering} and we allow clients to connect through paths of \emph{arbitrary lengths}. In fact, the clustering-free nature of our algorithm is crucial for applying our LP-rounding approach to the dynamic problem.

preprint2014arXiv

LP-Based Algorithms for Capacitated Facility Location

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.

preprint2013arXiv

Centrality of Trees for Capacitated k-Center

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 problem: there is a simple tight 2-approximation algorithm for the uncapacitated version whereas the first constant factor approximation algorithm for the general version with capacities was only recently obtained by using an intricate rounding algorithm that achieves an approximation guarantee in the hundreds. Our paper aims to bridge this discrepancy. For the capacitated k-center problem, we give a simple algorithm with a clean analysis that allows us to prove an approximation guarantee of 9. It uses the standard LP relaxation and comes close to settling the integrality gap (after necessary preprocessing), which is narrowed down to either 7, 8 or 9. The algorithm proceeds by first reducing to special tree instances, and then solves such instances optimally. Our concept of tree instances is quite versatile, and applies to natural variants of the capacitated k-center problem for which we also obtain improved algorithms. Finally, we 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.

preprint2011arXiv

Improving Christofides' Algorithm for the s-t Path TSP

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 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 has 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+sqrt(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.