Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinimum Scan Cover and Variants -- Theory and Experiments
73
0
0.0
(
0
)
Added by
Dominik Michael Krupke
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider a spectrum of geometric optimization problems motivated by contexts such as satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Costs, we are given a graph $G$ that is embedded in Euclidean space. The edges of $G$ need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex incurs some cost in terms of energy or rotation time that is proportional to the corresponding rotation angle. Our goal is to compute schedules that minimize the following objective functions: (i) in Minimum Makespan Scan Cover (MSC-MS), this is the time until all edges are scanned; (ii) in Minimum Total Energy Scan Cover (MSC-TE), the sum of all rotation angles; (iii) in Minimum Bottleneck Energy Scan Cover (MSC-BE), the maximum total rotation angle at one vertex. Previous theoretical work on MSC-MS revealed a close connection to graph coloring and the cut cover problem, leading to hardness and approximability results. In this paper, we present polynomial-time algorithms for 1D instances of MSC-TE and MSC-BE, but NP-hardness proofs for bipartite 2D instances. For bipartite graphs in 2D, we also give 2-approximation algorithms for both MSC-TE and MSC-BE. Most importantly, we provide a comprehensive study of practical methods for all three problems. We compare three different mixed-integer programming and two constraint programming approaches, and show how to compute provably optimal solutions for geometric instances with up to 300 edges. Additionally, we compare the performance of different meta-heuristics for even larger instances.
rate research
Read More
We provide a comprehensive study of a natural geometric optimization problem motivated by questions in the context of satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Costs (MSC), we are given a graph $G$ that is embedded in Euclidean space. The edges of $G$ need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan. We show that MSC is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in $Theta(log chi (G))$, while for 3D the minimum scan time is not upper bounded by $chi (G)$. We use this relationship to prove that the existence of a constant-factor approximation implies $P=NP$, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of $frac{3}{2}$, even for bipartite graphs; conversely, we present a $frac{9}{2}$-approximation algorithm for this scenario. Generally, we give an $O(c)$-approximation for $k$-colored graphs with $kleq chi(G)^c$. For general metric cost functions, we provide approximation algorithms whose performance guarantee depend on the arboricity of the graph.
Given a graph $G=(V,E)$, the dominating set problem asks for a minimum subset of vertices $Dsubseteq V$ such that every vertex $uin Vsetminus D$ is adjacent to at least one vertex $vin D$. That is, the set $D$ satisfies the condition that $|N[v]cap D|geq 1$ for each $vin V$, where $N[v]$ is the closed neighborhood of $v$. In this paper, we study two variants of the classical dominating set problem: $boldmath{k}$-tuple dominating set ($k$-DS) problem and Liars dominating set (LDS) problem, and obtain several algorithmic and hardness results. On the algorithmic side, we present a constant factor ($frac{11}{2}$)-approximation algorithm for the Liars dominating set problem on unit disk graphs. Then, we obtain a PTAS for the $boldmath{k}$-tuple dominating set problem on unit disk graphs. On the hardness side, we show a $Omega (n^2)$ bits lower bound for the space complexity of any (randomized) streaming algorithm for Liars dominating set problem as well as for the $boldmath{k}$-tuple dominating set problem. Furthermore, we prove that the Liars dominating set problem on bipartite graphs is W[2]-hard.
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.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
