What is best known approximation ratio for the following problem :

Given n points in d dimensions , what is the minimum number of axis parallel lines needed to cover them . A line is said to cover a point , if the point lies on the line .

  • 3
    $\begingroup$ A constant factor should follow from VC-dimension arguments. I assume you'd want a precise constant ? $\endgroup$ Sep 19, 2012 at 19:49
  • 1
    $\begingroup$ Yes , I am looking for a precise value. $\endgroup$ Sep 20, 2012 at 14:22
  • $\begingroup$ @SureshVenkat Can you elaborate? I'm only aware of the log(OPT) approximation factor that would come automatically from VC-dimension arguments. $\endgroup$
    – James King
    Sep 22, 2012 at 1:16
  • $\begingroup$ Each point is in exactly $d$ axis-parallel lines so this is a special case of set cover where an element is in at most $d$ sets. One can get a $d$-approximation via LP rounding but perhaps one can do better using the geometric structure? $\endgroup$ Sep 23, 2012 at 4:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.