Geometric Packing Under Nonuniform Constraints
| dc.contributor.author | Ene, Alina | en_US |
| dc.contributor.author | Har-Peled, Sariel | en_US |
| dc.contributor.author | Raichel, Benjamin A. | en_US |
| dc.contributor.utdAuthor | Raichel, Benjamin A. | en_US |
| dc.date.accessioned | 2018-10-22T20:10:18Z | |
| dc.date.available | 2018-10-22T20:10:18Z | |
| dc.date.created | 2017-11-14 | en_US |
| dc.date.issued | 2018-10-22 | |
| dc.description | Full text access from Treasures at UT Dallas is restricted to current UTD affiliates. | en_US |
| dc.description.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. | en_US |
| dc.identifier.bibliographicCitation | Ene, Alina, Sariel Har-Peled, and Benjamin Raichel. 2017. "Geometric Packing Under Nonuniform Constraints." Siam Journal on Computing 46(6), doi:http://dx.doi.org/10.1137/120898413 | en_US |
| dc.identifier.issn | 0097-5397 | en_US |
| dc.identifier.issue | 6 | en_US |
| dc.identifier.uri | http://hdl.handle.net/10735.1/6243 | |
| dc.identifier.volume | 46 | en_US |
| dc.language.iso | en | en_US |
| dc.publisher | SIAM Publications | en_US |
| dc.relation.uri | http://dx.doi.org/10.1137/120898413 | en_US |
| dc.rights | ©2017 Society for Industrial and Applied Mathematics | en_US |
| dc.source.journal | SIAM Journal On Computing | en_US |
| dc.subject | Rectangles | en_US |
| dc.subject | Graphic methods | en_US |
| dc.subject | Set theory | en_US |
| dc.subject | Computer science | en_US |
| dc.subject | Mathematical optimization | en_US |
| dc.subject | Algorithms | en_US |
| dc.subject | Geometrical constructions | en_US |
| dc.title | Geometric Packing Under Nonuniform Constraints | en_US |
| dc.type.genre | article | en_US |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- JECS-6182-8388.70-LINK.pdf
- Size:
- 95.54 KB
- Format:
- Adobe Portable Document Format
- Description:
- Link to Article