Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization
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.