Abstract
We consider two classical hard graph problems: finding the maximum independent set of vertices, and coloring the vertices with fewest colors possible. We are interested in frugal algorithms for these problems, ones that use limited amount of computing capabilities. Such algorithms yield approximate, rather than exact, solutions, and are valued according to their performance guarantee, which is the maximum factor that approximate solutions can differ from optimal ones. We are primarily interested in two classes of frugal algorithms: polynomial-time, and on-line algorithms. We present several polynomial-time algorithms for obtaining large approximations in graphs containing large independent sets, and use them to improve the best performance guarantees known for both problems. We show how nearly all effective algorithms for these problems fall into yet another category of frugal algorithms, based on removing subgraphs, and obtain tight lower bounds on their performance. For on-line graph coloring, we give strong lower bounds for both deterministic and randomized algorithms, that hold even if the models are weakened in several ways, and improve the best performance guarantee known for randomized on-line coloring. Finally, we prove simple tight bounds on two interpretations of the on-line independent set problem and some of its variations.