12
votes
Accepted
Checking equivalence of two polytopes
I cannot say for sure if you will consider the following approach as better, but from a complexity-theoretic point of view there is a more efficient solution. The idea is to rephrase your question in ...
- 371
7
votes
Accepted
Does Horn SAT (Horn formula in CNF) have an integral polytope?
EDIT: Strengthened Theorem 2.
The answer to the problem as posed is no, unless P=NP:
Theorem 1. Unless P=NP, there is no LP polytope for Horn-SAT that has only integer extreme points and is ...
- 9,595
6
votes
Reaching the double exponential upper bound in Fourier-Motzkin elimination
I think this upper bound is tight. As an example, consider the following system
\begin{align*}
+x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le 0 \\
+x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2 \le ...
6
votes
Accepted
Complexity of Finding Largest Set of Intersecting Convex Polytopes
Suppose that the dimension $d$ of the Euclidean space is fixed, and that the input consists of $n$ convex polytopes in $\mathbb{R}^d$ that altogether have $p$ facets.
Let $h_1,\ldots,h_p$ denote the ...
- 5,772
5
votes
Decide whether a point is a vertex of a polytope?
This answer expands on Chandra's comment, and on my follow up comment. The problem is indeed solvable in polynomial time. More general versions of it are also solvable in polynomial time: $\Theta$ ...
- 18.1k
5
votes
Checking equivalence of two polytopes
The fact that the underlying polytope $Ax \le b$ is the same for $P_1$ and $P_2$ does not matter, unless we know something specific about $A$ and $b$. This is because a general polytope is an affine ...
- 377
4
votes
Accepted
Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?
Edit 2: Embarrassingly, there is a two line proof of the $NP$-hardness, if one starts with the right polytope.
First, recall the circulation polytope of a graph on the bottom of page 4 of Generating ...
- 1,439
3
votes
Accepted
Properties of convex polytope of 0-1 matrices
Sasho already gave you a yes/no answer, but here's an actual convex combination for you: If $B_\ell$ is the $k \times k$ matrix which is $1$ when $|S_i \cap S_j| \ge \ell$ and zero otherwise, then $M =...
- 1,429
2
votes
Accepted
Hardness of computing the dimension of an integral polytope?
Yes, MORE-SAT, defined below, is one example of a combinatorial optimization problem for which the natural 0/1 integer linear program (ILP) is guaranteed to be feasible, and determining the dimension ...
- 9,595
2
votes
Accepted
On polytope lattice points
Let's just take the reduction from SAT to IP and see if it works. For a 3-CNF $\phi$, define a polytope $P$ which contains all $x \in \mathbb{R}^n$ satisfying the constraints
$0\le x_i \le 1$ for all ...
- 18.1k
2
votes
Accepted
Reference needed for lower bound on number of guards in three-dimensional art gallery guarding
To my knowledge, Seidel's construction has only been published in O'Rourke's book and nowhere else.
In one of his papers, Seidel even refers to O'Rourke's book for a description of his own ...
- 5,772
Only top scored, non community-wiki answers of a minimum length are eligible