Skip to main content

Section16.1On-line algorithms¶ permalink

Many applications of combinatorics occur in a dynamic, on-line manner. It is rare that one has all the information about the challenges a problem presents before circumstances compel that decisions be made. As examples, a decision to proceed with a major construction project must be made several years before ground is broken; investment decisions are made on the basis of today's information and may look particularly unwise when tomorrow's news is available; and deciding to exit a plane with a parachute is rarely reversible.

In this section, we present two examples intended to illustrate on-line problems in a combinatorial setting. Our first example involves graph coloring. As is customary in discussions of on-line algorithms, we consider a two-person game with the players called Assigner and Builder. The two players agree in advance on a class $\cgC$ of graphs, and the game is played in a series of rounds. At round $1$ Builder presents a single vertex, and Assigner assigns it a color. At each subsequent rounds, Builder presents a new vertex, and provides complete information at to which of the preceding vertices are adjacent to it. In turn, Assigner must give the new vertex a color distinct from colors she has assigned previously to its neighbors.

Example16.1

Even if Builder is constrained to build a path on $4$ vertices, then Assigner can be forced to use three colors. At Round 1, Builder presents a vertex $x$ and Assigner colors it. At Round 2, Builder presents a vertex $y$ and declares that $x$ and $y$ are not adjacent.

Now Assigner has a choice. She may either give $x$ and $y$ the same color, or she may elect to assign a new color to $y\text{.}$ If Assigner gives $x$ and $y$ different colors, then in Round 3, Builder presents a vertex $z$ and declares that $z$ is adjacent to both $x$ and $y\text{.}$ Now Assigner will be forced to use a third color on $z\text{.}$ In Round $4\text{,}$ Builder will add a vertex $w$ adjacent to $y$ but to neither $x$ nor $z\text{,}$ but the damage has already been done.

On the other hand, if Assigner $x$ and $y$ the same color, then in Round 3, Builder presents a vertex $z\text{,}$ with $z$ adjacent to $x$ but not to $y\text{.}$ Assigner must use a second color on $z\text{,}$ distinct from the one she gave to $x$ and $y\text{.}$ In Round 4, Builder presents a vertex $w$ adjacent to $z$ and $y$ but not to $x\text{.}$ Assigner must use a third color on $w\text{.}$

Note that a path is a tree and trees are forests. The next result shows that while forests are trivial to color off-line, there is a genuine challenge ahead when you have to work on-line. To assist us in keeping track of the colors used by Assigner, we will use the notation from Chapter 5 and write $\phi(x)$ for the color given by Assigner to vertex $x\text{.}$

Discussion16.3

Bob reads the proof and asks whether it was really necessary to treat the cases $k=2$ and $k=3$ separately. Wasn't it enough just to note that the case $k=1$ holds trivially. Carlos says yes.

Subsection16.1.1Doing Relatively Well in an On-Line Setting

Theorem 16.2 should be viewed as a negative result. It is hard to imagine a family of graphs easier to color than forests, yet in an on-line setting, graphs in this family are difficult to color. On the other hand, in certain settings, one can do reasonably well in an on-line setting, perhaps not as well as the true optimal off-line result but good enough to be useful. Here we present a particularly elegant example involving partially ordered sets.

Recall that a poset $P$ of height $h$ can be partitioned into $h$ antichains—by recursively removing the set of minimal elements. But how many antichains are required in an on-line setting? Now Builder constructs a poset $P$ one point at a time, while Assigner constructs a partition of $P$ into antichains. At each round, Builder will present a new point $x\text{,}$ and list those points presented earlier that are, respectively, less than $x\text{,}$ greater than $x$ and incomparable with $x\text{.}$ Subsequently, Assigner will assign $x$ to an antichain. This will be done either by adding $x$ to an antichain already containing one or more of the points presented previously, or by assigning $x$ to a new antichain.

Proof

The strategy for Assigner is so simple and natural, it might be the case that a more complex strategy would yield a more efficient partitioning. Not so.