Skip to main content
Post Undeleted by Turbo
Post Deleted by Turbo
Post Undeleted by Turbo
Post Deleted by Turbo
added 17 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Consider polytopes

$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$ $$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$ $$B[z_{1},z_{2},z]'\leq c$$ having vertex count $v_1,v_2$ and $v$ respectively.

We eliminate $z_{1}$ to $z_{2}$ by Fourier Motzkin and get a new polyhedron $$C[x_{1,1},\dots,x_{2,m_2},z]'\leq\tilde c.$$

IsUnder what conditions do we have the number of vertices in the new polyhedron $\leq v_1v_2$ if $m_1=m_2$?

Consider polytopes

$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$ $$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$ $$B[z_{1},z_{2},z]'\leq c$$ having vertex count $v_1,v_2$ and $v$ respectively.

We eliminate $z_{1}$ to $z_{2}$ by Fourier Motzkin and get a new polyhedron $$C[x_{1,1},\dots,x_{2,m_2},z]'\leq\tilde c.$$

Is the number of vertices in the new polyhedron $\leq v_1v_2$ if $m_1=m_2$?

Consider polytopes

$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$ $$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$ $$B[z_{1},z_{2},z]'\leq c$$ having vertex count $v_1,v_2$ and $v$ respectively.

We eliminate $z_{1}$ to $z_{2}$ by Fourier Motzkin and get a new polyhedron $$C[x_{1,1},\dots,x_{2,m_2},z]'\leq\tilde c.$$

Under what conditions do we have the number of vertices in the new polyhedron $\leq v_1v_2$?

Post Undeleted by Turbo
Post Deleted by Turbo
Post Undeleted by Turbo
Post Deleted by Turbo
[Edit removed during grace period]
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Number of vertices in a polyhedron

Consider polytopes

$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$ $$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$ $$B[z_{1},z_{2},z]'\leq c$$ having vertex count $v_1,v_2$ and $v$ respectively.

We eliminate $z_{1}$ to $z_{2}$ by Fourier Motzkin and get a new polyhedron $$C[x_{1,1},\dots,x_{2,m_2},z]'\leq\tilde c.$$

Is the number of vertices in the new polyhedron $\leq v_1v_2$ if $m_1=m_2$?