We show that k-means clustering is an NP-hard optimization problem, even if k is fixed to 2.
Pre-2018 CSE ID: CS2008-0916
