Geometric Packing Under Nonuniform Constraints

Date
2018-10-22
item.page.orcid
Journal Title
Journal ISSN
Volume Title
Publisher
SIAM Publications
item.page.doi
Abstract

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.

Description
Full text access from Treasures at UT Dallas is restricted to current UTD affiliates.
Keywords
Rectangles, Graphic methods, Set theory, Computer science, Mathematical optimization, Algorithms, Geometrical constructions
item.page.sponsorship
item.page.rights
©2017 Society for Industrial and Applied Mathematics
Citation