4 citations · 5 across the 13 of their papers we have counts for
16 papers
Iterative Randomized Rounding for Better-Than-2 k-Median Approximation
Jarosław Byrka, Yuhao Guo, Yang Hu +5
We study the classic -median problem and refine the iterative rounding framework recently introduced by Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which yields a $(2+\varepsil…
Pure Tail Constraints for Online Problems
Mateusz Basiak, Marcin Bienkowski, Yongho Shin +1
Controlling tail risk is an important objective in online optimization, and recently it has been studied in the context of competitive analysis. Continuing this line of research, w…
Parsimonious Learning-Augmented Online Metric Matching
Yongho Shin, Phanu Vajanopath
Learning-augmented algorithms have received significant attention in recent years, particularly in the context of online optimization. Motivated by the high computational cost of g…
Optimal Learning-Augmented Algorithm for Online Bidding
Changyeol Lee, Dahoon Lee, Jongseo Lee +2
Recent advances in machine learning have spurred significant interest in learning-augmented algorithms, particularly for online optimization. A growing body of work has studied onl…
Servicing Matched Client Pairs with Facilities
Fateme Abbasi, Martin Böhm, Jarosław Byrka +2
We study Facility Location with Matching, a Facility Location problem where, given additional information about which pair of clients is compatible to be matched, we need to match…
Post-Training and Test-Time Scaling of Generative Agent Behavior Models for Interactive Autonomous Driving
Hyunki Seong, Jeong-Kyun Lee, Heesoo Myeong +5
Learning interactive motion behaviors among multiple agents is a core challenge in autonomous driving. While imitation learning models generate realistic trajectories, they often i…
Approximating (Weighted) Chromatic Correlation Clustering via Cluster LP
Fateme Abbasi, Hyung-Chan An, Jarosław Byrka +2
Correlation Clustering is a fundamental clustering problem that is generalized to Chromatic Correlation Clustering to incorporate categorical data. Both problems have been intensiv…
Online Rounding Schemes for Edge Cover
Jarosław Byrka, Yongho Shin
Linear programming rounding is a fundamental technique in the design of approximation and online algorithms. A growing body of work has investigated online rounding schemes for var…
Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach
Changyeol Lee, Yongho Shin, Hyung-Chan An
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 catego…
Learning-Augmented Online Bipartite Fractional Matching
Davin Choo, Billy Jin, Yongho Shin
Online bipartite matching is a fundamental problem in online optimization, extensively studied both in its integral and fractional forms due to its theoretical significance and pra…
Textual Training for the Hassle-Free Removal of Unwanted Visual Data: Case Studies on OOD and Hateful Image Detection
Saehyung Lee, Jisoo Mok, Sangha Park +3
In our study, we explore methods for detecting unwanted content lurking in visual datasets. We provide a theoretical analysis demonstrating that a model capable of successfully par…
On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental
Yongho Shin, Changyeol Lee, Hyung-Chan An
The learning-augmented multi-option ski rental problem generalizes the classical ski rental problem in two ways: the algorithm is provided with a prediction on the number of days w…
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…
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…