[OT] Retreating from Iraq

[Russell Lewis]

-3.2 seconds.  It will be on the Drudge Report before the president 
picks up the phone.

Seriously, though, the algorithm is as follows:

- Give each private a "cost" of 0, since he has no calls to make
- Iterate through the list of superiors, starting with the lowest
   level and working upwards:
   - Sort the superior's subordinates by their cost, from greatest
     cost to least.
   - The superior will plan to call his subordinates in this order
   - The "cost" of the superior is equal to
        max (over subordinates si) i + cost(si)
     That is, each term in the max() is teh cost of the subordinate,
     plus his order in the list.  The total cost of this superior is
     the time from when he makes his first call, until the last
     private in his tree is notified.

This works because of two points:
1) The cost of a given officer notifying his tree doesn't depend on
    his upper heirarchy.  Thus, we can build the values from bottom up.
2) If an officer calls any high-cost subordinate after any lower-cost
    subordinate, then that obviously will make the tree finish later
    than in my suggested order.

Russ

Andrei Alexandrescu wrote:
> Russell Lewis wrote:
>> If every superior uses a conference call to talk to his subordinates, 
>> then the news propagates exactly proportional to the depth of the 
>> heirarchy.
>>
>> :)
>>
>> Of course, if he has to call all of his subordinates in sequence, then 
>> things are different...but in that case, we need a measurement for 
>> "fast."  Are we looking for an algorithm that provides the lowest 
>> possible maximum time, lowest average, or something else?
> 
> Time from the president lifting the phone to the time the last private 
> hears it.
> 
> Andrei
>