Skip to main content

All Questions

Filter by
Sorted by
Tagged with
7 votes
2 answers
242 views

Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$

Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds: $$ \langle x_k, \theta_k \rangle &...
Alireza Bakhtiari's user avatar
2 votes
0 answers
76 views

Polyhedron coordinate bound

Given a polyhedron $$Ax\leq b$$ where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
Turbo's user avatar
  • 13.9k