Publications

^(*): Authors are listed in alphabetical order.

2026

1. Optimal Learning-Augmented Algorithm for Online Bidding

   Changyeol Lee, Dahoon Lee, Jongseo Lee, Yongho Shin, and Changki Yun  ^(*)

   In The Fortieth Annual Conference on Neural Information Processing Systems (NeurIPS, to appear), Dec, 2026

   [Abstract] [arXiv]

   Recent advances in machine learning have spurred significant interest in learning-augmented algorithms, particularly for online optimization. A growing body of work has studied online bidding in this framework, aiming to characterize the trade-off between robustness and consistency. While this trade-off is fully understood for deterministic algorithms, a gap between upper and lower bounds remains in the randomized setting. In this paper, we close this gap by presenting a Pareto-optimal randomized learning-augmented algorithm for this problem. Our approach introduces the notion of a bidding profile, a novel framework for representing the distribution over bids generated by an algorithm. We show that any bidding algorithm can be reduced, without loss of generality, to one driven by a bidding profile, and we characterize the optimal profile via a system of delayed differential equations. Finally, we demonstrate the broader applicability of our approach by extending it to the linear search problem, yielding a significant improvement over prior learning-augmented algorithms for linear search.

2. Ultrametric Violation Distance with Upper and Lower Bounds: A 4-Approximation

   Changyeol Lee, and Hyung-Chan An

   In 37th International Symposium on Algorithms and Computation (ISAAC, to appear), Dec, 2026

   [Abstract]

   We study the ultrametric violation distance problem with upper and lower bounds. In this problem, the input consists of a set of points together with a distance, an upper bound, and a lower bound for each pair of points. The goal is to find an ultrametric that satisfies all bounds and minimizes the violation distance, defined as the number of pairs whose output distance differs from the input. Previously, approximation algorithms for this problem were known only for special cases, such as the unconstrained version and the version with only lower bounds. When both upper and lower bounds are present, however, no algorithmic results were known beyond feasibility testing. In this paper, we give the first approximation algorithm for the general problem, achieving an approximation ratio of 4. This immediately improves the best approximation ratio of 5 previously known for the unconstrained version, first obtained by Charikar and Gao (SODA 2024) and subsequently by An, Kao, Lee, and Lee (FOCS 2025). Our result also improves the best approximation ratio of 62 previously known for the version with lower bounds, due to Das, Kipouridis, and Spoerhase (SOSA 2026). As a further consequence, via Das et al.’s reduction, our result yields 20-approximation algorithms for the unconstrained tree metric violation distance problem and its lower-bounded version, improving the previous ratios 30 and 310, respectively.

3. Approximating (Weighted) Chromatic Correlation Clustering via Cluster LP

   Fateme Abbasi, Hyung-Chan An, Jarosław Byrka,  Changyeol Lee, and Yongho Shin  ^(*)

   In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), vol. 392, pp. 13:1–13:20, Sep, 2026

   [Abstract] [arXiv] [DOI]

   Correlation Clustering is a fundamental clustering problem, and there has been a line of work on improving the approximation ratio for this problem in recent years. A key algorithmic component in these works is the cluster LP. Chromatic Correlation Clustering is an interesting generalization that has also been intensively studied. In light of success of the cluster LP in Correlation Clustering, it would be an interesting question whether the cluster LP can be used in Chromatic Correlation Clustering. We answer this question with affirmatives by presenting a (2+ε)-approximation algorithm for Chromatic Correlation Clustering using a chromatic cluster LP.

2025

1. Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics

   Hyung-Chan An, Mong-Jen Kao,  Changyeol Lee, and Mu-Ting Lee ^(*)

   In IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1144-1169, Dec, 2025

   [Abstract] [PDF] [Slides] [Talk] [DOI]

   We consider the classic correlation clustering problem in the hierarchical setting. Given a complete graph G=(V,E) and ℓ layers of input information, where the input of each layer consists of a nonnegative weight and a labeling of the edges with either + or -, this problem seeks to compute for each layer a partition of V such that the partition for any non-top layer subdivides the partition in the upper-layer and the weighted number of disagreements over the layers is minimized. Hierarchical correlation clustering is a natural formulation of the classic problem of fitting distances by ultrametrics, which is further known as numerical taxonomy in the literature. While single-layer correlation clustering received wide attention since it was introduced and major progress evolved in the past three years, few is known for this problem in the hierarchical setting. The lack of understanding and adequate tools is reflected in the large approximation ratio known for this problem originating from 2021. In this work we make both conceptual and technical contributions towards the hierarchical clustering problem. We present a simple paradigm that greatly facilitates LP-rounding in hierarchical clustering, illustrated with an algorithm providing a significantly improved approximation guarantee of 25.7846 for the hierarchical correlation clustering problem. Our techniques reveal surprising new properties of the formulation presented and subsequently used in previous works for hierarchical clustering over the past two decades. This provides an interpretation on the core problem in hierarchical clustering as the problem of finding cuts with prescribed properties regarding average distances. We further illustrate this perspective by showing that a direct application of the techniques gives a simple alternative to the state-of-the-art result for the ultrametric violation distance problem.

2. Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach

   Changyeol Lee, Yongho Shin, and Hyung-Chan An

   In The Thirty-ninth Annual Conference on Neural Information Processing Systems (NeurIPS), vol. 38, pp. 78913–78945, Dec, 2025

   [Abstract] [PDF] [Poster] [Slides] [DOI]

   Clustering is a fundamental task in both machine learning and data mining. Among various methods, edge-colored clustering (ECC) has emerged as a useful approach for handling categorical data. Given a hypergraph with (hyper)edges labeled by colors, ECC aims to assign vertex colors to minimize the number of edges where the vertex color differs from the edge’s color. However, traditional ECC has inherent limitations, as it enforces a nonoverlapping and exhaustive clustering. To tackle these limitations, three versions of ECC have been studied: Local ECC and Global ECC, which allow overlapping clusters, and Robust ECC, which accounts for vertex outliers. For these problems, both linear programming (LP) rounding algorithms and greedy combinatorial algorithms have been proposed. While these LP-rounding algorithms provide high-quality solutions, they demand substantial computation time; the greedy algorithms, on the other hand, run very fast but often compromise solution quality. In this paper, we present a family of algorithms that combines the strengths of LP with the computational efficiency of combinatorial algorithms. Both experimental and theoretical analyses show that our algorithms efficiently produce high-quality solutions for all three problems: Local, Global, and Robust ECC. We complement our algorithmic contributions with complexity-theoretic inapproximability results and integrality gap bounds, which suggest that significant theoretical improvements are unlikely. Our results also answer two open questions previously raised in the literature.

3. Improved Learning-Augmented Algorithms and (Tight) Lower Bounds for Multi-Option Ski Rental Problem

   Yongho Shin,  Changyeol Lee, Gukryeol Lee, and Hyung-Chan An

   ACM Transactions on Algorithms (TALG), vol. 22, Nov, 2025

   [Abstract] [URL]

   We present improved learning-augmented algorithms for the multi-option ski rental problem. Learning-augmented algorithms take machine learning (ML) predictions as an added part of the input and incorporate these predictions in solving the given problem. Due to their unique strength that combines the power of ML predictions with provable performance guarantees, they have been extensively studied in the context of online optimization problems. While the multi-option ski rental problem provides a natural generalization of the classical rent-or-buy variant, only deterministic algorithms for this problem were previously known, with or without learning augmentation.In this article, we first present that a very simple modification to a previously known algorithm suffices to give an improved deterministic learning-augmented algorithm. In fact, we prove that this algorithm has the best-possible performance of a deterministic algorithm by giving a matching lower bound. Then we present the first randomized learning-augmented algorithm, which surpasses the lower bound of deterministic algorithms; this learning-augmented algorithm is based on a new best-possible randomized competitive algorithm. These results are complemented by lower bounds for randomized competitive/learning-augmented algorithms.

2023

1. Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis

   Yongho Shin,  Changyeol Lee, Gukryeol Lee, and Hyung-Chan An

   In Proceedings of the 40th International Conference on Machine Learning (ICML), vol. 202, pp. 31539–31561, 23–29 jul, 2023

   [Abstract] [PDF] [Poster] [Slides] [URL]

   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 input and incorporates these predictions in solving the given problem. Due to their unique strength that combines the power of ML predictions with rigorous performance guarantees, they have been extensively studied in the context of online optimization problems. Even though ski rental problems are one of the canonical problems in the field of online optimization, only deterministic algorithms were previously known for multi-option ski rental, with or without learning augmentation. We present the first randomized learning-augmented algorithm for this problem, surpassing previous performance guarantees given by deterministic algorithms. Our learning-augmented algorithm is based on a new, provably best-possible randomized competitive algorithm for the problem. Our results are further complemented by lower bounds for deterministic and randomized algorithms, and computational experiments evaluating our algorithms’ performance improvements.