Linear Programming (LP) Formulation
The fractional chromatic number χf(G) of a graph G can be obtained as a solution to a linear program. Let (G) be the set of all independent sets of G, and let (G,x) be the set of all those independent sets which include vertex x. For each independent set I, define a nonnegative real variable xI. Then χf(G) is the minimum value of
- ,
- subject to for each vertex .
The dual of this linear program computes the "fractional clique number", a relaxation to the rationals of the integer concept of clique number. That is, a weighting of the vertices of G such that the total weight assigned to any independent set is at most 1. The strong duality theorem of linear programming guarantees that the optimal solutions to both linear programs have the same value. Note however that each linear program may have size that is exponential in the number of vertices of G, and that computing the fractional chromatic number of a graph is NP-hard. This stands in contrast to the problem of fractionally coloring the edges of a graph, which can be solved in polynomial time. This is a straightforward consequence of Edmonds' matching polytope theorem.
Read more about this topic: Fractional Coloring
Famous quotes containing the words programming and/or formulation:
“If there is a price to pay for the privilege of spending the early years of child rearing in the driver’s seat, it is our reluctance, our inability, to tolerate being demoted to the backseat. Spurred by our success in programming our children during the preschool years, we may find it difficult to forgo in later states the level of control that once afforded us so much satisfaction.”
—Melinda M. Marshall (20th century)
“In necessary things, unity; in disputed things, liberty; in all things, charity.”
—Variously Ascribed.
The formulation was used as a motto by the English Nonconformist clergyman Richard Baxter (1615-1691)