Pilipczuk, Michal ;
van Leeuwen, Erik Jan ;
Wiese, Andreas
Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
Abstract
Consider the Maximum Weight Independent Set problem for rectangles: given a family of weighted axisparallel rectangles in the plane, find a maximumweight subset of nonoverlapping rectangles. The problem is notoriously hard both in the approximation and in the parameterized setting. The best known polynomialtime approximation algorithms achieve superconstant approximation ratios [Chalermsook & Chuzhoy, Proc. SODA 2009; Chan & HarPeled, Discrete & Comp. Geometry, 2012], even though there is a (1+epsilon)approximation running in quasipolynomial time [Adamaszek & Wiese, Proc. FOCS 2013; Chuzhoy & Ene, Proc. FOCS 2016]. When parameterized by the target size of the solution, the problem is W[1]hard even in the unweighted setting [Marx, ESA 2005].
To achieve tractability, we study the following shrinking model: one is allowed to shrink each input rectangle by a multiplicative factor 1delta for some fixed delta > 0, but the performance is still compared against the optimal solution for the original, nonshrunk instance. We prove that in this regime, the problem admits an EPTAS with running time f(epsilon,delta) n^{O(1)}, and an FPT algorithm with running time f(k,delta) n^{O(1)}, in the setting where a maximumweight solution of size at most k is to be computed. This improves and significantly simplifies a PTAS given earlier for this problem [Adamaszek, Chalermsook & Wiese, Proc. APPROX/RANDOM 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.
BibTeX  Entry
@InProceedings{pilipczuk_et_al:LIPIcs:2017:8091,
author = {Michal Pilipczuk and Erik Jan van Leeuwen and Andreas Wiese},
title = {{Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {42:142:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8091},
URN = {urn:nbn:de:0030drops80917},
doi = {10.4230/LIPIcs.MFCS.2017.42},
annote = {Keywords: Combinatorial optimization, Approximation algorithms, Fixedparameter algorithms}
}
01.12.2017
Keywords: 

Combinatorial optimization, Approximation algorithms, Fixedparameter algorithms 
Seminar: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Issue date: 

2017 
Date of publication: 

01.12.2017 