@article{d42643607798444283357d884b63cdee,
title = "Geometric packing under nonuniform constraints",
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 otilla 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.",
keywords = "Independent set, Optimization, Rounding scheme",
author = "Alina Ene and Sariel Har-Peled and Benjamin Raichel",
note = "Funding Information: The first author was partially supported by NSF grants CCF-0728782 and CCF- 1016684. The second author was partially supported by NSF AF awards CCF-0915984, CCF- 1421231, and CCF-1217462. The third author was partially supported by NSF AF award CCF- 0915984. Funding Information: ∗Received by the editors November 9, 2012; accepted for publication (in revised form) August 7, 2017; published electronically November 14, 2017. A preliminary version of this paper appeared in Proceedings of SoCG 2012. http://www.siam.org/journals/sicomp/46-6/89841.html Funding: The first author was partially supported by NSF grants CCF-0728782 and CCF-1016684. The second author was partially supported by NSF AF awards CCF-0915984, CCF-1421231, and CCF-1217462. The third author was partially supported by NSF AF award CCF-0915984. †Department of Computer Science, Boston University, Boston, MA 02215 (aene@bu.edu, http://cs-people.bu.edu/aene/). ‡Department of Computer Science, University of Illinois, Urbana, IL, 61801 (sariel@uiuc.edu, http://www.uiuc.edu/∼sariel/). §Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080 (benjamin.raichel@utdallas.edu, http://utdallas.edu/∼bar150630). 1See http://tinyurl.com/7td67v3 for a story of an airport closing down because of radio interference. Publisher Copyright: Copyright {\textcopyright} by SIAM.",
year = "2017",
doi = "10.1137/120898413",
language = "English (US)",
volume = "46",
pages = "1745--1784",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "6",
}