Jan, 2014

一种加权互斥最大集覆盖问题的精确算法

PDF
TL;DR本文介绍了一个时间复杂度为 $O^*(1.325^m)$ 的精确算法用于权重互斥最大集覆盖问题，该问题是 NP 难问题并来自从基因突变中识别信号通路的生物信息学问题，目前该问题使用启发式算法解决，无法保证解决方案的性能。通过提供一个相对高效的精确算法，我们的方法将提高在癌症研究中寻找更好解决方案的能力。
exact algorithmweighted mutually exclusive maximum set coverbioinformaticssignaling pathwayscancer research
发现论文，激发创造
  • 疫苗设计中的最大 n 次覆盖

    本文提出了最大 $n$ 次覆盖问题和最小成本 $n$ 次覆盖问题，并介绍了两种基于整数线性规划和贪婪优化的 $n$ 次覆盖的实际解决方案。研究表明，最大 $n$ 次覆盖是一种自然的肽疫苗设计方法，并找到了一种针对 COVID-19 的泛株系疫苗设计，其预测人群覆盖率和每个个体 HLA 分子显示的肽数均优于其他 29 种已发表的设计。

    Jan, 2021

  • 广义最小总和集盖问题注记

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

    Jul, 2011

  • H - 自由图中最大权独立集问题的拟多项式时间逼近方案

    本文研究的是在 $H$-free 图中最大独立集问题的复杂度，通过提出近似算法和精确算法，对一些情况下的这一问题做出了更好的可解性结果。

    Jul, 2019

  • 大规模最大独立集问题的元启发式算法

    针对实际的车辆路径问题，研究了最大权独立集问题，通过开发一个新的本地搜索算法，该算法使用了先前文献中未描述的更广泛的简单局部搜索运算和数据结构，引入了路径重新链接的新变体来避免局部最优解以及一种新的交替增广路径局部搜索移动来提高算法性能。

    Mar, 2022

  • 解决实际大规模图中的最大权独立集问题

    本文提出了一种新的最大权独立集问题分支和缩减策略，结合核心化与局部搜索能够比局部搜索单独得出更高质量的解，通过实验表明，在实践中这种方法比现有的算法更加有效，可以处理高达数百万个顶点和边的实际问题。

    Oct, 2018

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

    本文探讨基于在线偏好聚合的基础模型，在评估算法的竞争力方面提出了一种新算法，能够实现更强的动态最优解，算法的竞争比由 $O (r^2)$ 到达。

    Sep, 2022

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

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

    Jul, 2020

  • 大规模图上最大团问题的快速算法及其在重叠社团检测中的应用

    提出了一种使用新的修剪技术的确切算法，可快速在非常大、稀疏的图中找到最大团，并提出了一个快得多且提供最优或接近最优解的启发式算法，同时在网络中检测重叠社区的开发方法。

    Nov, 2014

  • 最坏情况下的自适应亚模模糊覆盖

    本文研究自适应子模块覆盖问题，在最坏情况下进行研究。该问题推广了许多以前研究过的问题，对于固定成本下观察每个医学测试的结果的效用函数，我们目的是选择一组物品以实现 “目标值”，并在最小化实现代价（最大较差情况下成本）的同时逐步选择这些物品。同时研究了最坏情况下的最大覆盖问题。

    Oct, 2022

  • 混合装箱和覆盖线性规划的更快的宽度相关算法

    本文提出了基于面积凸性的混合装箱问题 LP 的宽度相关算法并进一步将其应用于最密子图问题中，实现了比宽度独立算法更高的精度。

    Sep, 2019