I have two questions regarding coreset construction of clustering problem

  1. In A Unified Framework for Approximating and Clustering Data, a very general framework is given to construct coresets for vairous computational problems, including clustering. The starting point of this work is the theory of VC dimension, more precisely "Pseudodimension".They used tight sample complexity result of this paper by Li et.al. My question is whether this framework can be (or have been) improved by using other notion of sample complexity, such as Rademacher complexity .
  2. Can the Clarkson-Shor sampling technique be used in coreset construction?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.