Linear-inequality feasibility. Given a set of m linear inequalities on n variabl

Question

Linear-inequality feasibility. Given a set of m linear inequalities on
n variables x1 , x2 , . . . , xn , the linear inequality feasibility problem asks
whether there is a setting of the variables that simultaneously satisfies each
of the inequalities.

(a) Show that if we have an algorithm for linear programming, we can
use it to solve a linear-inequality feasibility problem. The number
of variables and constraints that you use in the linear-programming
problem should be polynomial in n and m.

(b) Show that if we have an algorithm for the linear-inequality feasibility
problem, we can use it to solve a linear-programming problem. The
number of variables and linear inequalities that you use in the linear-
inequality feasibility problem should be polynomial in n and m, the
number of variables and constraints in the linear program.

Explanation / Answer

(b)

Solution:

In Linear Program, if n represents variables and m represents constraints and those are converted into standard forms.

In standard form each constraint can be express like it must be less than or equal to

Constraint.

Thus the linear program is converted into standard form are 2n ,2m.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.