Nearly-TightandObliviousAlgorithmsfor ExplainableClustering: FullVersion

Wegiveanalgorithm thatoutputs anexplainable clustering that loses at most a factor ofO(log2k) compared to an optimal (not necessarily explainable) clustering for thek-medians objective, and a factor of O(klog2k)forthek-meansobjective.