I was looking in VIJAY VAZIRANI Approximation Algorithms, but from the Table of contents , it seems that such algorithm is not there.
But you should try searching algortihm for finding maximal independent set of fixed sized boxes.... or unit sided.... it is somewhat dual, and there is good algortihm and PTAS for that. I know 2 approximation algorithm for fixed boxes, it is that you split input point to strips of unit size, and for each strip you compute minimum. now the optimal solution is smaller that number of covers of points from strips 0,2,4,8,10... you take each other. and also if you take 1,3,5,7,9... you can improve this by using the dynamci programing to solve for two strips at one time, but i am not sure how would that work, but that approach was used to find PTAS for finding maximum independent set in one unit side rectanges. Which can be somehow be found on internet. 2009/3/17 DavidR <david.dav...@gmail.com> > > I have a problem that must be well-studied, but I can't find the > literature. > > Given a set of points in the plane, find an approximately minimal > collection of boxes of fixed size that cover the points. > Alternatively, use discs of fixed radius to cover the points. > > I'm mostly interested in results people have had with different > algorithms and pointers to the literature. > > Thanks! > > > David > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
