The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [polytope]

The tag has no usage guidance.

23 questions
Filter by
Sorted by
Tagged with
119 views

### Is counting the total number of faces of a polytope $\#P$ hard?

Let $P$ be a polytope defined by $Ax = b, x \geq 0$. Question: What is the complexity of computing the total number of faces of $P$? I know counting vertices is $\# P$-complete, but this problem is ...
137 views

955 views

Consider a vector of variables $\vec{x}$, and a set of linear constraints specified by $A\vec{x}\leq b$. Furthermore, consider two polytopes \begin{align*} P_1&=\{(f_1(\vec{x}), \cdots, f_m(\... 1answer 275 views ### Vertices of a polytope Consider the polytope P=\{(x_1,x_2,...,x_n)\in \mathbb{R}^n| \sum_{i=1}^n x_i=1; 0\leq a_i\leq x_i\leq b_i, i=1,...,n\} where a_i and b_i are constant lower and upper bounds for x_i. Is it ... 1answer 185 views ### When are all facets rank facets? (for independence system polyhedra) Consider an independence system (E,\mathcal{I}), and the corresponding polytope: P(E,\mathcal{I}):=\operatorname{conv.hull}\{ x^S ~|~S\in \mathcal{I}\} where x^S \in \{0,1\}^E denotes the ... 1answer 435 views ### Is the feasible region of this SDP polyhedral? We have a semidefinite program (SDP) whose feasible region contains only a finite number of rank-1 matrices. Can we conclude that the feasible region of this SDP is polyhedral? We believe this to ... 0answers 142 views ### Computing diameter of a 3D polyhedron A polyhedron is given as a set of its vertex coordinates. Is it possible to find its diameter faster than O(n^2)? Or, maybe, some another common polyhedron representation would help fasten this? 3answers 249 views ### The number of integral points in a polytope Suppose we define a polytope with \mathbf{Ax} \leq \mathbf{b}  What is the best way to find/approximate the number of the integral points in the polytope? Update: how hard is the complexity ...
Let $G$ be a complete graph edge-colored with $k$ colors. We say that $G$ is Gallai-colored if no triangle is colored with three distinct colors. Fix a tuple of integers $c = (c_1,\ldots,c_k)$. We may ...
Consider the following set. $S_n =\{ (x,y) ~|~x \in \mathbb{Z}_+~\wedge~ y \in \{0,1\}^n ~\wedge~x=\sum_{i=0}^{n-1} 2^i y_i \}$ $S_n$ is a collection of pairs $(x,y)$, where $x$ is an integer ...