Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStabbing Planes
128
0
0.0
(
0
)
Added by
Noah Fleming
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by branching on an inequality and its integer negation. That is, we can (nondeterministically choose) a hyperplane a x geq b with integer coefficients, which partitions the polytope into three pieces: the points in the polytope satisfying a x geq b, the points satisfying a x leq b-1, and the middle slab b-1 < a x < b. Since the middle slab contains no integer points it can be safely discarded, and the algorithm proceeds recursively on the other two branches. Each path terminates when the current polytope is empty, which is polynomial-time checkable. Among our results, we show somewhat surprisingly that Stabbing Planes can efficiently simulate Cutting Planes, and moreover, is strictly stronger than Cutting Planes under a reasonable conjecture. We prove linear lower bounds on the rank of Stabbing Planes refutations, by adapting a lifting argument in communication complexity.
rate research
Read More
The random k-SAT model is the most important and well-studied distribution over k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for satisfiability algorithms, and average-case hardness over this distribution has also been linked to hardness of approximation via Feiges hypothesis. We prove that any Cutting Planes refutation for random k-SAT requires exponential size, for k that is logarithmic in the number of variables, in the (interesting) regime where the number of clauses guarantees that the formula is unsatisfiable with high probability.
It is well known that any graph admits a crossing-free straight-line drawing in $mathbb{R}^3$ and that any planar graph admits the same even in $mathbb{R}^2$. For a graph $G$ and $d in {2,3}$, let $rho^1_d(G)$ denote the minimum number of lines in $mathbb{R}^d$ that together can cover all edges of a drawing of $G$. For $d=2$, $G$ must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results. - For $din{2,3}$, we prove that deciding whether $rho^1_d(G)le k$ for a given graph $G$ and integer $k$ is ${existsmathbb{R}}$-complete. - Since $mathrm{NP}subseteq{existsmathbb{R}}$, deciding $rho^1_d(G)le k$ is NP-hard for $din{2,3}$. On the positive side, we show that the problem is fixed-parameter tractable with respect to $k$. - Since ${existsmathbb{R}}subseteqmathrm{PSPACE}$, both $rho^1_2(G)$ and $rho^1_3(G)$ are computable in polynomial space. On the negative side, we show that drawings that are optimal with respect to $rho^1_2$ or $rho^1_3$ sometimes require irrational coordinates. - Let $rho^2_3(G)$ be the minimum number of planes in $mathbb{R}^3$ needed to cover a straight-line drawing of a graph $G$. We prove that deciding whether $rho^2_3(G)le k$ is NP-hard for any fixed $k ge 2$. Hence, the problem is not fixed-parameter tractable with respect to $k$ unless $mathrm{P}=mathrm{NP}$.
In their seminal work, Danzer (1956, 1986) and Stach{o} (1981) established that every set of pairwise intersecting disks in the plane can be stabbed by four points. However, both these proofs are non-constructive, at least in the sense that they do not seem to imply an efficient algorithm for finding the stabbing points, given such a set of disks $D$. Recently, Har-Peled etal (2018) presented a relatively simple linear-time algorithm for finding five points that stab $D$. We present an alternative proof (and the first in English) to the assertion that four points are sufficient to stab $D$. Moreover, our proof is constructive and provides a simple linear-time algorithm for finding the stabbing points. As a warmup, we present a nearly-trivial liner-time algorithm with an elementary proof for finding five points that stab $D$.
Let $P subseteq mathbb{R}^2$ be a set of points and $T$ be a spanning tree of $P$. The emph{stabbing number} of $T$ is the maximum number of intersections any line in the plane determines with the edges of $T$. The emph{tree stabbing number} of $P$ is the minimum stabbing number of any spanning tree of $P$. We prove that the tree stabbing number is not a monotone parameter, i.e., there exist point sets $P subsetneq P$ such that treestab{$P$} $>$ treestab{$P$}, answering a question by Eppstein cite[Open Problem~17.5]{eppstein_2018}.
It is known that for every dimension $dge 2$ and every $k<d$ there exists a constant $c_{d,k}>0$ such that for every $n$-point set $Xsubset mathbb R^d$ there exists a $k$-flat that intersects at least $c_{d,k} n^{d+1-k} - o(n^{d+1-k})$ of the $(d-k)$-dimensional simplices spanned by $X$. However, the optimal values of the constants $c_{d,k}$ are mostly unknown. The case $k=0$ (stabbing by a point) has received a great deal of attention. In this paper we focus on the case $k=1$ (stabbing by a line). Specifically, we try to determine the upper bounds yielded by two point sets, known as the stretched grid and the stretched diagonal. Even though the calculations are independent of $n$, they are still very complicated, so we resort to analytical and numerical software methods. We provide strong evidence that, surprisingly, for $d=4,5,6$ the stretched grid yields better bounds than the stretched diagonal (unlike for all cases $k=0$ and for the case $(d,k)=(3,1)$, in which both point sets yield the same bound). Our experiments indicate that the stretched grid yields $c_{4,1}leq 0.00457936$, $c_{5,1}leq 0.000405335$, and $c_{6,1}leq 0.0000291323$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
