variables. See also Fractional coloring, a linear programming relaxation of graph coloring. Randomized rounding, for obtaining a solution to the original problem from a solution to the relaxation. References . . . . . . . . . Linear programming Combinatorial optimization Polyhedral combinatorics Relaxation (approximation)