Jul, 2018

关于 (稀疏) 覆盖整数规划问题的近似算法

PDF
TL;DR本文针对覆盖整数规划问题提出了基于随机取整与修改的简单算法来改进其逼近度，并证明了近似度几乎是最优的，并且在没有失去逼近保证或效率的情况下可以去随机化，同时也提出了一种基于强化的线性规划近似方案，其运行时间比之前的最优解快 n 倍。这两个算法的组合使得本文提出的覆盖整数规划问题算法在近乎线性的时间内得到准确的结果。
approximation algorithmscovering integer programsrandomized roundingknapsack cover inequalitiesnear-optimal approximation bounds
发现论文，激发创造
  • 在线近似稀疏涵盖整数规划

    本文研究了覆盖整数规划和线性规划的在线算法，其中在保证可行性的前提下，提出了 O (log k) 的 CLP 算法和 O (log k log L) 的 CIP 随机算法，这是多项式时间内在线算法的最优竞争比。

    May, 2012

  • 近似约束满足需要较大线性规划松弛

    证明了对于约束满足问题的近似版本，线性规划松弛的规模存在超多项式下界，并且对于这些问题，多项式大小的线性规划方案与一定轮数的 Sherali-Adams 层次中产生的方案具有相同的能力；具体来说，最大割的多项式大小线性规划的可积性差可能性上界为 1/2，而最大三种满足问题的多项式大小线性规划则可能性上界为 7/8。

    Sep, 2013

  • 在线混合装箱与覆盖

    本文研究在线问题中的线性规划问题，提出了解决混合 packing 和 covering 约束线性规划在线问题的算法，并应用于两个与机器调度和设施定位相关的问题，得到了多项式对数竞争积分解决方案。

    Mar, 2012

  • 非凸二次约束规划的紧凑析取逼近

    本文提出一种新的方法 Compact Disjunctive Approximation，通过背包约束变量的复合设计来实现非凸 MIQCP 到任意精度的逼近，并且我们提出的方法在数值实验中表现良好。

    Nov, 2018

  • 混合装箱和覆盖的顺序和并行算法

    本文研究线性规划、近似算法和贪心算法在解决混合装箱和覆盖问题方面的应用，并提出一种可行的贪心算法，该算法复杂度为 O (epsilon^-2 log m) 线性时间迭代，且结论推广了之前的研究结果。

    May, 2002

  • 基于整数规划的贝叶斯网络学习的进展

    本研究通过整数规划方案和贪心算法等方法，从离散数据中学习 Bayesian 网络，在实验结果中取得了和之前相比有着巨大的改进。

    Sep, 2013

  • 从无限到有限程序：显式误差界与近似动态规划应用

    本研究探讨了在一般情况下难以计算的无穷维空间线性规划问题，通过采用随机优化和一阶方法等新兴发展，将其近似为易于处理的有限凸规划，同时在长期平均成本和折抵成本最优控制问题上，展示了理论研究的适用性和泛化性。

    Jan, 2017

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

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

    Sep, 2019

  • 混合装箱 / 覆盖和设施选址线性规划的近线性工作算法

    本文介绍了一种高效的线性规划和设施选址的近似算法，同时提出了一种节省时间和工作量的并行算法，该算法可在多项式对数时间内完成，并在时间和工作方面提供了（1+ϵ）- 近似解。

    Jul, 2014

  • 线性算术约束上的近似整数解统计

    我们提出了一种新的随机行走抽样方法来近似计算多面体内的晶格点计数，并且通过实验结果表明，我们的算法在解决高维多面体时明显优于现有的计数方法。

    Dec, 2023