SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2210.17028 · 2022

Improved Learning-augmented Algorithms for k-means and k-medians Clustering

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

We consider the problem of clustering in the learning-augmented setting, where we are given a data set in $d$-dimensional Euclidean space, and a label for each data point given by an oracle indicating what subsets of points should be clustered together. This setting captures situations where we have access to some auxiliary information about the data set relevant for our clustering objective, for instance the labels output by a neural network. Following prior work, we assume that there are at most an $α\in (0,c)$ for some $c<1$ fraction of false positives and false negatives in each predicted cluster, in the absence of which the labels would attain the optimal clustering cost $\mathrm{OPT}$. For a dataset of size $m$, we propose a deterministic $k$-means algorithm that produces centers with improved bound on clustering cost compared to the previous randomized algorithm while preserving the $O( d m \log m)$ runtime. Furthermore, our algorithm works even when the predictions are not very accurate, i.e. our bound holds for $α$ up to $1/2$, an improvement over $α$ being at most $1/7$ in the previous work. For the $k$-medians problem we improve upon prior work by achieving a biquadratic improvement in the dependence of the approximation factor on the accuracy parameter $α$ to get a cost of $(1+O(α))\mathrm{OPT}$, while requiring essentially just $O(md \log^3 m/α)$ runtime.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2210.17028")
get_code_for_paper("2210.17028")
have("2210.17028")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2210.17028.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2210.17028.svg)](https://syntology.ai/paper/2210.17028)

Connect an agent — have() is free.