Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFramework for $exists mathbb{R}$-Completeness of Two-Dimensional Packing Problems
87
0
0.0
(
0
)
Added by
Tillmann Miltzow
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials. A two-dimensional packing problem is defined by the type of pieces, containers, and motions that are allowed. The aim is to decide if a given set of pieces can be placed inside a given container. The pieces must be placed so that they are pairwise interior-disjoint, and only motions of the allowed type can be used to move them there. We establish a framework which enables us to show that for many combinations of allowed pieces, containers, and motions, the resulting problem is $existsmathbb R$-complete. This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution. We consider packing problems where only translations are allowed as the motions, and problems where arbitrary rigid motions are allowed, i.e., both translations and rotations. When rotations are allowed, we show that the following combinations of allowed pieces and containers are $existsmathbb R$-complete: $bullet$ simple polygons, each of which has at most 8 corners, into a square, $bullet$ convex objects bounded by line segments and hyperbolic curves into a square, $bullet$ convex polygons into a container bounded by line segments and hyperbolic curves. Restricted to translations, we show that the following combinations are $existsmathbb R$-complete: $bullet$ objects bounded by segments and hyperbolic curves into a square, $bullet$ convex polygons into a container bounded by segments and hyperbolic curves.
rate research
Read More
We show that the decision problem of determining whether a given (abstract simplicial) $k$-complex has a geometric embedding in $mathbb R^d$ is complete for the Existential Theory of the Reals for all $dgeq 3$ and $kin{d-1,d}$. This implies that the problem is polynomial time equivalent to determining whether a polynomial equation system has a real root. Moreover, this implies NP-hardness and constitutes the first hardness results for the algorithmic problem of geometric embedding (abstract simplicial) complexes.
We study several problems on geometric packing and covering with movement. Given a family $mathcal{I}$ of $n$ intervals of $kappa$ distinct lengths, and another interval $B$, can we pack the intervals in $mathcal{I}$ inside $B$ (respectively, cover $B$ by the intervals in $mathcal{I}$) by moving $tau$ intervals and keeping the other $sigma = n - tau$ intervals unmoved? We show that both packing and covering are W[1]-hard with any one of $kappa$, $tau$, and $sigma$ as single parameter, but are FPT with combined parameters $kappa$ and $tau$. We also obtain improved polynomial-time algorithms for packing and covering, including an $O(nlog^2 n)$ time algorithm for covering, when all intervals in $mathcal{I}$ have the same length.
In a nutshell, we show that polynomials and nested polytopes are topological, algebraic and algorithmically equivalent. Given two polytops $Asubseteq B$ and a number $k$, the Nested Polytope Problem (NPP) asks, if there exists a polytope $X$ on $k$ vertices such that $Asubseteq X subseteq B$. The polytope $A$ is given by a set of vertices and the polytope $B$ is given by the defining hyperplanes. We show a universality theorem for NPP. Given an instance $I$ of the NPP, we define the solutions set of $I$ as $$ V(I) = {(x_1,ldots,x_k)in mathbb{R}^{kcdot n} : Asubseteq text{conv}(x_1,ldots,x_k) subseteq B}.$$ As there are many symmetries, induced by permutations of the vertices, we will consider the emph{normalized} solution space $V(I)$. Let $F$ be a finite set of polynomials, with bounded solution space. Then there is an instance $I$ of the NPP, which has a rationally-equivalent normalized solution space $V(I)$. Two sets $V$ and $W$ are rationally equivalent if there exists a homeomorphism $f : V rightarrow W$ such that both $f$ and $f^{-1}$ are given by rational functions. A function $f:Vrightarrow W$ is a homeomorphism, if it is continuous, invertible and its inverse is continuous as well. As a corollary, we show that NPP is $exists mathbb{R}$-complete. This implies that unless $exists mathbb{R} =$ NP, the NPP is not contained in the complexity class NP. Note that those results already follow from a recent paper by Shitov. Our proof is geometric and arguably easier.
Given an initial placement of a set of rectangles in the plane, we consider the problem of finding a disjoint placement of the rectangles that minimizes the area of the bounding box and preserves the orthogonal order i.e. maintains the sorted ordering of the rectangle centers along both $x$-axis and $y$-axis with respect to the initial placement. This problem is known as Layout Adjustment for Disjoint Rectangles(LADR). It was known that LADR is $mathbb{NP}$-hard, but only heuristics were known for it. We show that a certain decision version of LADR is $mathbb{APX}$-hard, and give a constant factor approximation for LADR.
Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. In this paper, we close this gap by giving almost tight hardness results for these problems. 1. We show that Vector Bin Packing has no polynomial time $Omega( log d)$ factor asymptotic approximation algorithm when $d$ is a large constant, assuming $textsf{P} eq textsf{NP}$. This matches the $ln d + O(1)$ factor approximation algorithms (Chekuri, Khanna SICOMP 2004, Bansal, Caprara, Sviridenko SICOMP 2009, Bansal, Eli{a}s, Khan SODA 2016) upto constants. 2. We show that Vector Scheduling has no polynomial time algorithm with an approximation ratio of $Omegaleft( (log d)^{1-epsilon}right)$ when $d$ is part of the input, assuming $textsf{NP} subseteq textsf{ZPTIME}left( n^{(log n)^{O(1)}}right)$. This almost matches the $Oleft( frac{log d}{log log d}right)$ factor algorithms(Harris, Srinivasan JACM 2019, Im, Kell, Kulkarni, Panigrahi SICOMP 2019). We also show that the problem is NP-hard to approximate within $(log log d)^{omega(1)}$. 3. We show that Vector Bin Covering is NP-hard to approximate within $Omegaleft( frac{log d}{log log d}right)$ when $d$ is part of the input, almost matching the $O(log d)$ factor algorithm (Alon et al., Algorithmica 1998). Previously, no hardness results that grow with $d$ were known for Vector Scheduling and Vector Bin Covering when $d$ is part of the input and for Vector Bin Packing when $d$ is a fixed constant.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
