Inapproximability of Clustering in Lp metrics

Cohen-Addad, V; Karthik, CS

Cohen-Addad, V (reprint author), UPMC Univ Paris 06, Sorbonne Univ, CNRS, LIP6, Paris, France.

2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019), 2019; (): 519

Abstract

Proving hardness of approximation for min-sum objectives is an infamous challenge. For classic problems such as the Traveling Salesman problem, the St......

Full Text Link