Set Cover

Recall the definition of Set Cover: Given a collection ${\cal S}${\cal S} of finite sets from a universe $U$U and a cost $c_ s$c_ s for each set $s\in {\cal S}$s\in {\cal S}, the problem is to choose a minimum-cost set cover — a collection ${\cal C}${\cal C} of sets in ${\cal S}${\cal S} such that each element $e\in U$e\in U is contained in at least one set in ${\cal C}${\cal C}. The cost of ${\cal C}${\cal C} is $\sum _{s\in {\cal C}} c_ s$\sum _{s\in {\cal C}} c_ s.

The standard integer linear program for the problem is

In the linear-program relaxation of the problem, the variables can take non-integer values:

If a (possibly fractional) $x$x meets the constraint $\sum _{s\ni e} x_ s \ge 1$\sum _{s\ni e} x_ s \ge 1 for an element $e$e, we say that $x$x covers $e$e, and, if $x$x covers all elements, it is a fractional set cover — a feasible solution to the linear program. If $x$x is an integer solution, we identify it with the collection of sets $\{ s\in {\cal S}: x_ s \gt 0\}$\{ s\in {\cal S}: x_ s \gt 0\} .

The figure shows a fractional set cover of size 2 (that is, $\sum _ s x_ s = 2$\sum _ s x_ s = 2). The value assigned to each variable $x_ s$x_ s is written above its set $s$s. For each element $e$e, the total coverage $\sum _{s\ni e} x_ s$\sum _{s\ni e} x_ s of $e$e is shown below $e$e. The total coverage of each element is at least 1, so $x$x is a fractional set cover.

Multicommodity Flow

Maximum multicommodity flow (defined in this note) is exactly modeled by the following linear program:

For each path $p\in P$p\in P, there is a variable $f_ p$f_ p representing the flow on path $p$p. For each edge $e$e, there is a constraint that the total flow on paths through the edge is at most the edge capacity $c_ e$c_ e. Subject to these constraints, the objective is to maximize the total flow $|f|$|f| (i.e., $\sum _ p f_ p$\sum _ p f_ p) on all paths.

Wikipedia

• Set cover

• Multi-commodity flow

• covering and packing

• linear programming