maths.free › Combinatorics & Graph Theory › 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.

现在轮到你没有计算器能解决这一个问题, 但其中的碎片是可以计算的。请在下面尝试一个, 或者输入您自己的。

保持你自己的工作

免费账户在每一课上都添加注解, 记录你完成的, 在一个地方解决的, 以及您可以询问的关于此页的导师。数学本身向每个人开放, 是否签名。

签名上签名登录

此处所用符号

输入完整定义、图片和其中每个字母的含义的符号。

人们对人们提出的问题

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.

本页部分内容从 Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). 在这里进行浓缩和重新解释;错误属于我们。