One of the first heuristic approaches was presented by Balinski
(2) in 1961. He observed that there exist an optimal solution to the
relaxed version of (1.2) (i.e. the problem formed by ignoring the
restriction z. . e {0,1}) with the property that z.. = x../y... This
ID id id id
observation reduces the relaxed version of (1.2) to the following
problem,