Homework 5

Problem 1.

Let \(G=(V,E)\) be a directed graph, let \(u,v,w\) be three distinct nodes in \(G\), and let \(k > 1\). Give a three-line argument to prove the following claim: If there are \(k\) edge-disjoint paths from \(u\) to \(v\), and there are \(k\) edge-disjoint paths from \(v\) to \(w\), then there are \(k\) edge-disjoint paths from \(u\) to \(w\).

Problem 2.

Give the dual of the following linear program.
\[ \begin{array}{rrl} \textrm{maximize} & 4x_1+x_2 +5x_3+3x_4& \\ \textrm{such that} & x_1-x_2-x_3+3x_4 & \le 1\\ & 5x_1+x_2+3x_3+8x_4 & \le 55\\ & -x_1+2x_2+3x_3-5x_4 & \le 3\\ & x_1,x_2,x_3x_4 & \ge 0 \end{array} \]

Problem 3.

A restaurant has 880 abalones and 720 oysters. They offer two dishes: A dish for 20,000 Won (4 abalones, 1 oyster), and a dish for 15,000 Won (2 abalones, 3 oysters).

Formulate a linear program to determine the optimal number of the two dishes to be sold.

Give the dual of the linear program. Can you give an interpretation of the variables, constraints, and objective function?

Problem 4.

You are given the universe \(U = \{1, 2, 3, \ldots, n\}\), and a family \(\mathcal{F} = \{B_1, B_2, \ldots, B_m\}\) of \(m\) subsets of \(U\). Each element \(i \in U\) has a weight \(w_i \geq 0\). Your goal is to find a subset \(A \subseteq U\) that contains an element of every \(B_j \in \mathcal{F}\), and you want the total weight \(w(A) = \sum_{i \in A}w_i\) to be as small as possible.

Let \(b = \max_{j} |B_{j}|\) denote the maximum size (number of elements) of any of the sets \(B_1, B_2, \ldots, B_{m}\). Give a polynomial time approximation algorithm for this problem that finds a set \(A\) whose weight is at most \(b\) times the minimum possible weight (in other words, your algorithm must be a \(b\)-approximation).

Problem 5.

Your company has a supplier providing aluminium bars of length 3.00m. You use those bars to provide pieces for window elements. Today, you have received an order for 300 pieces of length 0.50m, 130 pieces of length 1.00m, and 100 pieces of length 1.20m. How many bars of 3.00m length do you need to order from your supplier to make these pieces? (Note that any leftover aluminium from cutting a bar cannot be reused, so we really want to minimize the number of bars.)

Model this problem as a linear program. Clearly explain the meaning of your variables and constraints.

(You will have to hope the solution to the LP has integer values—ignore this issue.)