Generalized submodular cover problems and applications

The greedy approach has been successfully applied in the past to produce lo garithmic ratio approximations to NP-hard problems under certain conditions . The problems for which these conditions hold are known as submodular cove r problems. The current paper(3) extends the applicability of the greedy ap proach to wider classes of problems. The usefulness of our extensions is il lustrated by giving new approximate solutions for two different types of pr oblems. The first problem is that of finding the spanning tree of minimum w eight among those whose diameter is bounded by D. A logarithmic ratio appro ximation algorithm is given for the cases of D = 4 and 5. This approximatio n ratio is also proved to be the best possible, unless P = NP. The second t ype involves some (known and new) center selection problems, for which new logarithmic ratio approximation algorithms are given. Again, it is shown th at the ratio must be at least logarithmic unless P = NP. (C) 2001 Elsevier Science B.V. All rights reserved.