One day, a while back, I was driving and I had a morbid idea. I asked myself a question- say you had a collection of cities with initial populations, which were experiencing a plague, causing a specific reduction in population per time step. Now, lets say you can 'cure' a city, and each city takes a given time period to cure, during which the population still drops in all uncured cities, but post cure, the population is stable. Given the disposition of initial populations, death rates and cure times, how can you decide on a treatment order to save the most people?

Like I said, macabre. Essentially, it's an abstract formalization of the triage problem. A less sad version is to imagine a bunch of leaky buckets, which have a spill rate, and take time to patch; but the disease version is the way it originally entered my head, and thus the terminology I use when thinking about the problem. Plus the sense of urgency adds to the conceptual weight of the problem. Perhaps if I teach one day, I'll use only macabre metaphors in word problems so as to draw students in to the utility of mathematics. Anyway.

Let's formalize this problem. For starters, we have n-many cities with initial populations Pi; Pi = {Pi1,Pi2,..Pin}. Additionally, each city has a death rate D = {d1,d2,...dn} and a cure time Q = {q1,q2,...qn} (Q for Qure, I guess; Don't judge me). Then, we can write the population of a given city j at some time t as Pj(t) = Pij - djt. If we know that city j has the cure process begun at time tjs, then we can write the total population saved due to intervention at this time as Psj = Pij - dj(tjs + qj). The goal is to maximize the total saved population: Ps = Ps1 + Ps2 + ... + Psn.

Now, looking at the expansion of this expression, we can see a very specific relation between the net loss, di, and qi:

Like I said, macabre. Essentially, it's an abstract formalization of the triage problem. A less sad version is to imagine a bunch of leaky buckets, which have a spill rate, and take time to patch; but the disease version is the way it originally entered my head, and thus the terminology I use when thinking about the problem. Plus the sense of urgency adds to the conceptual weight of the problem. Perhaps if I teach one day, I'll use only macabre metaphors in word problems so as to draw students in to the utility of mathematics. Anyway.

Let's formalize this problem. For starters, we have n-many cities with initial populations Pi; Pi = {Pi1,Pi2,..Pin}. Additionally, each city has a death rate D = {d1,d2,...dn} and a cure time Q = {q1,q2,...qn} (Q for Qure, I guess; Don't judge me). Then, we can write the population of a given city j at some time t as Pj(t) = Pij - djt. If we know that city j has the cure process begun at time tjs, then we can write the total population saved due to intervention at this time as Psj = Pij - dj(tjs + qj). The goal is to maximize the total saved population: Ps = Ps1 + Ps2 + ... + Psn.

Now, looking at the expansion of this expression, we can see a very specific relation between the net loss, di, and qi:

Examining this sum, we can see that dn is going to experience the greatest proliferation by total wait to triage, and that q1 will be the greatest influencing cure time. So then, we will naturally want to tend to minimize q1, and maximize dn. Unfortunately, qi and di are not independent, so we can't select their orderings to precisely reflect this desired ordering. However, we can constrict a new metric ratio ri = di/qi; which allows us to reflect these contradictory aims: by sorting a list of ri in descending order, we impose an ordering by which di tends to be relatively large and qi relatively small early on, and vice versa later in the sequence.

To make this policy a little more formal, let's consider a solution order Sr which is sorted by ri. Let's say we take two elements of this order, sk and sl, and switch their position, assuming rl < rk (sk precedes sl in the original order). We can lay out all terms which sum up in the total loss expression for the original order and the order with the swap, side by side, like so:

To make this policy a little more formal, let's consider a solution order Sr which is sorted by ri. Let's say we take two elements of this order, sk and sl, and switch their position, assuming rl < rk (sk precedes sl in the original order). We can lay out all terms which sum up in the total loss expression for the original order and the order with the swap, side by side, like so:

By examination, we can write an equation specifying the difference between these two losses by subtracting the two net sums. Since the total starting population is the same, it disappears from the relative difference equation, and we are left with terms of the sort diqj, which are losses due to wait times.

We can write out the difference between the original series and the series with the swapped elements by examining the two sums and noting that only terms associated with the swapped elements themselves, and those in the sequence between them, are impacted by the switch. This is because both terms, when swapped, will carry both their d and q, and so the change in each individual step are directly due to the sway, and those in between are due to the cumulative nature of the sums (terms between the two will lose the loss due to sk and gain that due to sl; terms after will still have both, and order is immaterial in a sum). Joining all these terms, we end up with the following equation expressing the difference in loss between the two sequences:

