AAAINov, 2016

竞赛方案的查询复杂度

PDF
TL;DR本文研究在仅查询尽可能少的边的情况下找到锦标赛的最佳顶点集合的问题，并给出了 Condorcet 非输家集合的计算方法，并证明了任何找到 Copeland 集合，Slater 集合，Markov 集合，双方集合，未覆盖集合，Banks 集合和顶点集合的算法在最坏情况下必须查询 Ω(n²) 条边，但如果输入的锦标赛的顶部循环的大小不超过 k，则可以只查询 O (nk + n log (n)/(log (1-1/k))) 条边即可找到所有锦标赛解。
发现论文，激发创造
  • 通过边界检测查询学习图

    这篇论文探讨了用边缘检测查询学习一般图的问题，研究并给出了 Las Vegas 算法和 Monte Carlo 算法不同的轮数和查询数量，概述了解决此问题的难点和限制。

    Mar, 2018

  • 反馈弧集锦标赛、肯尼等级聚合和中介集锦标赛的更快算法

    我们研究了三个问题的固定参数算法：Kemeny 排名聚合、反馈弧集锦标赛和在两点之间的锦标赛。

    Jun, 2010

  • 利用独立集预言机进行边缘估计

    本研究探讨了使用独立集合查询进行图边估计的问题，并提出了两种算法来估计 n 个顶点的图中边的数量。

    Nov, 2017

  • 关于树、单圈图和仙人掌图的在线图探索

    探究搜索者搜索未知的加权无向图的问题，证明最近邻算法的竞争比率在树中为 θ(logn)，并研究参数范围内算法 Blocking 在单轮图上是 3-competitive，在仙人掌图上是 5/2+√2 约等于 3.91-competitive。

    Apr, 2020

  • 有限查询图连接性测试

    提出了一种组合优化模型，可以在限定次数的查询下寻找图中两点的连通性，创新性地提出了一种较为可扩展的精确算法以及适用于大规模数据的启发式算法。

    Feb, 2023

  • 图中的确定性和概率二分搜索

    本文研究在带权无向图中的二分查找问题，并给出了一个在查询顶点时几乎达到信息熵下界的算法，同时也探讨了该问题在不同情况下的复杂性。

    Mar, 2015

  • 无知几乎是福利：少数查询下几近最优的随机匹配

    本文提出应用于随机匹配问题和随机集合覆盖问题的边缘和集合查询算法，分别基于自适应和非自适应策略，并将结果扩展到肾脏交换问题等实际问题上，结果表明即使在每个顶点上进行非常少量的非自适应边缘查询，也可以大大提高成功匹配率。

    Jul, 2014

  • 图上 Voronoi 游戏中的 Nash 平衡

    在这篇论文中，我们研究了一种游戏，其中每个玩家需要在给定的无向图中选择一个顶点（设施）。然后，所有顶点（客户）都被分配给最近的设施，玩家的回报是分配给它的客户数量。我们证明了在给定图中决定 Nash 均衡的存在是 NP 难问题，这是我们所知的这种零和游戏的首个结果。我们还引入了一个新的度量，社会成本差异，定义为最差和最佳纳什均衡之间成本的比率。我们证明了在我们的游戏中，社会成本差异为 Omega (sqrt (n/k)) 和 O (sqrt (kn))，其中 n 是顶点数量，k 是玩家数量。

    Feb, 2007

  • CONGEST 模型二次和接近二次的下界

    该研究给出在 CONGEST 模型中自然图问题的第一个超线性下界，并回答了长期以来的一个开放性问题，特别地，证明任何精确计算最小顶点覆盖或最大独立集的算法都需要在最坏情况下花费 Ω(n²/log²n) 轮，这样强的下界不仅局限于 NP 困难问题。

    May, 2017

  • 关于年轻选举的获胜者问题的精确复杂度

    本文研究了三种投票方案的胜者问题和排名问题的复杂度，发现 Young 的方案和 Lewis Carroll 的方案都是 NP 难问题，而 Fishburn 的方案可以通过线性规划高效求解。

    Dec, 2001