{"id":"W2313395524","doi":"10.1109/focs.2016.47","title":"Local Search Yields a PTAS for $k$-Means in Doubling Metrics","year":2016,"lang":"en","type":"preprint","venue":"","topic":"Sparse and Compressive Sensing Techniques","field":"Engineering","cited_by":45,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Alberta","funders":"Natural Sciences and Engineering Research Council of Canada; Canada Research Chairs","keywords":"Mathematics; Combinatorics; Dimension (graph theory); Euclidean space; Partition (number theory); Euclidean distance; Simple (philosophy); Approximation algorithm; Metric space; Euclidean geometry; Space (punctuation); Local search (optimization); Heuristic; Discrete mathematics; Algorithm; Mathematical optimization; Computer science","routes":{"ca_aff":true,"ca_fund":true,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.002396035,0.001895907,0.002237638,0.001725155,0.001700106,0.00255525,0.002688846,0.003191671,0.01091606],"category_scores_gemma":[0.01690715,0.0006923513,0.002104122,0.002055019,0.002199129,0.004811746,0.005010601,0.004494894,0.005268591],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002543704,"about_ca_system_score_gemma":0.002158166,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.004290896,"about_ca_topic_score_gemma":0.004067871,"domain_scores_codex":[0.9978143,0.0006459219,0.0001522794,0.0006051399,0.0006030665,0.000179279],"domain_scores_gemma":[0.9958009,0.002237344,0.0002558426,0.0007610741,0.0006808789,0.0002638784],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.0002942277,0.0001150891,0.001103634,0.0004891466,0.0001199132,0.0002049917,0.0004054642,0.1338619,0.003642245,0.6532651,0.02635734,0.1801409],"study_design_scores_gemma":[0.0000487166,0.0001705136,0.0003896152,0.00008646113,0.00004937304,0.00026738,0.00007377865,0.5230583,0.001585298,0.4580833,0.01613623,0.00005098921],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.01391069,0.001448233,0.9644215,0.001143894,0.0002201275,0.0001500766,0.0002365825,0.0009931255,0.01747588],"genre_scores_gemma":[0.2171291,0.001852757,0.7487513,0.001266484,0.0003789552,0.0007867703,0.0008579985,0.001225562,0.0277511],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01091606,"threshold_uncertainty_score":0.03651786,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.0647369646453559,"score_gpt":0.3000650282161767,"score_spread":0.2353280635708208,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}