Theory Lunch Seminar
— 1:00pm
Location:
In Person
-
Gates Hillman 8102
Speaker:
CHEN WANG
,
Postdoctoral Researcher, Texas A&M University and Rice University
https://sites.google.com/view/chen-wang/home
Metric Clustering and MST with Strong and Weak Distance Oracles
I will discuss recent results of k-clustering and MST in a new weak-strong oracle model. In this model, for a fixed metric space $(\chi, d)$, we can compute distances in two ways: via a "strong" oracle that returns exact distances $d(x,y)$, and a "weak" oracle that returns distances $ \tilde{d}(x,y)$ which may be arbitrarily corrupted with some probability. This model captures the increasingly common trade-off between employing both an expensive similarity model (e.g. a large-scale embedding model) and a less accurate but cheaper model. Hence, the goal is to make as few queries to the strong oracle as possible. We consider both "point queries", where the strong oracle is queried on a set of points $ S \subset \chi$ and returns $d(x,y)$ for all $x,y \in S$, and "edge queries" where it is queried for individual distances $d(x,y)$. Our main contributions are optimal algorithms and lower bounds for clustering and 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)}$ queries are required for any bounded approximation. For edge queries, our upper and lower bounds are both $ \tilde{\Theta}(k^2)$. Surprisingly, for the MST problem, we give an $ \ O{(\sqrt{ \log n})}$ approximation algorithm using no strong oracle queries at all, and we prove a matching $ \Omega{(\sqrt{ \log n})}$ lower bound which holds even if $ \tilde{\Omega}(n)$ strong oracle point queries are allowed.
Based on the this paper
Event Website:
https://www.cs.cmu.edu/~theorylunch/