English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking

Pilipczuk, M., van Leeuwen, E. J., & Wiese, A. (2016). Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking. Retrieved from http://arxiv.org/abs/1611.06501.

Item is

Files

show Files
hide Files
:
arXiv:1611.06501.pdf (Preprint), 548KB
Name:
arXiv:1611.06501.pdf
Description:
File downloaded from arXiv at 2017-02-02 09:22
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Pilipczuk, Michał1, Author
van Leeuwen, Erik Jan2, Author              
Wiese, Andreas1, Author              
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Geometry, cs.CG
 Abstract: Consider the Maximum Weight Independent Set problem for rectangles: given a family of weighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlapping rectangles. The problem is notoriously hard both in the approximation and in the parameterized setting. The best known polynomial-time approximation algorithms achieve super-constant approximation ratios [Chalermsook and Chuzhoy, SODA 2009; Chan and Har-Peled, Discrete & Comp. Geometry 2012], even though there is a $(1+\epsilon)$-approximation running in quasi-polynomial time [Adamaszek and Wiese, FOCS 2013; Chuzhoy and Ene, FOCS 2016]. When parameterized by the target size of the solution, the problem is $\mathsf{W}[1]$-hard even in the unweighted setting [Marx, FOCS 2007]. To achieve tractability, we study the following shrinking model: one is allowed to shrink each input rectangle by a multiplicative factor $1-\delta$ for some fixed $\delta>0$, but the performance is still compared against the optimal solution for the original, non-shrunk instance. We prove that in this regime, the problem admits an EPTAS with running time $f(\epsilon,\delta)\cdot n^{\mathcal{O}(1)}$, and an FPT algorithm with running time $f(k,\delta)\cdot n^{\mathcal{O}(1)}$, in the setting where a maximum-weight solution of size at most $k$ is to be computed. This improves and significantly simplifies a PTAS given earlier for this problem [Adamaszek et al., APPROX 2015], and provides the first parameterized results for the shrinking model. Furthermore, we explore kernelization in the shrinking model, by giving efficient kernelization procedures for several variants of the problem when the input rectangles are squares.

Details

show
hide
Language(s): eng - English
 Dates: 2016-11-202016
 Publication Status: Published online
 Pages: 25 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1611.06501
URI: http://arxiv.org/abs/1611.06501
BibTex Citekey: DBLP:journals/corr/PilipczukLW16
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show