# Lorentzen’s Fractional Edge Cover Upper Bound

While reading Shrijver’s Combinatorial Optimization, I ran across the following interesting and efficiently computable upper bound for the independence number due to Lorentzen (1966):

$\alpha\leq 2\rho^*-\rho$,

where $\rho$ is the edge covering number, and $\rho^*$ is the fractional edge covering number. In terms of invariants that we’re already coded this becomes

$\alpha\leq 2\alpha^*+\mu-n$,

where $\alpha^*$ is the fractional independence number (a very good upper bound on its own), $\mu$ is the matching number, and n is the order of the graph.

Lorentzen’s bound is included in a technical report . While it is cited by Shrijver and Lovasz, among others, no pdf of this report seems to be available anywhere. That surprises me a little.