论文标题
lyapunov函数方法用于近似算法设计和分析：伴随于supporular最大化的应用
Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization
论文作者
论文摘要
我们提出了一个两相系统的框架，用于通过Lyapunov函数进行近似算法设计和分析。第一阶段包括使用Lyapunov函数作为输入，并输出具有可证明的近似比的连续时间近似算法。然后，第二阶段将这种连续的时间算法转换为几乎相同近似值的离散时间算法以及可证明的时间复杂性。我们框架的一个独特特征是，我们只需要了解Lyapunov函数的参数形式，该函数的参数形式将通过最大化连续时算法的近似值来决定，直到第一阶段结束时才能确定完整的规范。 Lyapunov功能方法的一些直接好处包括：（i）统一许多现有算法； （ii）提供设计和分析新算法的指南； （iii）提供新的观点，以改善现有算法。我们使用各种suplodular最大化问题作为运行示例来说明我们的框架。
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.
