{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T03:04:04Z","timestamp":1773803044143,"version":"3.50.1"},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","issue":"25","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AAAI"],"abstract":"<jats:p>In this paper, we investigate the  learning-augmented k-median clustering problem, which aims to improve the performance of traditional clustering algorithms by preprocessing the point set with a predictor of error rate \u03b1 \u2208 [0,1). This preprocessing step assigns potential labels to the points before clustering. We introduce an  algorithm for this problem based on a simple yet effective  sampling method, which substantially improves upon the time complexities of existing algorithms. Moreover, we  mitigate their exponential dependency on the dimensionality of the Euclidean space. Lastly, we conduct experiments to compare our method with several state-of-the-art learning-augmented k-median clustering methods. The experimental results suggest that our proposed approach can significantly reduce the computational complexity in practice, while achieving a lower clustering cost.<\/jats:p>","DOI":"10.1609\/aaai.v40i25.39186","type":"journal-article","created":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:23:00Z","timestamp":1773796980000},"page":"20509-20517","source":"Crossref","is-referenced-by-count":0,"title":["Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High Dimensions"],"prefix":"10.1609","volume":"40","author":[{"given":"Kangke","family":"Cheng","sequence":"first","affiliation":[]},{"given":"Shihong","family":"Song","sequence":"additional","affiliation":[]},{"given":"Guanlin","family":"Mo","sequence":"additional","affiliation":[]},{"given":"Hu","family":"Ding","sequence":"additional","affiliation":[]}],"member":"9382","published-online":{"date-parts":[[2026,3,14]]},"container-title":["Proceedings of the AAAI Conference on Artificial Intelligence"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/39186\/43147","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/39186\/43147","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:23:00Z","timestamp":1773796980000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/39186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,14]]},"references-count":0,"journal-issue":{"issue":"25","published-online":{"date-parts":[[2026,3,17]]}},"URL":"https:\/\/doi.org\/10.1609\/aaai.v40i25.39186","relation":{},"ISSN":["2374-3468","2159-5399"],"issn-type":[{"value":"2374-3468","type":"electronic"},{"value":"2159-5399","type":"print"}],"subject":[],"published":{"date-parts":[[2026,3,14]]}}}