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

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 …

algorithm algorithm design analysis applications approximation arxiv design function math