# Tag Info

## Hot answers tagged polytope

15 votes
Accepted

• 1,419
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 ...
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,722
2 votes
Accepted

### When are all facets rank facets? (for independence system polyhedra)

On (1): The case of stable sets in graphs may clarify the situation (a stable set of a graph is a set of pairwise non-adjacent vertices). For each graph $G$, let $\mathcal{S}(G)$ be the set of stable ...
• 36
1 vote
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 ...
• 8,273

Only top scored, non community-wiki answers of a minimum length are eligible