maths.free › Combinatorics & Graph Theory › 16. The Many Faces of Combinatorics › On-line algorithms

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.

Example

Even if Builder is constrained to build a path on \(4\) vertices, then Assigner can be forced to use three colors. At Round1, Builder presents a vertex \(x\) and Assigner colors it. At Round2, 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\). If Assigner gives \(x\) and \(y\) different colors, then in Round3, Builder presents a vertex \(z\) and declares that \(z\) is adjacent to both \(x\) and \(y\). Now Assigner will be forced to use a third color on \(z\). In Round\(4\), Builder will add a vertex \(w\) adjacent to \(y\) but to neither \(x\) nor \(z\), but the damage has already been done.

On the other hand, if Assigner \(x\) and \(y\) the same color, then in Round3, Builder presents a vertex \(z\), with \(z\) adjacent to \(x\) but not to \(y\). Assigner must use a second color on \(z\), distinct from the one she gave to \(x\) and \(y\). In Round4, Builder presents a vertex \(w\) adjacent to \(z\) and \(y\) but not to \(x\). Assigner must use a third color on \(w\).

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\).

Theorem

Let \(n\) be a positive integer. Then there is a strategy for Builder that will enable Builder to construct a forest having at most \(2^{n-1}\) vertices while forcing Assigner to use \(n\) colors.

Proof

When \(n=1\), all Builder does is present a single vertex. When \(n=2\), two adjacent vertices are enough. When \(n=3\), Builder constructs a path on \(4\) vertices as detailed in . Now assume that for some \(k\ge3\), Builder has a strategy \(S_i\) for forcing Assigner to use \(i\) colors on a forest of at most \(2^{i-1}\) vertices, for each \(i=1,2,\dots,k\). Here's how Builder proceeds to force \(k+1\) colors.

First, for each \(i=1,2,\dots,k\), Builder follows strategy \(S_i\) to build a forest \(F_i\) having at most \(2^{i-1}\) vertices on which assigner is forced to use \(i\) colors. Furthermore, when \(1\le i\lt j\le k\), there are no edges between vertices in \(F_i\) and vertices in \(F_j\).

Next, Builder chooses a vertex \(y_1\) from \(F_1\). Since Assigner uses two colors on \(F_2\), there is a vertex \(y_2\) from \(F_2\) so that \(\phi(y_2)\neq \phi(y_1)\). Since Assigner uses three colors on \(F_3\), there is a vertex \(y_3\) in \(F_3\) so that \(\{\phi(y_1),\phi(y_2),\phi(y_3)\}\) are all distinct. It follows that Builder may identify vertices \(y_1,y_2,\dots,y_k\) with \(y_i\in F_i\) so that the colors \(\phi(y_i)\) satisfy \(\phi(y_i)\neq \phi(y_j)\) if \(i\neq j\). Builder now presents a new vertex \(x\) and declares \(x\) adjacent to all vertices in \(\{y_1,y_2,\dots,y_k\}\) and to no other vertices. Clearly, the resulting graph is a forest and Assigner is forced to use a color for \(x\) distinct from the \(k\) colors she assigned previously to the vertices in \(\{y_1,y_2,\dots, y_k\}\). Also, the total number of vertices is at most \(1+[1+2+4+8+\dots+2^{k-1}]=2^k\).

Doing Relatively Well in an On-Line Setting

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.

Symbols used here

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

y',\ y''

first and second derivative of y
Prime notation for derivatives with respect to x (or t).

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\neq

not equal
The two sides are different.

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

试试你自己试试

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.