- Given a directed graph, where each edge $e$ has a capacity $u_e$, and designated nodes $s,t$, let the widest path problem be the problem of finding a path from $s$ to $t$ maximizing the minimum capacity, i.e., $\max \min_{e \in P} u_e$.
Give an algorithm for widest path of the same complexity as Dijkstra, and briefly explain its differences from Dijkstra.
-
Suppose $n$ families $F_1,...,F_n$ go out to dinner, and they all have to be seated at tables in the restaurant. Each family $F_i$ consists of family members $f_i^1,...,f_i^{|F_i|}$. Unfortunately, the members of each family all despise one another, so, for each family $F_i$, we want all its members to end up at different tables. There's a finite set of tables $T_1,...,T_m$, and each table $T_j$ has some capacity $|T_j|$.
Show (mostly by picture) how to solve the problem of finding such an assignment of people to tables by reduction to max flow.
-
Given an unweighted, undirected graph $G$, where nodes are people and edges are friendship, the friendliest subgraph problem is the problem of finding an induced subgraph $H$ of $G$ maximizing $|E_H|/|V_H|$. (Recall that an induced subgraph is fully specified by its vertex set: whenever $u,v \in V_H$ and $(u,v) \in E_G$, this means $(u,v) \in E_H$.)
Show that friendliest subgraph can be solved by reduction to max flow.
-
Consider the following production planning problem. You're in the widget business, and each month $i$, $1 \le i \le 12$, you need to supply $d_i$ widgets to your customers, who will pay $p_i$ apiece for them. In each month you can buy them from your suppliers at cost $c_i$ apiece. You can store at most $B$ widgets in the warehouse from one month to the next. You begin the year with no widgets, and you benefit from maintaining any supply past the end of the year.
How can you solve this problem?
-
Let a cycle cover be vertex disjoint collection of cycles, where every node is included in some cycle. Given a graph $G$ with edge weights $c_e$, the min-weight cycle cover problem is...the problem of finding a cycle cover of minimum total weight. To ensure feasibility, assume that every node $v$ has a self-loop $(v,v)$ with some weight $c_{(v,v)}$, in which case an isolated node counts as a trivial cycle, though perhaps a costly one.
Show that min-cost cycle cover can be solved by reduction to the assignment problem (i.e., min-cost bipartite perfect matching).