Analysis of Algorithms : An Active Learning Approach

238 OTHER ALGORITHMIC TECHNIQUES

For example, with a set of items of sizes {27, 22, 14, 11, 7, 1} and an upper

limit on the size of the subset sum of 55, the process would have the series of

passes as given in the table in Fig. 9.2. We see that this algorithm has found an

optimal solution of 55 on the third pass.

■ 9.1.5 Graph Coloring Approximation

Graph coloring is an unusual problem because, as opposed to the previous

cases, it has been shown that getting an approximate coloring that is even close

to the optimal coloring is as complex as getting the optimal coloring. The best

of the approximation algorithms that run in polynomial time will use more

than twice as many colors as optimal. Research has also shown that if there was

Pass Subsets of Item added Sum

size pass

0 27,22,1

27,22

27,11,1

27,14,1

27,14,1

22,1

27,1

1

14

11

7

27

22

50

53

53

49

50

50

50

1

11, 7, 1

14, 7, 1

14, 11, 1

14,1

14,1

22

27

1

11,1

27,1

27,1

27,1

27,11

27,14

27,14

22, 14

22, 11

22, 7

22, 1

11, 1

7, 1

14, 11

14, 7

11, 7

14, 1

27, 11

27, 7

27, 1

27, 22

27, 14

55

50

55

55

53

53

53

49

49

46

53

49

50

50

53

2

∅

■FIGURE 9.2

Results of first

three passes of

subset sum

approximation

algorithm