Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BY - Uznanie autorstwaOn Geometric Set Cover for Orthants
| dc.abstract.en | We study SET COVER for orthants: Given a set of points in a d-dimensional Euclidean space and a set of orthants of the form (-infty,p_1] x ... x (-infty,p_d], select a minimum number of orthants so that every point is contained in at least one selected orthant. This problem draws its motivation from applications in multi-objective optimization problems. While for d=2 the problem can be solved in polynomial time, for d>2 no algorithm is known that avoids the enumeration of all size-k subsets of the input to test whether there is a set cover of size k. Our contribution is a precise understanding of the complexity of this problem in any dimension d >= 3, when k is considered a parameter: - For d=3, we give an algorithm with runtime n^O(sqrt{k}), thus avoiding exhaustive enumeration. - For d=3, we prove a tight lower bound of n^Omega(sqrt{k}) (assuming ETH). - For d >=slant 4, we prove a tight lower bound of n^Omega(k) (assuming ETH). Here n is the size of the set of points plus the size of the set of orthants. The first statement comes as a corollary of a more general result: an algorithm for SET COVER for half-spaces in dimension 3. In particular, we show that given a set of points U in R^3, a set of half-spaces D in R^3, and an integer k, one can decide whether U can be covered by the union of at most k half-spaces from D in time |D|^O(sqrt{k})* |U|^O(1). We also study approximation for SET COVER for orthants. While in dimension 3 a PTAS can be inferred from existing results, we show that in dimension 4 and larger, there is no 1.05-approximation algorithm with runtime f(k)* n^o(k) for any computable f, where k is the optimum. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.conference.country | Niemcy |
| dc.conference.datefinish | 2019-09-13 |
| dc.conference.datestart | 2019-09-09 |
| dc.conference.place | Monachium |
| dc.conference.series | European Symposium on Algorithms |
| dc.conference.series | European Symposium on Algorithms |
| dc.conference.seriesshortcut | ESA |
| dc.conference.shortcut | ESA 2019 |
| dc.conference.weblink | http://esa-symposium.org/ |
| dc.contributor.author | Pilipczuk, Marcin |
| dc.contributor.author | Kisfaludi-Bak, Sándor |
| dc.contributor.author | Bringmann, Karl |
| dc.contributor.author | Leeuwen, Erik Jan van |
| dc.date.accessioned | 2024-01-25T15:45:11Z |
| dc.date.available | 2024-01-25T15:45:11Z |
| dc.date.copyright | 2019-09-06 |
| dc.date.issued | 2019 |
| dc.description.accesstime | AT_PUBLICATION |
| dc.description.finance | Nie dotyczy |
| dc.description.version | FINAL_PUBLISHED |
| dc.identifier.doi | 10.4230/LIPICS.ESA.2019.26 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/114698 |
| dc.identifier.weblink | https://drops.dagstuhl.de/opus/volltexte/2019/11147/ |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.pages | 26:1--26:18 |
| dc.rights | CC-BY |
| dc.sciencecloud | nosend |
| dc.subject.en | Set Cover |
| dc.subject.en | parameterized complexity |
| dc.subject.en | algorithms |
| dc.subject.en | Exponential Time Hypothesis |
| dc.title | On Geometric Set Cover for Orthants |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |