Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization
Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization
复制标题
用于近似算法设计和分析的李亚普诺夫函数方法：在子模最大化中的应用
DOI：
10.48550/arxiv.2205.12442
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
D. Du
中科院分区：
文献类型：
--
作者：
D. Du
我们提出了一个两阶段的系统框架近似算法的设计和分析，通过李雅普诺夫函数。第一阶段包括使用李雅普诺夫函数作为输入和输出的连续时间近似算法与可证明的近似比。第二阶段，然后将此连续时间算法转换为离散时间算法，具有几乎相同的近似比沿着可证明的时间复杂度。我们的框架的一个显着特点是，我们只需要知道的参数形式的李雅普诺夫函数，其完整的规格将不会决定，直到第一阶段结束时，通过最大化的连续时间算法的近似比。李雅普诺夫函数方法的一些直接好处包括：（i）统一许多现有的算法;（ii）提供设计和分析新算法的指导方针;以及（iii）提供新的视角来潜在地改进现有算法。我们使用各种子模块最大化问题作为运行的例子来说明我们的框架。
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.
一种改进的k-中值局部搜索算法
DOI：
10.1137/1.9781611977073.65
发表时间：
2022
期刊：
2022 ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Cohen-Addad, Vincent;Gupta, Anupam;Hu, Lunjia;Oh, Hoon;Saulpic, David
通讯作者：
Saulpic, David
影响因子：
3.1
作者：
Diakonikolas, Jelena;Orecchia, Lorenzo
通讯作者：
Orecchia, Lorenzo