Efficient Relaxation and Rounding Techniques for Submodular Optimization
摘要
In the study of submodular optimization, the combination of relaxation and rounding stands out as one of the most effective techniques for designing approximation algorithms with reliable performance guarantees. This survey aims to compile a comprehensive collection of diverse relaxation functions and typical rounding schemes along with their applications. The relaxation functions include convex closure, Lovász extension, concave closure, and multilinear extension, while the rounding schemes encompass pipage rounding, swap rounding, and contention resolution schemes. We also demonstrate how combining primal-dual and extension functions can be applied to solve problems. By summarizing the related research within the domain of submodular optimization using these techniques, this survey contributes to a comprehensive understanding of the effectiveness and applicability of relaxation and rounding methodologies.