用历史数据提升k-中位数聚类的平均性能，自动适应变化。
Learning-Augmented Algorithms for $k$-median via Online Learning
- 基于在线学习框架，利用历史实例指导未来求解
- 平均性能接近事后最优固定解，且算法高效
- 适合动态数据流场景，实测表现接近最优
学习增强型算法旨在利用过去问题实例的机器学习技术，为未来实例提供指导。本文提出一种受在线学习启发的新模型：给定一系列问题实例，目标是利用前期实例为后续实例提出解决方案。算法性能通过所有实例上的平均性能衡量，单个实例的性能定义为算法解与最优解成本之比。将该框架应用于经典的k-中位数聚类问题，提出一种高效学习算法，可近似达到事后最优固定k-中位数解在所有实例上的平均性能。实验验证了算法的实测性能接近最优，并能自动适应动态变化的实例序列。
原文摘要 · Abstract (English)
The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for learning-augmented algorithms inspired by online learning. In this model, we are given a sequence of instances of a problem and the goal of the learning-augmented algorithm is to use prior instances to propose a solution to a future instance of the problem. The performance of the algorithm is measured by its average performance across all the instances, where the performance on a single instance is the ratio between the cost of the algorithm's solution and that of an optimal solution for that instance. We apply this framework to the classic $k$-median clustering problem, and give an efficient learning algorithm that can approximately match the average performance of the best fixed $k$-median solution in hindsight across all the instances. We also experimentally evaluate our algorithm and show that its empirical performance is close to optimal, and also that it automatically adapts the solution to a dynamically changing sequence.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。