# Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization

arXiv: https://arxiv.org/abs/2205.12442 · HTML: https://mlsanity.com/paper/2205.12442/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 32 references that are in the map.
- First posted on arXiv 25 May 2022.

## Builds on (most cited first, 11 of 11)

- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [A Variational Perspective on Accelerated Methods in Optimization](https://mlsanity.com/paper/1603.04245/) (2016)
- [Gradient Methods for Submodular Maximization](https://mlsanity.com/paper/1708.03949/) (2017)
- [The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods](https://mlsanity.com/paper/1712.02485/) (2017)
- [Continuous DR-submodular Maximization: Structure and Algorithms](https://mlsanity.com/paper/1711.02515/) (2017)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Continuous Submodular Function Maximization](https://mlsanity.com/paper/2006.13474/) (2020)
- [An Improved Local Search Algorithm for k-Median](https://mlsanity.com/paper/2111.04589/) (2021)
- [An improved approximation algorithm for maximizing a DR-submodular function over a convex set](https://mlsanity.com/paper/2203.14740/) (2022)
- [Submodular Maximization Through Barrier Functions](https://mlsanity.com/paper/2002.03523/) (2020)
- [A Unified Convergence Analysis of First Order Convex Optimization Methods via Strong Lyapunov Functions](https://mlsanity.com/paper/2108.00132/) (2021)

## Built on by (most cited first, 6 of 6)

- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [A Unified Approach for Maximizing Continuous DR-submodular Functions](https://mlsanity.com/paper/2305.16671/) (2023)
- [Boosting Gradient Ascent for Continuous DR-submodular Maximization](https://mlsanity.com/paper/2401.08330/) (2024)
- [Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization](https://mlsanity.com/paper/2403.10063/) (2024)
- [Fairness in Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2312.14299/) (2023)
- [Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization](https://mlsanity.com/paper/2401.09251/) (2024)

## Abstract (arXiv)

We propose a two-phase systematical framework for approximation algorithm design and analysis via Lyapunov function. The first phase consists of using Lyapunov function as an input and outputs a continuous-time approximation algorithm with a provable approximation ratio. The second phase then converts this continuous-time algorithm to a discrete-time algorithm with almost the same approximation ratio along with provable time complexity. One distinctive feature of our framework is that we only need to know the parametric form of the Lyapunov function whose complete specification will not be decided until the end of the first phase by maximizing the approximation ratio of the continuous-time algorithm. Some immediate benefits of the Lyapunov function approach include: (i) unifying many existing algorithms; (ii) providing a guideline to design and analyze new algorithms; and (iii) offering new perspectives to potentially improve existing algorithms. We use various submodular maximization problems as running examples to illustrate our framework.