Description
This problem set covers linear programming and reduction.
1. Consider the problem PDV 7.1, please reduce the linear problem to a di erent form of linear program in which all variables must non-negative, the constraints are all equations, and the objective is to be minimized.
2. Consider the following problem:
max x1 + x2 s.t. jx1 x2j 10
Can you solve this problem with a linear program? If so, how?
3. Consider the following problem:
min maxfx1; x2; x3g s.t. 3×1 + 2×2 5×3 8
Can you solve this problem with a linear program? If so, how?
4. PDV 7.5
5. Please formulate the unbounded knapsack problem into a linear program.
6. Consider the following two problems.
In the hitting set problem, we are given a family of sets fS1; S2; :::; Sng and a budget b, and we wish to nd if there exists a set H of size b that intersects every Si.
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