We can write out the difference between the original series and the series with the swapped elements by examining the two sums and noting that only terms associated with the swapped elements themselves, and those in the sequence between them, are impacted by the switch. This is because both terms, when swapped, will carry both their d and q, and so the change in each individual step are directly due to the sway, and those in between are due to the cumulative nature of the sums (terms between the two will lose the loss due to sk and gain that due to sl; terms after will still have both, and order is immaterial in a sum). Joining all these terms, we end up with the following equation expressing the difference in loss between the two sequences:

In this expression for the difference between net losses, we are seeing the impact of swapping sk and sl from the initial ordering. We can break it up into three meaningful terms: The two components containing sums, which account for the change due to accumulation effects between the switched elements. Essentially, these two terms subtract off the loss due to sk during the k-l period, and add in the resultant new loss due to selecting sl at time step k. The third term accounts for the change due to the swap at the time steps from which the swap is made (swapping k and l has a loss effect on all elements at those times, since the cure time you spend at that element at that step changes).

Now, looking at this equation, we can see that if the value resolves to a negative, the net change in population will be negative, i.e. swapping sk and sl reduced the number saved by the configuration Sr, and vice versa if positive. Let's look to our original ordering, sorted by ri = di/qi. Now, the form of ΔPs contains a pair of terms which account for the elements in the sequence between the two swaps, sk and sl. If, however, we let sk and sl be consecutive entries, then these two terms dwindle to zero, as there are no elements between them.

Now, looking at this equation, we can see that if the value resolves to a negative, the net change in population will be negative, i.e. swapping sk and sl reduced the number saved by the configuration Sr, and vice versa if positive. Let's look to our original ordering, sorted by ri = di/qi. Now, the form of ΔPs contains a pair of terms which account for the elements in the sequence between the two swaps, sk and sl. If, however, we let sk and sl be consecutive entries, then these two terms dwindle to zero, as there are no elements between them.

This leaves us with a much more simple relationship: ΔPs = qldk - qkdl. Now, our original order assumed dl/ql > dk/qk, so that: dlqk > dkql, or; dlqk - dkql > 0. Therefor, in our switch expression above, we can see that ΔPs < 0, so swapping any two adjacent results causes a loss. Thus, by considering a hypothetical sequence of swaps that move s0 shows that s0 must be in its optimal location, as its ri is greater than any succeeding element, so in any ordering, it can be moved to the first position to improve the net population saved.

Consequently, once s0 is fixed in first position, the same reasoning can be used to demonstrate that s1 may always be shifted to second position for a gain, and so forth and so on. Thus sorting by ri produces an optimally sorted list.

Unless, that is, ignoring an element all together turns out to be better for the whole collective. In that case, we'd have, essentially, a group of sacrifices for which the removal from the regular ordering resulted in a net gain in total saved population. The mechanism by which this would be enacted is fairly straightforward: By removing an element ss from the order, we effectively sacrifice the population saved for that element, but gain the population that would have been lost during its cure time.

At first, this seems like it should be easy to deal with by running through the order, computing for each entry the saved population, and the population lost due to all remaining elements waiting through the current element's cure time. However, this turns out to be problematic: consider removing some element ss1, and then later a subsequent element ss2. What, then, if in removing ss2, we encounter situation where ss1, without the loss due to ss2 (since we consider it a total sacrifice) is no longer a valid sacrifice (i.e. removing ds2 from the wait loss makes the net gain due to sacrificing ss1 negative).

So it's clear that the quality of a given element as a sacrifice candidate is dependent on the elements which succeed it. What about proceeding in reverse order, then? In that case, we run into almost the same problem, because the calculation determining loss depend on the population at cure time, but that value is dependent on the exact sum of cure times preceding that element, and thus removing ss2 (working back from the last element, sn), may be followed by removal of ss1 later on, but this sacrifice may elevate ss2's population sufficiently to negate its sacrifice.

Keeping this in mind, we can instead look to evaluating sacrifices in-situ. We could simply iterate over 2^n possible configurations, which would test every possible set of inclusions/exclusions over the whole set, however, we can do better that this. Consider that a 'sacrifice' is formally the same as moving an element to the end of the ordering, since the nature of the sacrifice is to ignore curing the element in question while you precede through the remaining included elements. But look at this- if you finish all the included elements and you have remaining population in the sacrificed element, you might as well go ahead and cure it to gain that population, right?

