# 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.)