chap37.htm

CLRS-算法导论

<pre>line 4:  <I>L</I>2  =  <img src="../images/lftwdchv.gif">0, 102, 104, 206<img src="../images/wdrtchv.gif"> ,</sub></sup></pre><P>
<pre>line 5:  <I>L</I><SUB>2  </SUB>=  <img src="../images/lftwdchv.gif">0, 102, 206<img src="../images/wdrtchv.gif"> ,</sub></sup></pre><P>
<pre>line 6:  <I>L</I><SUB>2  </SUB>=  <img src="../images/lftwdchv.gif">0, 102, 206<img src="../images/wdrtchv.gif"> ,</sub></sup></pre><P>
<pre>line 4:  <I>L</I><SUB>3  </SUB>=  <img src="../images/lftwdchv.gif">0,102, 201, 206, 303, 407<img src="../images/wdrtchv.gif"> ,</sub></sup></pre><P>
<pre>line 5:  <I>L</I><SUB>3  </SUB>=  <img src="../images/lftwdchv.gif">0,102, 201, 303, 407<img src="../images/wdrtchv.gif"> ,</sub></sup></pre><P>
<pre>line 6:  <I>L</I><SUB>3</SUB>  =  <img src="../images/lftwdchv.gif">0, 102, 201, 303<img src="../images/wdrtchv.gif"> ,</sub></sup></pre><P>
<pre>line 4:  <I>L</I><SUB>4  </SUB>=  <img src="../images/lftwdchv.gif">0, 101, 102, 201, 203, 302, 303, 404<img src="../images/wdrtchv.gif"> ,</sub></sup></pre><P>
<pre>line 5:  <I>L</I><SUB>4  </SUB>=  <img src="../images/lftwdchv.gif">0,101, 201, 302, 404<img src="../images/wdrtchv.gif"> ,</sub></sup></pre><P>
<pre>line 6:  <I>L</I><SUB>4  </SUB>=  <img src="../images/lftwdchv.gif">0,101, 201, 302<img src="../images/wdrtchv.gif"> .</sub></sup></pre><P>
The algorithm returns <I>z</I> = 302 as its answer, which is well within <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT> = 20% of the optimal answer 307 = 104 + 102 + 101; in fact, it is within 2%.<P>
<a name="0a25_1d4d">Theorem 37.6<a name="0a25_1d4d"><P>
A<FONT FACE="Courier New" SIZE=2>PPROX-</FONT>S<FONT FACE="Courier New" SIZE=2>UBSET-</FONT><FONT FACE="Courier New" SIZE=2>SUM</FONT> is a fully polynomial-time approximation scheme for the subset-sum problem.<P>
<I><B>Proof     </I></B>The operations of trimming <I>L<SUB>i</I></SUB> in line 5 and removing from <I>L<SUB>i</I></SUB> every element that is greater than <I>t</I> maintain the property that every element of <I>L<SUB>i</I></SUB> is also a member of <I>P<SUB>i</I></SUB>. Therefore, the value <I>z</I> returned in line 8 is indeed the sum of some subset of <I>S</I>. It remains to show that it is not smaller than 1 - <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT> times an optimal solution. (Note that because the subset-sum problem is a maximization problem, equation (37.2) is equivalent to <I>C</I>*(1-<FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT>) <img src="../images/lteq12.gif"> <I>C</I>.) We must also show that the algorithm runs in polynomial time.<P>
To show that the relative error of the returned answer is small, note that when list <I>L<SUB>i</I></SUB> is trimmed, we introduce a relative error of at most <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT>/<I>n</I> between the representative values remaining and the values before trimming. By induction on <I>i</I>, it can be shown that for every element <I>y</I> in <I>P<SUB>i</I></SUB> that is at most <I>t</I>, there is a <I>z</I> <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT> <I>L<SUB>i</I></SUB> such that<P>
<pre>(1 - <img src="../images/memof12.gif">/<I>n</I>)<I><SUP>i</SUP>y</I> <img src="../images/lteq12.gif"> <I>z</I> <img src="../images/lteq12.gif"> <I>y</I>.</sub></sup></pre><P>
<h4><a name="0a25_1d4e">(37.12)<a name="0a25_1d4e"></sub></sup></h4><P>
If <I>y</I>* <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT> <I>P<SUB>n</I></SUB> denotes an optimal solution to the subset-sum problem, then there is a <I>z</I> <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT> <I>L<SUB>n</I></SUB> such that<P>
<pre>(1 - <img src="../images/memof12.gif">/<I>n</I>)<I><SUP>n</SUP>y</I>* <img src="../images/lteq12.gif"> <I>z</I> <img src="../images/lteq12.gif"> <I>y</I>*;</sub></sup></pre><P>
<h4><a name="0a25_1d4f">(37.13)<a name="0a25_1d4f"></sub></sup></h4><P>
the largest such <I>z</I> is the value returned by <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-<FONT FACE="Courier New" SIZE=2>SUBSET</FONT>-<FONT FACE="Courier New" SIZE=2>SUM</FONT>. Since it can be shown that<P>
<img src="983_a.gif"><P>
the function (1 - <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT>/<I>n</I>)<I><SUP>n</I></SUP> increases with <I>n</I>, so that <I>n</I> &gt; 1 implies<P>
<pre>1 - <img src="../images/memof12.gif"> &lt;(1 - <img src="../images/memof12.gif">/<I>n</I>)<I><SUP>n</I></SUP>,</sub></sup></pre><P>
and thus,<P>
<pre>(1 - <img src="../images/memof12.gif">)<I>y</I>* <img src="../images/lteq12.gif"> <I>z</I>.</sub></sup></pre><P>
Therefore, the value <I>z</I> returned by <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-<FONT FACE="Courier New" SIZE=2>SUBSET</FONT>-<FONT FACE="Courier New" SIZE=2>SUM</FONT> is not smaller than 1 - <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT> times the optimal solution <I>y</I>*.<P>
To show that this is a fully polynomial-time approximation scheme, we derive a bound on the length of <I>L<SUB>i</I></SUB>. After trimming, successive elements <I>z</I> and <I>z</I>' of <I>L<SUB>i</I></SUB> must have the relationship <I>z/z</I>' &gt; 1/(1 - <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT>/<I>n</I>). That is, they must differ by a factor of at least 1/(1 - <FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT>/<I>n</I>). Therefore, the number of elements in each <I>L<SUB>i</I></SUB> is at most<P>
<img src="983_b.gif"><P>
using equation (2.10). This bound is polynomial in the number <I>n</I> of input values given, in the number of bits 1g <I>t</I> needed to represent <I>t</I>, and in 1/<FONT FACE="Courier New" SIZE=2><img src="../images/memof12.gif"></FONT>. Since the running time of <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-<FONT FACE="Courier New" SIZE=2>SUBSET</FONT>-<FONT FACE="Courier New" SIZE=2>SUM</FONT> is polynomial in the length of the <I>L<SUB>i</I></SUB>, <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-<FONT FACE="Courier New" SIZE=2>SUBSET</FONT>-<FONT FACE="Courier New" SIZE=2>SUM</FONT> is a fully polynomial-time approximation scheme.      <P>
<P>







