Hardness and Approximation Schemes for Discrete Packing and Domination
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909581764984832 |
|---|---|
| author | Madireddy, Raghunath Reddy Mudgal, Apurva Pandit, Supantha |
| author_facet | Madireddy, Raghunath Reddy Mudgal, Apurva Pandit, Supantha |
| contents | We present polynomial-time approximation schemes based on local search} technique for both geometric (discrete) independent set (\mdis) and geometric (discrete) dominating set (\mdds) problems, where the objects are arbitrary radii disks and arbitrary side length axis-parallel squares. Further, we show that the \mdds~problem is \apx-hard for various shapes in the plane. Finally, we prove that both \mdis~and \mdds~problems are \np-hard for unit disks intersecting a horizontal line and axis-parallel unit squares intersecting a straight line with slope $-1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_12022 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hardness and Approximation Schemes for Discrete Packing and Domination Madireddy, Raghunath Reddy Mudgal, Apurva Pandit, Supantha Computational Geometry We present polynomial-time approximation schemes based on local search} technique for both geometric (discrete) independent set (\mdis) and geometric (discrete) dominating set (\mdds) problems, where the objects are arbitrary radii disks and arbitrary side length axis-parallel squares. Further, we show that the \mdds~problem is \apx-hard for various shapes in the plane. Finally, we prove that both \mdis~and \mdds~problems are \np-hard for unit disks intersecting a horizontal line and axis-parallel unit squares intersecting a straight line with slope $-1$. |
| title | Hardness and Approximation Schemes for Discrete Packing and Domination |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2504.12022 |