Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment
202
0
0.0
(
0
)
Added by
Santanu Bhowmick
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We consider variants of the following multi-covering problem with disks. We are given two point sets $Y$ (servers) and $X$ (clients) in the plane, a coverage function $kappa :X rightarrow mathcal{N}$, and a constant $alpha geq 1$. Centered at each server is a single disk whose radius we are free to set. The requirement is that each client $x in X$ be covered by at least $kappa(x)$ of the server disks. The objective function we wish to minimize is the sum of the $alpha$-th powers of the disk radii. We present a polynomial time algorithm for this problem achieving an $O(1)$ approximation.
The problem of vertex guarding a simple polygon was first studied by Subir K. Ghosh (1987), who presented a polynomial-time $O(log n)$-approximation algorithm for placing as few guards as possible at vertices of a simple $n$-gon $P$, such that every point in $P$ is visible to at least one of the guards. Ghosh also conjectured that this problem admits a polynomial-time algorithm with constant approximation ratio. Due to the centrality of guarding problems in the field of computational geometry, much effort has been invested throughout the years in trying to resolve this conjecture. Despite some progress (surveyed below), the conjecture remains unresolved to date. In this paper, we confirm the conjecture for the important case of weakly visible polygons, by presenting a $(2+varepsilon)$-approximation algorithm for guarding such a polygon using vertex guards. A simple polygon $P$ is weakly visible if it has an edge $e$, such that every point in $P$ is visible from some point on $e$. We also present a $(2+varepsilon)$-approximation algorithm for guarding a weakly visible polygon $P$, where guards may be placed anywhere on $P$s boundary (except in the interior of the edge $e$). Finally, we present a $3c$-approximation algorithm for vertex guarding a polygon $P$ that is weakly visible from a chord, given a subset $G$ of $P$s vertices that guards $P$s boundary whose size is bounded by $c$ times the size of a minimum such subset. Our algorithms are based on an in-depth analysis of the geometric properties of the regions that remain unguarded after placing guards at the vertices to guard the polygons boundary. It is plausible that our results will enable Bhattacharya et al. to complete their grand attempt to prove the original conjecture, as their approach is based on partitioning the underlying simple polygon into a hierarchy of weakly visible polygons.
MAX CLIQUE problem (MCP) is an NPO problem, which asks to find the largest complete sub-graph in a graph $G, G = (V, E)$ (directed or undirected). MCP is well known to be $NP-Hard$ to approximate in polynomial time with an approximation ratio of $1 + epsilon$, for every $epsilon > 0$ [9] (and even a polynomial time approximation algorithm with a ratio $n^{1 - epsilon}$ has been conjectured to be non-existent [2] for MCP). Up to this date, the best known approximation ratio for MCP of a polynomial time algorithm is $O(n(log_2(log_2(n)))^2 / (log_2(n))^3)$ given by Feige [1]. In this paper, we show that MCP can be approximated with a constant factor in polynomial time through approximation ratio preserving reductions from MCP to MAX DNF and from MAX DNF to MIN SAT. A 2-approximation algorithm for MIN SAT was presented in [6]. An approximation ratio preserving reduction from MIN SAT to min vertex cover improves the approximation ratio to $2 - Theta(1/ sqrt{n})$ [10]. Hence we prove false the infamous conjecture, which argues that there cannot be a polynomial time algorithm for MCP with an approximation ratio of any constant factor.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
