More Network Flow

1. Kleinberg, Jon. Algorithm Design (p .416 q. 6) . Suppose you’re a consultant for the Ergonomic Architec- ture Commission, and they come to you with the following problem.

They’re really concerned about designing houses that are“user-friendly”, and they’ve been having a lot of trouble with the setup of light fixtures and switches in newly designed houses. Consider, for example, a one-floor house with n light fixtures and n locations for light switches mounted in the wall. You’d like to be able to wire up one switch to control each light fixture, in such a way that a person at the switch can see the light fixture being controlled.

Figure 1:  The floor plan in (a) is ergonomic, because we can wire switches to fixtures in such a way that each fixture is visible from the switch that controls it.  (This can be done by wiring switch 1 to a, switch 2 to b, and switch 3 to c.) The floor plan in (b) is not ergonomic, because no such wiring is possible.

Sometimes this is possible and sometimes it isn’t.  Consider the two simple floor plans for houses in Figure 1.   There are three light fixtures (labelled a,b,c) and three switches (labelled 1, 2, 3).  It is possible to wire switches to fixtures in Figure 1(a) so that every switch has a line of sight to the fixture, but this is not possible in Figure 1(b).

Let’s call a floor plan, together with n light fixture locations and n switch locations, ergonomic if it’s possible to wire one switch to each fixture so that every fixture is visible from the switch that controls it. A floor plan will be represented by a set of m horizontal or vertical line segments in the plane (the walls), where the i-th wall has endpoints (xi ,yi ), (x,y).  Each of the n switches and each of the n fixtures is given by its coordinates in the plane. A fixture is visible from a switch if the line segment joining them does not cross any of the walls.

Give an algorithm to decide if a given floor plan is ergonomic. The running time should be polynomial in m and n.  You may assume that you have a subroutine with O(1) running time that takes two line segments as input and decides whether or not they cross in the plane.

Each of the balloons is produced by one of three different subcontractors involved in the experiment. A requirement of the experiment is that there be no condition for which all k measurements come from balloons produced by a single subcontractor.

Explain how to modify your polynomial-time algorithm for part (a) into a new algorithm that decides whether there exists a solution satisfying all the conditions from (a), plus the new requirement about subcontractors.

3. Kleinberg, Jon. Algorithm Design (p .442, q.41) .

Suppose you’re managing a collection of k processors and must schedule a sequence of m jobs over n time steps.

The jobs have the following characteristics. Each job j has an arrival time aj  when it is first available for processing, a length ℓj  which indicates how much processing time it needs, and a deadline dj  by which it must be finished.  (We’ll assume 0 < ℓj   ≤ dj  − aj .)  Each job can be run on any of the processors, but only on one at a time; it can also be preempted and resumed from where it left off (possibly after a delay) on another processor.

Moreover, the collection of processors is not entirely static either: You have an overall pool of k possible processors; but for each processor i, there is an interval of time [ti ,t ] during which it is available; it is unavailable at all other times.

Given all this data about job requirements and processor availability, you’d like to decide whether the jobs can all be completed or not. Give a polynomial-time (in k , m, and n) algorithm that either produces a schedule completing all jobs by their deadlines or reports (correctly) that no such schedule exists. You may assume that all the parameters associated with the problem are integers.

Example.   Suppose we have two jobs J1  and J2 .  J1  arrives at time 0, is due at time 4, and has length 3.  J2 arrives at time 1, is due at time 3, and has length 2.  We also have two processors P1  and P2 .  P1  is available between times 0 and 4; P2  is available between times 2 and 3.  In this case, there is a schedule that gets both jobs done.

•  At time 0, we start job J1  on processor P1 .

•  At time 1, we preempt J1  to start J2  on P1 .

•  At time 2, we resume J1  on P2 . (J2  continues processing on P1 .)

•  At time 3, J2  completes by its deadline.  P2  ceases to be available, so we move J1  back to P1  to finish its remaining one unit of processing there.

•  At time 4,  J1   completes its processing on P1 .   Notice that there is no solution that does not involve preemption and moving of jobs.

4. Kleinberg, Jon. Algorithm Design (p .444, q.45) .

Consider the following definition. We are given a set of n countries that are engaged in trade with one another. For each country i, we have the value si  of its budget surplus; this number may be positive or negative, with a negative number indicating a deficit. For each pair of countries i,j, we have the total value eij  of all exports from i to j; this number is always nonnegative.  We say that a subset S of the countries is free-standing if the sum of the budget surpluses of the countries in S , minus the total value of all exports from countries in S to countries not in S , is nonnegative. Give a polynomial-time algorithm that takes this data for a set of n countries and decides whether it contains a nonempty free-standing subset that is not equal to the full set.