Generalized submodular cover problems and applications

Judit Bar-Ilan, Guy Kortsarz, David Peleg

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

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.

שפה מקוריתאנגלית
עמודים (מ-עד)179-200
מספר עמודים22
כתב עתTheoretical Computer Science
כרך250
מספר גיליון1-2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 6 ינו׳ 2001

הערה ביבליוגרפית

Funding Information:
∗Corresponding author. E-mail addresses: judit@shum.cc.huji.ac.il (J. Bar-Ilan), peleg@wisdom.weizmann.ac.il (D. Peleg). 1Part of this work was carried out while the author was with the Department of Applied Mathematics and Computer Science at the Weizmann Institute of Science. 2Supported in part by a Walter and Elise Haas Career Development Award and by a grant from the Israel Science Foundation. 3A preliminary version of this paper has appeared as an extended abstract in Proc. 4th Israel Symp. on the Theory of Computing and Systems, Jerusalem, Israel, June 1996.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Generalized submodular cover problems and applications'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי