approximation ratio | BriefGPT

关键词approximation ratio

搜索结果 - 25

关于确定性机制在设施选址博弈中的威力
考虑 K-Facility Location games 中的确定性策略对象机制，证明了确定性策略对象机制最佳逼近率为 n-2，并研究了在不同情况下的适用特点，如线性空间情况下存在唯一的独裁者机制，而简单情况下的策略不可能实现有界逼近率。
PDF12 years ago
MM正半定格罗滕迪克问题的秩约束
本文设计了一个多项式时间逼近算法以解决正半定 Grothendieck 问题，得到了逼近比例，并证明了该逼近比例是最优的。作者也提出了一种改进的算法，并应用它来解决 Laplacian 矩阵的情况。
PDF15 years ago
我们之和：公正的选人策略
在给定的有向图中选择一个大小为 k 的代理人子集，将入度之和最大化，并设计不需要付款的机制以满足策略无关性和近似最优性约束。具有近似比例边界的策略无关机制的近似比例上限为四对于任何 k 值，并随着 k 的增加逼近一。
PDF15 years ago
在线随机匹配：超越 1-1/e
本研究介绍了一种算法来解决在线随机二分匹配问题，提供了一个 0.67 的逼近比和一种基于流量图和最大流问题的新方法来解决这个问题。
PDF15 years ago
度量 k - 中心问题的反贪心算法
本篇研究介绍了一种名叫 ' 反贪心算法 '（RGreedy）的算法，用于求解 k - 中位数问题；并证明，当距离函数是度量时，RGreedy 的近似比在 log n/log log n 和 O（log n）之间。
PDF19 years ago