KisfaludiBak, Sándor ;
Marx, Dániel ;
van der Zanden, Tom C.
How Does Object Fatness Impact the Complexity of Packing in d Dimensions?
Abstract
Packing is a classical problem where one is given a set of subsets of Euclidean space called objects, and the goal is to find a maximum size subset of objects that are pairwise nonintersecting. The problem is also known as the Independent Set problem on the intersection graph defined by the objects. Although the problem is NPcomplete, there are several subexponential algorithms in the literature. One of the key assumptions of such algorithms has been that the objects are fat, with a few exceptions in two dimensions; for example, the packing problem of a set of polygons in the plane surprisingly admits a subexponential algorithm. In this paper we give tight running time bounds for packing similarlysized nonfat objects in higher dimensions.
We propose an alternative and very weak measure of fatness called the stabbing number, and show that the packing problem in Euclidean space of constant dimension d >=slant 3 for a family of similarly sized objects with stabbing number alpha can be solved in 2^O(n^(11/d) alpha) time. We prove that even in the case of axisparallel boxes of fixed shape, there is no 2^o(n^(11/d) alpha) algorithm under ETH. This result smoothly bridges the whole range of having constantfat objects on one extreme (alpha=1) and a subexponential algorithm of the usual running time, and having very "skinny" objects on the other extreme (alpha=n^(1/d)), where we cannot hope to improve upon the brute force running time of 2^O(n), and thereby characterizes the impact of fatness on the complexity of packing in case of similarly sized objects. We also study the same problem when parameterized by the solution size k, and give a n^O(k^(11/d) alpha) algorithm, with an almost matching lower bound: there is no algorithm with running time of the form f(k) n^o(k^(11/d) alpha/log k) under ETH. One of our main tools in these reductions is a new wiring theorem that may be of independent interest.
BibTeX  Entry
@InProceedings{kisfaludibak_et_al:LIPIcs:2019:11532,
author = {S{\'a}ndor KisfaludiBak and D{\'a}niel Marx and Tom C. van der Zanden},
title = {{How Does Object Fatness Impact the Complexity of Packing in d Dimensions?}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {36:136:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11532},
URN = {urn:nbn:de:0030drops115327},
doi = {10.4230/LIPIcs.ISAAC.2019.36},
annote = {Keywords: Geometric intersection graph, Independent Set, Object fatness}
}
28.11.2019
Keywords: 

Geometric intersection graph, Independent Set, Object fatness 
Seminar: 

30th International Symposium on Algorithms and Computation (ISAAC 2019)

Issue date: 

2019 
Date of publication: 

28.11.2019 