Algorithms Core 15-750  PROBLEM SET # 4  Spring 1999

DUE: 1:00PM Wednesday March 17 1999

1 The off-line k-server problem

In the k-server problem we have an edge-weighted graph G and k servers each server is located at a node of the graph, we may have more than one server at a node. At each time interval we get a request from a subset of s ≤ k nodes of G for a server. We must move s servers to each node that request a server. We may also move other servers to new nodes in anticipation of later requests. The cost to move a server from node v, were it is, to a new node w is equal to the min-cost path from v to w in G. In the off-line version of the problem we are given all the request ahead of time we must simply find the min-cost strategy to handle all the request at the requested times.

Problem 1.1 Show how to reduce the off-line k-server problem to a min-cost max-flow problem of size at most O(n · t) nodes and O(n^{2} · t) edges.

2 Maximum Flow for Negative Capacities

In lecture we considered the case when all capacities are nonnegative. Suppose we would like to find a maximum flow where the flow on some edge (u, v) is in the interval [2, 3], that is, the flow is at least 2 but no more than 3. We can model this by setting the capacity of (u, v) to 3 and the capacity of (v, u) to −2.

Problem 2.1 Show how to reduce the problem of maximum flow with possibly negative capacities to two maximum flow problems both with nonnegative capacities.

3 Maximum Planar Flow

In this problem we consider the Max-Flow problem where the flow graph is planar. We first consider a simpler problem, we say that G is a circulation graph if it has arc capacities c, in general c may be negative. A circulation graph has no source or sink. A circulation of G is a feasible flow on G.

A natural dual problem is finding potential functions. A potential graph is a graph G = (V, E) plus assignment of a weight w(e) to each arc of G, in general, the weights may be negative. A function p which assigns a real value to each node of G is a potential function for G if w(u, v) ≥ p(v) − p(u).

We first show there is a very nice relationship between flows in G and potential functions on G^{∗} the geometric dual of G. Given an arc e in G the dual of e, denoted e^{∗} is the arc in G^{∗} from the face right of e to the face left of e.

Problem 3.1 Show how that a planar circulation graph G has a circulation if and only if the dual G^{∗} has a potential function, where w(e^{∗}) = c(e).

Problem 3.2 Show how to find a maximum flow in a planar flow graph in O(n log n) time when the capacities are nonnegative and the only source and only sink lie on the same face.

Problem 3.3 Show how to find a flow of some fixed size in a planar flow graph in O(n^{1.5}) time when there is only one source and only one sink.

You may use the fact that single source shortest paths can be found in a planar graph in O(n^{1.5}) time.

4 Making a Palindrome

Suppose we have n words W where the longest word has length l. Give an O(l^{2}n^{2}) time algorithm to determine if we can form a palindrome using words in W. You are allowed to uses the same word more than once.

Hint: Try solving this problem on your own. But if after some time you have not found a solution come by and we can give you a hint.