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

Donglei Du

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…