0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ one has to be careful with what $R$ is. Can you do efficient arithmetic in $R$ ? Typically one takes $R=\mathbb{Q}$. $\endgroup$
    – Dima Pasechnik
    Commented Jul 5, 2021 at 6:53
  • $\begingroup$ I just consider real numbers in this problem, thus we can reduce the problem to linear programming. $\endgroup$
    – Inner_peace
    Commented Jul 8, 2021 at 2:57

1 Answer 1

Reset to default
3
$\begingroup$

The extra constraint corresponds to including an additional row in $A$ and another entry in $b$. So it is still standard form, with $m$ replaced with $m+1$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your answer. I agree that this form with the extra constraint can be reduced to the standard form. How about the inverse? If there is no reduction for the inverse, then it means there could be some easier method than linear programming. $\endgroup$
    – Inner_peace
    Commented Jul 8, 2021 at 2:50
  • $\begingroup$ as you can multiply variables by arbitrary positive numbers, what you ask is whether having in $A$ a row with positive entries might give you a faster algorithm. Even more generally, as you can replace rows of $A$ by arbitrary linear combinations, you ask whether the property of $A$ to have an all-positive linear combination of rows might lead to a faster algorithm. $\endgroup$
    – Dima Pasechnik
    Commented Jul 8, 2021 at 11:40
  • $\begingroup$ @DimaPasechnik Thanks for your explanation! You give a more general statement of this problem. $\endgroup$
    – Inner_peace
    Commented Jul 8, 2021 at 12:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.