Generalized submodular cover problems and applications

Judit Bar-Ilan, Guy Kortsarz, David Peleg

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

Abstract

The greedy approach has been successfully applied in the past to produce logarithmic ratio approximations to NP-hard problems under certain conditions. The problems for which these conditions hold are known as submodular cover problems. The current paper3 extends the applicability of the greedy approach to wider classes of problems. The usefulness of our extensions is illustrated by giving new approximate solutions for two different types of problems. The first problem is that of finding the spanning tree of minimum weight among those whose diameter is bounded by D. A logarithmic ratio approximation algorithm is given for the cases of D = 4 and 5. This approximation ratio is also proved to be the best possible, unless P = NP. The second type involves some (known and new) center selection problems, for which new logarithmic ratio approximation algorithms are given. Again, it is shown that the ratio must be at least logarithmic unless P=NP.

Original languageEnglish (US)
Pages (from-to)179-200
Number of pages22
JournalTheoretical Computer Science
Volume250
Issue number1-2
DOIs
StatePublished - Jan 6 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Greedy approximation
  • NP-hard problems
  • Submodular covers

Fingerprint

Dive into the research topics of 'Generalized submodular cover problems and applications'. Together they form a unique fingerprint.

Cite this