Java Reference
In-Depth Information
Maximal means to pick as many pairs as possible, selecting them in some order un-
til there are no more available pairs to select. Maximum means the matching that
gives the most pairs possible for a given graph. If OPT is the size of a minimum
vertex cover, then jMj 2 OPT because at least one endpoint of every matched
edge must be in any vertex cover.
A better example of a guaranteed bound on a solution comes from simple
heuristics to solve the BIN PACKING problem.
BIN PACKING:
Input: Numbers x
1
;x
2
;:::;x
n
between 0 and 1, and an unlimited supply of
bins of size 1 (no bin can hold numbers whose sum exceeds 1).
Output: An assignment of numbers to bins that requires the fewest possible
bins.
BIN PACKING in its decision form (i.e., asking if the items can be packed in
less than k bins) is known to be NP-complete. One simple heuristic for solving
this problem is to use a “first fit” approach. We put the first number in the first
bin. We then put the second number in the first bin if it fits, otherwise we put it in
the second bin. For each subsequent number, we simply go through the bins in the
order we generated them and place the number in the first bin that fits. The number
of bins used is no more than twice the sum of the numbers, because every bin
(except perhaps one) must be at least half full. However, this “first fit” heuristic can
give us a result that is much worse than optimal. Consider the following collection
of numbers: 6 of 1=7 +, 6 of 1=3 +, and 6 of 1=2 +, where is a small, positive
number. Properly organized, this requires 6 bins. But if done wrongly, we might
end up putting the numbers into 10 bins.
A better heuristic is to use decreasing first fit. This is the same as first fit, except
that we keep the bins sorted from most full to least full. Then when deciding where
to put the next item, we place it in the fullest bin that can hold it. This is similar to
the “best fit” heuristic for memory management discussed in Section 12.3. The sig-
nificant thing about this heuristic is not just that it tends to give better performance
than simple first fit. This decreasing first fit heuristic can be proven to require no
more than 11/9 the optimal number of bins. Thus, we have a guarantee on how
much inefficiency can result when using the heuristic.
The theory ofNP-completeness gives a technique for separating tractable from
(probably) intractable problems. Recalling the algorithm for generating algorithms
in Section 15.1, we can refine it for problems that we suspect are NP-complete.
When faced with a new problem, we might alternate between checking if it is
tractable (that is, we try to find a polynomial-time solution) and checking if it is
intractable (we try to prove the problem is NP-complete). While proving that
some problem is NP-complete does not actually make our upper bound for our
