$30.00
Description
This problem set covers linear programming and reduction.

Consider the problem PDV 7.1, please reduce the linear problem to a di erent form of linear program in which all variables must nonnegative, the constraints are all equations, and the objective is to be minimized.

Consider the following problem:
max x_{1} + x_{2} s.t. jx_{1} x_{2}j 10
Can you solve this problem with a linear program? If so, how?
3. Consider the following problem:
min maxfx_{1}; x_{2}; x_{3}g s.t. 3x_{1} + 2x_{2} 5x_{3} 8
Can you solve this problem with a linear program? If so, how?

PDV 7.5

Please formulate the unbounded knapsack problem into a linear program.

Consider the following two problems.
In the hitting set problem, we are given a family of sets fS_{1}; S_{2}; :::; S_{n}g and a budget b, and we wish to nd if there exists a set H of size b that intersects every S_{i}.
In the vertex cover problem, we are given a graph G = (V; E) and a budget b, and we wish to nd if there exists a vertex cover S of size b such that S touches every edge in E.
Show that the vertex cover problem can be reduced to the hitting set problem.
1