Skip to main content
formatting, added tag
Link
YCor
  • 63.9k
  • 5
  • 187
  • 285

How hard is a Linearlinear programming with a bounded constraint?

Source Link

How hard is a Linear programming with a bounded constraint?

Background: I am reading Greg Kuperberg's answer to the question Deciding membership in a convex hull. I am thinking about the complexity of ''Deciding membership in a convex hull''.

Restate the problem ''Deciding membership in a convex hull'': Given points $u,v_1,…,v_n\in R^m$, decide if $u\in R^m$ is contained in the convex hull of $v_1,…,v_n$.

My Question: If I understand correctly, ''deciding membership in a convex hull'' is equivalent to check the feasibility of linear programming with a bounded feasible region which is

$Ax = b$ for $x_i\geq 0$ and $\sum_i x_i = 1$(or equal to a constant more than 0).

Let us say $Ax =b$ for $x\geq 0$ is standard linear programming. Then with an extra bounded constraint, how hard is this special linear programming? Is the complexity still the same as the standard form of linear programming?