Geometric Packing under Non-uniform Constraints

Details Geometric Packing under Non-uniform Constraints Geometric Packing under Non-uniform Constraints

2011-07-14

arxiv.org/abs/1107.2949v2

Computer Science

Computational Geometry

Scientific paper

We study the problem of discrete geometric packing. Here, given weighted regions (say in the plane) and points (with capacities), one has to pick a maximum weight subset of the regions such that no point is covered more than its capacity. We provide a general framework and an algorithm for approximating the optimal solution for packing in hypergraphs arising out of such geometric settings. Using this framework we get a flotilla of results on this problem (and also on its dual, where one wants to pick a maximum weight subset of the points when the regions have capacities). For example, for the case of fat triangles of similar size, we show an O(1)-approximation and prove that no \PTAS is possible.

Affiliated with

Also associated with

No associations

Rating

Geometric Packing under Non-uniform Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Geometric Packing under Non-uniform Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Geometric Packing under Non-uniform Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-224400