English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study optimization problems in a metric space $(\mathcal{X},d)$ where wecan compute distances in two ways: via a ''strong'' oracle that returns exactdistances $d(x,y)$, and a ''weak'' oracle that returns distances$\tilde{d}(x,y)$ which may be arbitrarily corrupted with some probability. Thismodel captures the increasingly common trade-off between employing both anexpensive similarity model (e.g. a large-scale embedding model), and a lessaccurate but cheaper model. Hence, the goal is to make as few queries to thestrong oracle as possible. We consider both so-called ''point queries'', wherethe strong oracle is queried on a set of points $S \subset \mathcal{X} $ andreturns $d(x,y)$ for all $x,y \in S$, and ''edge queries'' where it is queriedfor individual distances $d(x,y)$.  Our main contributions are optimal algorithms and lower bounds for clusteringand Minimum Spanning Tree (MST) in this model. For $k$-centers, $k$-median, and$k$-means, we give constant factor approximation algorithms with only$\tilde{O}(k)$ strong oracle point queries, and prove that $\Omega(k)$ queriesare required for any bounded approximation. For edge queries, our upper andlower bounds are both $\tilde{\Theta}(k^2)$. Surprisingly, for the MST problemwe give a $O(\sqrt{\log n})$ approximation algorithm using no strong oraclequeries at all, and a matching $\Omega(\sqrt{\log n})$ lower bound. Weempirically evaluate our algorithms, and show that their quality is comparableto that of the baseline algorithms that are given all true distances, but whilequerying the strong oracle on only a small fraction ($<1\%$) of points.

Metric Clustering and MST with Strong and Weak Distance Oracles