کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950905 | 1441042 | 2017 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Improved and simplified inapproximability for k-means
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The k-means problem consists of finding k centers in Rd that minimize the sum of the squared distances of all points in an input set P from Rd to their closest respective center. Awasthi et al. recently showed that there exists a constant εâ²>0 such that it is NP-hard to approximate the k-means objective within a factor of 1+εâ². We establish that 1+εⲠis at least 1.0013.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 120, April 2017, Pages 40-43
Journal: Information Processing Letters - Volume 120, April 2017, Pages 40-43
نویسندگان
Euiwoong Lee, Melanie Schmidt, John Wright,