{"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":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.0002633851,0.0002444224,0.000333197,0.0005773065,0.00002212058,0.00006496305,0.0003254029,0.0004549952,0.00003089133],"category_scores_gemma":[0.0000394418,0.0002075568,0.0001341008,0.0002023601,0.00002995083,0.00004510682,0.0002995484,0.0005348823,0.00001136156],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.0001621983,"about_ca_system_score_gemma":0.00004555941,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0001464645,"about_ca_topic_score_gemma":0.00007625898,"domain_scores_codex":[0.998828,0.00001779147,0.0002841795,0.0003161912,0.0001802309,0.0003736011],"domain_scores_gemma":[0.9991583,0.0002043383,0.00002274031,0.0004516261,0.0001000855,0.00006294271],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"simulation_or_modeling","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.0001335359,0.0001590425,0.0007941308,0.001270388,0.0005178543,0.0001152511,0.0007582608,0.5680336,0.006863689,0.02331635,0.07384501,0.3241929],"study_design_scores_gemma":[0.0004768059,0.00004309073,0.00007308523,0.0007742129,0.00002700344,0.000005337402,0.0000660512,0.8735837,0.09566693,0.01819242,0.01042288,0.0006685249],"study_design_candidate":"simulation_or_modeling","study_design_consensus":"simulation_or_modeling","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.005397803,0.0004855991,0.9745652,0.0001513334,0.0004588391,0.0004809904,0.00002106652,0.001011828,0.01742732],"genre_scores_gemma":[0.9737194,0.0002034166,0.02537825,0.0000490584,0.0001681282,0.00008132373,0.00001550976,0.0000706569,0.0003142805],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.9683216,"threshold_uncertainty_score":0.8463919,"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."}}