Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization. (arXiv:2205.12442v1 [math.OC])

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 a guideline to design a continuous-time algorithm with
provable approximation ratio. The second phase then converts the
continuous-time algorithm to a discrete-time algorithm with the same
approximation ratio and a provable time complexity. Some immediate benefits of
the Lyapunov function approach include: (i) unifying many existing algorithms;
(ii) providing a guideline to design and analyze new …

algorithm algorithm design analysis applications approximation arxiv design function math