Except that this contradicts our earlier proof that the ri sorting is the optimal distribution, because if you recreate the a fresh list with all sacrifices but the one with remaining population, it will be subject to the same sk/sl swap, until reordered by ri proper. Therefore, no sacrifice will have population remaining after all inclusions are made. This paves the way for a very simple evaluation metric: Noting that the long term presence of population at a given element is always improved by additional sacrifices preceding it, we can note that any elements which are projected to become extinct after the sum of all cure times will never be valid sacrifices.

Elements which can become extinct in less time than the sum of all qi may or may not be sacrifices, but they are the only ones we need check. Thus we can calculate, for each population, the time (tex) at which it will exhaust all population:

Pi(t) = Pi(0) - di(t);

0 = Pi(0) - di(tex);

tex = Pi(0)/di

This we compare to the sum of qi (Qs) and if less than it, we consider it a possible candidate for sacrifice.

Consequently, once s0 is fixed in first position, the same reasoning can be used to demonstrate that s1 may always be shifted to second position for a gain, and so forth and so on. Thus sorting by ri produces an optimally sorted list.

Unless, that is, ignoring an element all together turns out to be better for the whole collective. In that case, we'd have, essentially, a group of sacrifices for which the removal from the regular ordering resulted in a net gain in total saved population. The mechanism by which this would be enacted is fairly straightforward: By removing an element ss from the order, we effectively sacrifice the population saved for that element, but gain the population that would have been lost during its cure time.

At first, this seems like it should be easy to deal with by running through the order, computing for each entry the saved population, and the population lost due to all remaining elements waiting through the current element's cure time. However, this turns out to be problematic: consider removing some element ss1, and then later a subsequent element ss2. What, then, if in removing ss2, we encounter situation where ss1, without the loss due to ss2 (since we consider it a total sacrifice) is no longer a valid sacrifice (i.e. removing ds2 from the wait loss makes the net gain due to sacrificing ss1 negative).

So it's clear that the quality of a given element as a sacrifice candidate is dependent on the elements which succeed it. What about proceeding in reverse order, then? In that case, we run into almost the same problem, because the calculation determining loss depend on the population at cure time, but that value is dependent on the exact sum of cure times preceding that element, and thus removing ss2 (working back from the last element, sn), may be followed by removal of ss1 later on, but this sacrifice may elevate ss2's population sufficiently to negate its sacrifice.

Keeping this in mind, we can instead look to evaluating sacrifices in-situ. We could simply iterate over 2^n possible configurations, which would test every possible set of inclusions/exclusions over the whole set, however, we can do better that this. Consider that a 'sacrifice' is formally the same as moving an element to the end of the ordering, since the nature of the sacrifice is to ignore curing the element in question while you precede through the remaining included elements. But look at this- if you finish all the included elements and you have remaining population in the sacrificed element, you might as well go ahead and cure it to gain that population, right?

Except that this contradicts our earlier proof that the ri sorting is the optimal distribution, because if you recreate the a fresh list with all sacrifices but the one with remaining population, it will be subject to the same sk/sl swap, until reordered by ri proper. Therefore, no sacrifice will have population remaining after all inclusions are made. This paves the way for a very simple evaluation metric: Noting that the long term presence of population at a given element is always improved by additional sacrifices preceding it, we can note that any elements which are projected to become extinct after the sum of all cure times will never be valid sacrifices.

Elements which can become extinct in less time than the sum of all qi may or may not be sacrifices, but they are the only ones we need check. Thus we can calculate, for each population, the time (tex) at which it will exhaust all population:

Pi(t) = Pi(0) - di(t);

0 = Pi(0) - di(tex);

tex = Pi(0)/di

This we compare to the sum of qi (Qs) and if less than it, we consider it a possible candidate for sacrifice.

We then will have some number m <= n of sacrifice candidates, resulting in an exploration space with the same constraints as the selection described above, giving us an O(2^m) binary exploration space (note that the probe to calculate the net population saved is O(n) ) to find the optimal disposition of sacrifices, which, in conjunction with the ri metric, provides a fully realized algorithmic solution to the problem, at a radically preferred complexity of 2^m, as opposed to the n! length solution associated with a brute force solution.