# Questions tagged [polytope]

The tag has no usage guidance.

24 questions
Filter by
Sorted by
Tagged with
717 views

### Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

I have a polytope $P$ defined by $\{ x : Ax \leq b, x \geq 0\}$ . Question: Given a vertex $v$ of $P$, is there a polynomial time algorithm to uniformly sample from the neighbors of $v$ in the graph ...
1k views

71 views

### Check whether a point is a vertex of Minkowski sum of polytopes

Given $n$ polytopes \begin{align*} P_1&=\{(f^1_1(\vec{x}_1), \cdots, f^1_m(\vec{x}_1))\mid A_1\vec{x}_1\leq b_1\}\\ P_2&=\{(f^2_1(\vec{x}_2), \cdots, f^2_m(\vec{x}_2))\mid A_2\vec{x}_2\leq ...
94 views

### Properties of convex polytope of 0-1 matrices

Problem setting Consider a set $S = \big\{ 1,2,\cdots,n \big\}$. Now consider $k$ equal-sized subsets $S_i \subset S$ s.t of size $\big|S_i\big|=n' \;\forall i$. Consider a $k\times k$ matrix $M$ ...
97 views

### Is the edge cover polytope integral on graphs with self-loops?

It is well known that the edge cover polytope is integral on simple graphs. I am wondering whether this also holds for graphs with self-loops. Here is a Linear Relaxation of the edge cover polytope, ...
144 views

### On polytope lattice points

Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$. Denote $\mathcal P(a,c)$ to be the set of convex polytopes ...
107 views

### Hardness of computing the dimension of an integral polytope?

Given a set of linear inequalities $Ax \leq b$ let $P = \text{conv}\{x \in \{0,1\}^n \mid A x \leq b \}$ be the convex hull of all binary vectors that satisfy the given inequalities. I am interested ...
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 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 ...