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$ – Suresh Venkat Sep 19 '12 at 19:49
  • 1
    $\begingroup$ Yes , I am looking for a precise value. $\endgroup$ – Shalabh Vidyarthi Sep 20 '12 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 '12 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$ – Chandra Chekuri Sep 23 '12 at 4:13

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.