Practice problem set #5 Solution

$30.00

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.

  1. 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. 3x1 + 2x2 5x3 8

Can you solve this problem with a linear program? If so, how?

  1. PDV 7.5

  1. Please formulate the unbounded knapsack problem into a linear program.

  1. 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