Yong-Ho Shin

Fateme Abbasi, Hyung-Chan An, Jarosław Byrka et al.

Correlation Clustering is a fundamental clustering problem that is generalized to Chromatic Correlation Clustering to incorporate categorical data. Both problems have been intensively studied, and recently, substantial improvements were obtained in the approximation algorithms for Correlation Clustering. At the heart of this success lies a new linear program (LP) formulation called the cluster LP; a natural question was whether this LP can be extended to Chromatic Correlation Clustering to enable similar success. We answer this question in the affirmative by presenting a $(2+\varepsilon)$-approximation algorithm for the problem using a chromatic cluster LP. We then consider Weighted Chromatic Correlation Clustering, in which edges have fractional weights satisfying the probability constraints, to show that our algorithm extends to this weighted version to yield the same approximation guarantee.

Hyunki Seong, Jeong-Kyun Lee, Heesoo Myeong et al.

Learning interactive motion behaviors among multiple agents is a core challenge in autonomous driving. While imitation learning models generate realistic trajectories, they often inherit biases from datasets dominated by safe demonstrations, limiting robustness in safety-critical cases. Moreover, most studies rely on open-loop evaluation, overlooking compounding errors in closed-loop execution. We address these limitations with two complementary strategies. First, we propose Group Relative Behavior Optimization (GRBO), a reinforcement learning post-training method that fine-tunes pretrained behavior models via group relative advantage maximization with human regularization. Using only 10% of the training dataset, GRBO improves safety performance by over 40% while preserving behavioral realism. Second, we introduce Warm-K, a warm-started Top-K sampling strategy that balances consistency and diversity in motion selection. Our Warm-K method-based test-time scaling enhances behavioral consistency and reactivity at test time without retraining, mitigating covariate shift and reducing performance discrepancies. Demo videos are available in the supplementary material.

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 practical applications, such as online advertising and resource allocation. Motivated by recent progress in learning-augmented algorithms, we study online bipartite fractional matching when the algorithm is given advice in the form of a suggested matching in each iteration. We develop algorithms for both the vertex-weighted and unweighted variants that provably dominate the naive "coin flip" strategy of randomly choosing between the advice-following and advice-free algorithms. Moreover, our algorithm for the vertex-weighted setting extends to the AdWords problem under the small bids assumption, yielding a significant improvement over the seminal work of Mahdian, Nazerzadeh, and Saberi (EC 2007, TALG 2012). Complementing our positive results, we establish a hardness bound on the robustness-consistency tradeoff that is attainable by any algorithm. We empirically validate our algorithms through experiments on synthetic and real-world data.