Here is an LP for the minimum edge cover problem, where the goal is to
choose a minimum number of edges so that every node is covered (by at least one edge):
$\min \sum x_{uv}$
s.t.
$\sum_u x_{uv} \ge 1 \quad \forall v$
$x_{uv} \ge 0$
-
Give the dual of this LP.
-
What does this dual LP mean, assuming that in both the primal and dual problems the
variables are "intended" to be 0/1? Try to figure out and describe in your own words what
problem the dual LP is solving. (In order to see what's
going on, it might help to draw a small example graph with, say, five nodes and a few edges
and seeing what feasible solutions would look like, and what sort of solutions the
objective is preferring.)