lp relaxation | BriefGPT - AI 论文速递

关键词lp relaxation

搜索结果 - 8

近似纳什均衡算法中的搜索与混合范式
AI 在数学领域以一种建设性的方式处理数学问题，使推理自动化、减少劳动力和降低错误率。本研究首次提供了一个自动化方法，用于理论计算机科学中一个经过深入研究的问题：计算两人博弈中的近似纳什均衡。我们观察到，这样的算法可以被重新表述为搜索混合范
PDF9 months ago
社会公正聚类的近似算法
本文提出了一种在社会公正聚类中的近似算法，这个问题包括了在一个度量空间中，给定一组点，每个点属于一个或多个组，为了同时满足所有组，需要找到一个 k - 中位数、k - 均值或者更一般意义上，l_p - 聚类，同时给出了强化的 LP 松弛，将
PDF3 years ago
最小交点覆盖和广义最小交集覆盖的改进逼近算法
研究广义最小和集覆盖 (GMSSC) 问题，提出一种基于 LP 松弛和随机四舍五入的算法，解决传统特例 (MSSC) 问题并取得 4.642 的近似比例；同时在最小和顶点覆盖 (MSVC) 问题中获得 16/9 的近似比例，并且证明了常规线
PDF4 years ago
具有库存限制的多阶段多客户组合优化
我们考虑了一种混合物优化问题，针对在线随机匹配的情况，我们提出了一种多项式时间近似算法，其近似比为至少 1-ln (2-1 /e) 或 0.51，并基于线性规划松弛进一步改进了以前的随机舍入方案。在一般的混合物问题中，我们建立了第一个常数因
PDF5 years ago
割平面选择中的理论挑战
对比不同种类的切割平面以及它们间的相对强度，讨论在分支定界树中选取一个投资组合的切割平面的问题，提出一些新的方法。在研究中，试图为切割平面选择设计出一种更为系统的方法。同时我们为与切割平面选择有关的一些问题提供了初步的理论基础。
PDF6 years ago
基于原始对偶算法的 k-Means 和欧几里得 k-Median 的更好保证
该研究采用原始 - 对偶算法来解决 $k$-means 聚类问题，在满足集群数量限制的同时得到了 6.357 - 近似比的效果，并在欧几里得度量中解决了 $k$-median 的问题。
PDF8 years ago
利用消息传递来加紧 MAP 的 LP 松弛
使用双重消息传递算法对线性规划进行松弛，通过迭代选择具有保证改进的集群，解决集群选择问题，成功地在蛋白质侧链放置、蛋白质设计和立体化问题中找到了最有可能的 MAP 配置。
PDF12 years ago
辅助子模型问题实现局部最优解
本文提出了基于 LP-relaxation 的新的 LP-autarky 方法，证明了 Ivan Kovtun, LP 方法和 Yuri Boykov 扩展运动算法之间的关系，并证明了这些方法在确保变量分配时的优越性。
PDF13 years ago