15

No, even if there is a finite number of feasible rank-1 matrices, the feasible region of an SDP does not have to be polyhedral. A spectrahedron you see all the time in applications is $S_n = \{X: X \succeq 0, X_{11} = \ldots = X_{nn} = 1\}$, i.e. the set of Gram matrices of $n$ unit vectors. This is, for example, the feasible region for the Goemans-...


12

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 the first-order theory of the rationals with addition and order. You have that $P_1$ is included in $P_2$ if and only if \begin{align*} \Phi := \forall \vec{x}....


8

No. Suppose all $a_i$'s are $0$ and all your $b_i$'s are equal; then the polytopes you can get by varying the $b_i$'s are essentially the hypersimplices. But the number of vertices of an $n$-dimensional hypersimplex can be any binomial coefficient $\binom{n}{k}$. In particular choosing $k=n/2$ gives an exponential number of extreme points.


6

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 0 \\ +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 0 \\ -x_0 & +\frac{1}{2} x_1 +\frac{1}{4} ...


6

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 supporting hyperplanes for the $p$ facets of the input polytopes. The arrangement of $h_1,\ldots,h_p$ is the decomposition of $\mathbb{R}^d$ into connected open ...


6

Check out https://www.math.ucdavis.edu/~latte/ and the corresponding paper Effective lattice point counting in rational convex polytopes. Jesús A. De Loera, Raymond Hemmecke, Jeremiah Tauzer, Ruriko Yoshida. Journal of Symbolic Computation 2004 38:4, 1273-1302. The algorithm they implement was introduced in A Polynomial Time Algorithm for Counting ...


6

I think $S_n$ can be written in terms of inequalities in the obvious way. Let $$ Q_n = \{(x, y): x = \sum_{i = 0}^{n-1}{2^i y_i}, \forall i: 0 \leq y_i \leq 1\}. $$ I claim that $Q_n = S_n$. First, obviously all $(x, y) \in S_n$ are also in $Q_n$, so $S_n \subseteq Q_n$. Second, fix a point $(x^*, y^*) \in Q_n$. Consider the probability distribution over $\{...


5

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$ could be given by a separation oracle, rather than explicitly, and it is also possible to solve an appropriately formulated version for a polyhedron. Observe ...


5

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 projection of a simplex (see, for instance, Ziegler's "Lectures for Polytopes", Theorem 2.15). Thus, if $A$ and $b$ encode a simplex, your question is equivalent ...


4

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 all vertices of a polyhedron is hard. It's vertices are in bijective correspondence with the directed simple cycles. Therefore, they are hard to sample or ...


4

As far as I know, the parameterized complexity of the counting problem is still open. It is known that ILP solving is fixed-parameter tractable in the number of variables ('Integer programming with a fixed number of variables', H.W.Lenstra Jr), although ILP solution counting is expected to be $\# W[1]$-hard. The question was first asked by N. Betzler if my ...


3

Beside Latte, there is a less famous tool, called Barvinok (name of the original author of the algorithm): http://freecode.com/projects/barvinok The algorithm is described in this paper: Sven Verdoolaege, Rachid Seghir, Kristof Beyls, Vincent Loechner, Maurice Bruynooghe: Counting Integer Points in Parametric Polytopes Using Barvinok's Rational Functions....


3

Your question is related to how to represent the geometric intersection objects. Pairwise comparisons can get a geometric intersection graph, however, the problem is that two objects are possibly not close to each other in this intersection graph, even originally their geometric distance is very short. So it is easy to find counterexamples for the specific ...


3

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 = \sum_{\ell=1}^{n'} \frac{1}{n'} B_\ell$.


2

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 $i$, clause constraints for any clause $C$ of $\phi$: for example if $C = x_i \vee \bar{x}_j \vee x_k$ put the constraint $x_i + 1-x_j + x_k \ge 1$. (I trust ...


2

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 construction. He writes on top of page 253 of his joint paper with Jim Ruppert: "In his book [9, p. 255] O'Rourke describes n-vertex three-dimensional polyhedra that ...


2

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 sets of $G$. The graphs $G$ for which the non-trivial facets of $P(V(G),\mathcal{S}(G))$ (i.e the stable polytope) are all rank-facets are called rank-perfect ...


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