Analysis of greedy approximations with nonsubmodular potential functions

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: Shi-Kuo Chang, The Generation of Minimal Trees with a Steiner Topology, Journal of the ACM (JACM), v.19 n.4, p.699-711, Oct. 1972 [doi>10.1145/321724.321733]
• 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: Uriel Feige, A threshold of ln n for approximating set cover (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.314-318, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237977]
• 4: Toshihiro Fujito, On Approximability of the Independent/Connected Edge Dominating Set Problems, Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science, p.117-126, December 13-15, 2000
• 5: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 6: Lu Ruan , Hongwei Du , Xiaohua Jia , Weili Wu , Yingshu Li , Ker-I Ko, A greedy approximation for minimum connected dominating sets, Theoretical Computer Science, v.329 n.1-3, p.325-330, 13 December 2004 [doi>10.1016/j.tcs.2004.08.013]
• 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.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

General Terms:
Algorithms, Design, Theory