Weighted geometric set cover problems revisited
We study several set cover problems in low dimensional geometric settings. Specifically, we describe a PTAS for the problem of computing a minimum cover of given points by a set of weighted fat objects. Here, we allow the objects to expand by some prespecified δ-fraction of their diameter.<p>N...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Carleton University
2012-05-01
|
| Series: | Journal of Computational Geometry |
| Online Access: | http://jocg.org/index.php/jocg/article/view/77 |
| _version_ | 1819036470837510144 |
|---|---|
| author | Sariel Har-Peled Mira Lee |
| author_facet | Sariel Har-Peled Mira Lee |
| author_sort | Sariel Har-Peled |
| collection | DOAJ |
| description | We study several set cover problems in low dimensional geometric settings. Specifically, we describe a PTAS for the problem of computing a minimum cover of given points by a set of weighted fat objects. Here, we allow the objects to expand by some prespecified δ-fraction of their diameter.<p>Next, we show that the problem of computing a minimum weight cover of points by weighted halfplanes (without expansion) can be solved exactly in the plane. We also study the problem of covering ℝ<sup><em>d</em></sup> by weighted halfspaces, and provide approximation algorithms and hardness results. We also investigate the <q>dual</q>settings of computing minimum weight simplex that covers a given target point.</p><p>Finally, we provide a near linear time algorithm for the problem of solving a LP minimizing the total weight of violated constraints needed to be removed to make it feasible.</p> |
| first_indexed | 2024-12-21T08:06:02Z |
| format | Article |
| id | doaj.art-baba69efbd4c4c39889ebe854fb64bd2 |
| institution | Directory Open Access Journal |
| issn | 1920-180X |
| language | English |
| last_indexed | 2024-12-21T08:06:02Z |
| publishDate | 2012-05-01 |
| publisher | Carleton University |
| record_format | Article |
| series | Journal of Computational Geometry |
| spelling | doaj.art-baba69efbd4c4c39889ebe854fb64bd22022-12-21T19:10:47ZengCarleton UniversityJournal of Computational Geometry1920-180X2012-05-013110.20382/jocg.v3i1a425Weighted geometric set cover problems revisitedSariel Har-Peled0Mira Lee1University of Illinois, Urbana-ChampaignDepartment of Computer Science; Korea Advanced Institute of Science and Technology; Gwahangno 335 Yuseong-gu; Daejeon 305-701, Republic of KoreaWe study several set cover problems in low dimensional geometric settings. Specifically, we describe a PTAS for the problem of computing a minimum cover of given points by a set of weighted fat objects. Here, we allow the objects to expand by some prespecified δ-fraction of their diameter.<p>Next, we show that the problem of computing a minimum weight cover of points by weighted halfplanes (without expansion) can be solved exactly in the plane. We also study the problem of covering ℝ<sup><em>d</em></sup> by weighted halfspaces, and provide approximation algorithms and hardness results. We also investigate the <q>dual</q>settings of computing minimum weight simplex that covers a given target point.</p><p>Finally, we provide a near linear time algorithm for the problem of solving a LP minimizing the total weight of violated constraints needed to be removed to make it feasible.</p>http://jocg.org/index.php/jocg/article/view/77 |
| spellingShingle | Sariel Har-Peled Mira Lee Weighted geometric set cover problems revisited Journal of Computational Geometry |
| title | Weighted geometric set cover problems revisited |
| title_full | Weighted geometric set cover problems revisited |
| title_fullStr | Weighted geometric set cover problems revisited |
| title_full_unstemmed | Weighted geometric set cover problems revisited |
| title_short | Weighted geometric set cover problems revisited |
| title_sort | weighted geometric set cover problems revisited |
| url | http://jocg.org/index.php/jocg/article/view/77 |
| work_keys_str_mv | AT sarielharpeled weightedgeometricsetcoverproblemsrevisited AT miralee weightedgeometricsetcoverproblemsrevisited |