AAAISep, 2022

一种改进的在线最小和集合覆盖算法

PDF
TL;DR本文探讨基于在线偏好聚合的基础模型，在评估算法的竞争力方面提出了一种新算法，能够实现更强的动态最优解，算法的竞争比由 $O (r^2)$ 到达。
online preference aggregationmin-sum set coverdynamic optimal solutionrandomized algorithmcompetitive ratio
发现论文，激发创造
  • 广义最小总和集盖问题注记

    本文针对广义最小集合覆盖问题，基于 alpha 点调度概念，改进了 Bansal，Gupta 和 Krishnaswamy 的 485 逼近算法，并获得了 28 逼近算法，提高了性能保障。

    Jul, 2011

  • 通过梯度下降进行降维：高效在线学习最佳排名

    本研究探讨了在线偏好聚合的自然模型，使用广义 Min-Sum-Set-Cover 问题作为形式化模型，将排序降维到双重随机矩阵空间，并应用在线梯度下降技术以在多项式时间内实现 GMSSC 低遗憾学习，以提高学习效率。

    Nov, 2020

  • 最小交点覆盖和广义最小交集覆盖的改进逼近算法

    研究广义最小和集覆盖 (GMSSC) 问题，提出一种基于 LP 松弛和随机四舍五入的算法，解决传统特例 (MSSC) 问题并取得 4.642 的近似比例；同时在最小和顶点覆盖 (MSVC) 问题中获得 16/9 的近似比例，并且证明了常规线性松弛的匹配完美性间隙；最后通过双重拟合证明了一个紧的近似保证。

    Jul, 2020

  • 在线子模最大化算法及其中断

    本文研究基于在线变体的子模函数最大化问题，探讨了两种特殊情况并得出了竞争比的上下界。具体而言，设计了一个 $1/e$ 竞争算法和一个针对最多只包含 k 个元素的解的常数竞争比算法。

    Jan, 2015

  • 资源分配问题的近最优在线算法和快速近似算法

    本文提出一种针对多个资源分配问题的算法体系，将在线请求建模为每次从未知的概率分布中独立抽取，给出了一个在任意接受数据的情况下获得一定比例最优解的单一算法，并且探究了如何在任意情况下应对敌对分布。同时，文中提出了解决大型 LPs 混合装填覆盖问题的快速算法，并分析了该算法在在线拍卖、网络路由和广告策略方案等特殊情况下的应用。

    Mar, 2019

  • 随机优化的购买信息

    本文研究如何以在线学习问题的形式购买信息来帮助随机优化问题，提出了一个 $2$-competitive 算法和一个 $e/(e-1)$-competitive 随机化算法，特别应用于 Min-Sum Set Cover 优化问题。

    Jun, 2023

  • 多预测在线算法

    本文研究了在多个机器学习预测的基础上增强的在线算法。我们提出了一个通用的算法框架，用于多重预测的在线覆盖问题，该算法能够获得与最佳预测器性能相竞争的在线解决方案。该算法还能够同时使竞争性达到最佳预测和最佳在线算法的性能水平，并应用于解决一些经典问题。

    May, 2022

  • 停止依赖无选择，不要重复移动：商品组合优化的最优、高效和实用算法

    我们设计了一种基于 Plackett Luce 的用户选择的快速算法，用于解决主动在线组合优化问题中的后悔最小化问题，并证明了该方法在实践中是有效的、最优的，并且没有现有方法的限制。

    Feb, 2024

  • 具有子集评价偏好的主动排名

    本研究旨在通过自适应挑选子集并收集偏好反馈，在 Plackett-Luce 模型下解决 PAC 排名问题，提出了新的 pivot trick 技巧，从而实现了在一定概率下识别 n 个项目的 ε- 最优排名，（m-1）/m 降低的样本复杂度和对称排名算法的阶无法提高的。

    Oct, 2018

  • 子模覆盖问题的高效数据流算法

    在数据流模型中研究了经典的子模覆盖（SC）问题，提出了新的流式子模覆盖（SSC）问题。我们设计了首个高效的双目标子模覆盖流算法（ESC-Streaming），对其性能提供理论保证，并通过数值实验证明了其与近似最优的贪心算法可比的竞争力。

    Nov, 2016