<h2><a name="0a26_0001">Exercises<a name="0a26_0001"></h2><P>
<a name="0a26_0002">37.4-1<a name="0a26_0002"><P>
Prove equation (37.11).<P>
<a name="0a26_0003">37.4-2<a name="0a26_0003"><P>
Prove equations (37.12) and (37.13).<P>
<a name="0a26_0004">37.4-3<a name="0a26_0004"><P>
How would you modify the approximation scheme presented in this section to find a good approximation to the smallest value not less than <I>t</I> that is a sum of some subset of the given input list?<P>
<P>


<P>







<h1><a name="0a27_1d57">Problems<a name="0a27_1d57"></h1><P>
<a name="0a27_1d58">37-1     Bin packing<a name="0a27_1d58"><P>
<a name="0a27_1d4d"><a name="0a27_1d4e"><a name="0a27_1d4f">Suppose that we are given a set of <I>n</I> objects, where the the size <I>s<SUB>i</I></SUB> of the <I>i</I>th object satisfies 0 &lt; <I>s<SUB>i</I></SUB> &lt; 1. We wish to pack all the objects into the minimum number of unit-size bins. Each bin can hold any subset of the objects whose total size does not exceed 1.<P>
<I><B>a.     </I></B>Prove that the problem of determining the minimum number of bins required is NP-hard. (<I>Hint:</I> Reduce from the subset-sum problem.)<P>
The <I><B>first-fit</I></B> heuristic takes each object in turn and places it into the first bin that can accommodate it. Let<P>
<img src="984_a.gif">.<P>
<I><B>b.     </I></B>Argue that the optimal number of bins required is at least <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrul14.gif"><I>S</I><img src="../images/hfbrur14.gif"></FONT>.<P>
<I><B>c.     </I></B>Argue that the first-fit heuristic leaves at most one bin less than half full.<P>
<I><B>d.     </I></B>Prove that the number of bins used by the first-fit heuristic is never more than <FONT FACE="Times New Roman" SIZE=2><img src="../images/hfbrul14.gif"></FONT>2<I>S<FONT FACE="Times New Roman" SIZE=2></I><img src="../images/hfbrur14.gif"></FONT>.<P>
<I><B>e.     </I></B>Prove a ratio bound of 2 for the first-fit heuristic.<P>
<I><B>f.     </I></B>Give an efficient implementation of the first-fit heuristic, and analyze its running time.<P>
<a name="0a27_1d59">37-2     Approximating the size of a maximum clique<a name="0a27_1d59"><P>
<a name="0a27_1d50"><a name="0a27_1d51"><a name="0a27_1d52">Let <I>G</I> = (<I>V, E</I>) be an undirected graph. For any <I>k</I> <img src="../images/gteq.gif"> 1, define <I>G</I><SUP>(<I>k</I>)</SUP> to be the undirected graph (<I>V</I><SUP>(<I>k</I>),</SUP><I> E</I><SUP>(<I>k</I>), </SUP>where <I>V</I><SUP>(<I>k</I>)</SUP> is the set of all ordered <I>k</I>-tuples of vertices from <I>V</I> and <I>E</I><SUP>(<I>k</I>)</SUP> is defined so that (<I>v</I><SUB>1</SUB>,<I>v</I><SUB>2</SUB>, . . . , <I>v<SUB>k</I></SUB>) is adjacent to (<I>w</I><SUB>1</SUB>, <I>w</I><SUB>2</SUB>, . . . , <I>w<SUB>k</I></SUB>) if and only if for some <I>i</I>, vertex <I>v<SUB>i</I></SUB> is adjacent to <I>w<SUB>i</I></SUB> in <I>G</I>.<P>
<I><B>a.     </I></B>Prove that the size of the maximum clique in <I>G</I><SUP>(<I>k</I>)</SUP> is equal to the <I>k</I>th power of the size of the maximum clique in <I>G</I>.<P>
<I><B>b.     </I></B>Argue that if there is an approximation algorithm that has a constant ratio bound for finding a maximum-size clique, then there is a fully polynomial-time approximation scheme for the problem.<P>
<a name="0a27_1d5a">37-3     Weighted set-covering problem<a name="0a27_1d5a"><P>
<a name="0a27_1d53"><a name="0a27_1d54"><a name="0a27_1d55"><a name="0a27_1d56">Suppose that we generalize the set-covering problem so that each set <I>S<SUB>i</I></SUB> in the family <img src="984_b.gif"> has an associated weight <I>w<SUB>i</I></SUB> and the weight of a cover <img src="984_c.gif"> is <img src="../images/sum14.gif"><I><SUB>S<FONT FACE="Times New Roman" SIZE=1>i</I></SUB><img src="../images/memof12.gif"><I><SUB>c</SUB>w<SUB>i</I></FONT></SUB>. We wish to determine a minimum-weight cover. (Section 37.3 handles the case in which <I>w<SUB>i</I></SUB> = 1 for all <I>i</I>.)<P>
Show that the greedy set-covering heuristic can be generalized in a natural manner to provide an approximate solution for any instance of the weighted set-covering problem. Show that your heuristic has a ratio bound of <I>H</I>(<I>d</I>), where <I>d</I> is the maximum size of any set <I>S<SUB>i</I></SUB>.<P>
<P>







<h1>Chapter notes</h1><P>
There is a wealth of literature on approximation algorithms. A good place to start is Garey and Johnson [79]. Papadimitriou and Steiglitz [154] also have an excellent presentation of approximation algorithms. Lawler, Lenstra, Rinnooy Kan, and Shmoys [133] provide an extensive treatment of the traveling-salesman problem.<P>
Papadimitriou and Steiglitz attribute the algorithm <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-<FONT FACE="Courier New" SIZE=2>VERTEX</FONT>-<FONT FACE="Courier New" SIZE=2>COVER</FONT> to F. Gavril and M. Yannakakis. The algorithm <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-TSP-<FONT FACE="Courier New" SIZE=2>TOUR</FONT> appears in an excellent paper by Rosenkrantz, Stearns, and Lewis [170]. Theorem 37.3 is due to Sahni and Gonzalez [172]. The analysis of the greedy heuristic for the set-covering problem is modeled after the proof published by Chv&aacute;tal [42] of a more general result; this basic result as presented here is due to Johnson [113] and Lov&aacute;sz [141]. The algorithm <FONT FACE="Courier New" SIZE=2>APPROX</FONT>-<FONT FACE="Courier New" SIZE=2>SUBSET</FONT>-<FONT FACE="Courier New" SIZE=2>SUM</FONT> and its analy