Name
Abstract | ||
|---|---|---|
We consider the following clustering with outliers problem: Given a set of points X⊂{−1,1}n, such that there is some point z∈{−1,1}n for which Prx∈X ≥ ε] ≥ δ, find z. We call such a point z a (δ,ε)-center of X. In this work we give lower and upper bounds for the task of finding a (δ,ε)-center. We first show that for δ=1−ν close to 1, i.e. in the "unique decoding regime", given a (1−ν,ε)-centered set our algorithm can find a (1−(1+o(1))ν,(1−o(1))ε)-center. More interestingly, we study the "list decoding regime", i.e. when δ is close to 0. Our main upper bound shows that for values of ε and δ that are larger than 1/polylog(n), there exists a polynomial time algorithm that finds a (δ−o(1),ε−o(1))-center. Moreover, our algorithm outputs a list of centers explaining all of the clusters in the input. Our main lower bound shows that given a set for which there exists a (δ,ε)-center, it is hard to find even a (δ/nc, ε)-center for some constant c and ε=1/poly(n), δ=1/poly(n). |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-39206-1_35 | ICALP |
Keywords | DocType | Volume |
boolean hypercube,constant c,outliers problem,following clustering,unique decoding regime,points x,polynomial time algorithm,main upper bound shows,upper bound,main lower bound shows,approximation algorithms,clustering,list decoding | Journal | 20 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
6 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irit Dinur | 1 | 1187 | 85.67 |
| Elazar Goldenberg | 2 | 17 | 1.45 |