Analysis of greedy approximations with nonsubmodular potential functions
Ding‐Zhu Du, Ronald Graham, Pãnos M. Pardalos, Peng‐Jun Wan, Weili Wu, Wenbo Zhao · 2008
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.