skip to main content
10.5555/1347082.1347101acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article

Analysis of greedy approximations with nonsubmodular potential functions

Published: 20 January 2008 Publication History

Abstract

In this paper, we present two techniques to analyze greedy approximation with nonsubmodular functions restricted submodularity and shifted submodularity. As an application of the restricted submodularity, we present a worst-case analysis of a greedy algorithm for Network Steiner tree adapted from a heuristic originally proposed by Chang in 1972 for Euclidean Steiner tree. The performance ratio of Chang's heuristic is a longstanding open problem due to the nonsubmodularity of its potential function. As an application of the shifted submodularity, we present a worst-case analysis of a greedy algorithm for Connected Dominating Set generalized from a greedy algorithm proposed by Ruan et al. Such generalized greedy algorithm is shown to have performance ratio at most (1 + ε)(1 + ln(Δ - 1)), which matches the well-known lower bound (1-ε)ln Δ, where Δ is the maximum vertex-degree of input graph and ε is any positive constant.

References

[1]
S.-K. Chang, The generation of minimal trees with a Steiner topology, J. ACM, 19 (1972) 699--711.
[2]
S.-K. Chang, The design of network configurations with linear or piecewise linear cost functions, Symp. on Computer-Communications, Networks, and Teletraffic, (1972) 363--369.
[3]
U. Feige, A threshold of ln n for approximating set cover. Proc. the Twenty-Eighth Annual ACM Symp. Theory of Computing (1996) 314--318.
[4]
T. Fujito, On approximability of the independent/connected edge dominating set problems, Lecture Notes in Computer Sciences, vol. 1974, Springer, Berlin, 2000, pp. 117--126.
[5]
G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, 1999.
[6]
L. Ruan, H. Du, X. Jia, W. Wu, Y. Li, and K. Ko. A Greedy Approximation for Minimum Connected Dominating Sets. Theoretical Computer Science, 329 (2004) 325--330.
[7]
L. A. Wolsey, An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 4(2) (1982) 385--393.
[8]
A. Z. Zelikovsky, The 11/6-approximation algorithm for the Steiner problem on networks, Algorithmica 9 (1993) 463--470.

Cited By

View all
  • (2017)Guarantees for Greedy maximization of non-submodular functions with applicationsProceedings of the 34th International Conference on Machine Learning - Volume 7010.5555/3305381.3305433(498-507)Online publication date: 6-Aug-2017
  • (2017)Influence maximization with ε-almost submodular threshold functionsProceedings of the 31st International Conference on Neural Information Processing Systems10.5555/3294996.3295137(3804-3814)Online publication date: 4-Dec-2017
  • (2016)A greedy algorithm for the minimum $$2$$2-connected $$m$$m-fold dominating set problemJournal of Combinatorial Optimization10.1007/s10878-014-9720-631:1(136-151)Online publication date: 1-Jan-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
January 2008
1289 pages
  • Program Chair:
  • Shang-Hua Teng

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

  • Research-article

Conference

SODA08
Sponsor:
SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms
January 20 - 22, 2008
California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Guarantees for Greedy maximization of non-submodular functions with applicationsProceedings of the 34th International Conference on Machine Learning - Volume 7010.5555/3305381.3305433(498-507)Online publication date: 6-Aug-2017
  • (2017)Influence maximization with ε-almost submodular threshold functionsProceedings of the 31st International Conference on Neural Information Processing Systems10.5555/3294996.3295137(3804-3814)Online publication date: 4-Dec-2017
  • (2016)A greedy algorithm for the minimum $$2$$2-connected $$m$$m-fold dominating set problemJournal of Combinatorial Optimization10.1007/s10878-014-9720-631:1(136-151)Online publication date: 1-Jan-2016
  • (2013)A cross-monotonic cost-sharing scheme for the concave facility location gameJournal of Global Optimization10.1007/s10898-012-9852-056:4(1325-1334)Online publication date: 1-Aug-2013
  • (2011)On minimum submodular cover with submodular costJournal of Global Optimization10.1007/s10898-010-9563-350:2(229-234)Online publication date: 1-Jun-2011
  • (2010)PTAS for minimum connected dominating set with routing cost constraint in wireless sensor networksProceedings of the 4th international conference on Combinatorial optimization and applications - Volume Part I10.5555/1940390.1940411(252-259)Online publication date: 18-Dec-2010
  • (2010)New dominating sets in social networksJournal of Global Optimization10.1007/s10898-009-9511-248:4(633-642)Online publication date: 1-Dec-2010

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media