Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem

DOI10.1016/j.entcs.2019.08.050OpenAlexW2978067824WikidataQ113317379 ScholiaQ113317379MaRDI QIDQ2132392

Lucas Murtinho, Eduardo Sany Laber

Publication date: 27 April 2022

Full work available at URL: https://doi.org/10.1016/j.entcs.2019.08.050

zbMATH Keywords

GiniapproximationNP-completeness\(k\)-meansimpurity

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Graph theory (05Cxx)

Cites Work

• A local search approximation algorithm for \(k\)-means clustering
• Minimum impurity partitions
• Clustering for metric and nonmetric distance measures
• Unnamed Item

This page was built for publication: Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem