On-line algorithms

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 as 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.

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 and write \(\phi(x)\) for the color given by Assigner to vertex \(x\).

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\) antichainsby 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\), and list those points presented earlier that are, respectively, less than \(x\), greater than \(x\) and incomparable with \(x\). 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.

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.

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.