首页> 外文会议>Theory and applications of models of computation >Near Approximation of Maximum Weight Matching through Efficient Weight Reduction
【24h】

Near Approximation of Maximum Weight Matching through Efficient Weight Reduction

机译:通过有效的减重,最大重量匹配的近似值

获取原文
获取原文并翻译 | 示例

摘要

Let G be an edge-weighted hypergraph on n vertices, m edges of size ≤ s, where the edges have real weights in an interval [1, W. We show that if we can approximate a maximum weight matching in G within factor α in time T{n, m, W) then we can find a matching of weight at least (α - e) times the maximum weight of a matching in G in time (∈~(-1)~(O(1))× max_(1≤q≤O(∈ log n/∈/log ∈~(-1)) max _(m_1+...m_q=m∑_1~q T(min{n,sm_j},m_j,(∈~(-1))~(O(∈~(-1))). We obtain our result by an approximate reduction of the original problem to O(∈ log n/∈/log ∈~(-1)) subproblems with edge weights bounded by (∈~(-1)~(O(∈~(-1))). In particular, if we combine our result with the recent (1 - ∈)-approximation algorithm for maximum weight matching in graphs due to Duan and Pettie whose time complexity has a poly-logarithmic dependence on W then we obtain a (1 - ∈)-approximation algorithm for maximum weight matching in graphs running in time (∈~(-1))~(O(1))(m + n).
机译:令G为n个顶点的m个边缘≤s的边缘加权超图,其中这些边缘在区间[1,W中具有实际权重。我们证明,如果我们可以在G中的最大权重匹配因子α中,时间T {n,m,W),那么我们可以找到至少至少(α-e)乘以G在时间上的匹配最大权重(∈〜(-1)〜(O(1))× max_(1≤q≤O(∈log n /∈/ log∈〜(-1))max _(m_1 + ... m_q = m∑_1〜q T(min {n,sm_j},m_j,(∈〜 (-1))〜(O(∈〜(-1)))。通过将原始问题近似简化为带边的O(∈log n /∈/ log∈〜(-1))子问题,我们得到了结果权重由(∈〜(-1)〜(O(∈〜(-1)))界定,特别是如果我们将结果与最近的(1-∈)近似算法结合起来,则由于Duan和Pettie的时间复杂度对W具有多对数依赖关系,然后我们获得了(1--))近似算法,用于在时间为(ε〜(-1))〜(O(1))的图中进行最大权重匹配(m + n)。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号