• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Combinatorial optimization and applications >On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
【24h】

On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs

机译：幂律图上最优化问题的难点和难点

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The discovery of power law distribution in degree sequence (i.e. the number of vertices with degree i is proportional to i~(-β) for some constant β) of many large-scale real networks creates a belief that it may be easier to solve many optimization problems in such networks. Our works focus on the hardness and inapproximability of optimization problems on power law graphs (PLG). In this paper, we show that the Minimum Dominating Set, Minimum Vertex Cover and Maximum Independent Set are still APX-haxd on power law graphs. We further show the inapproximability factors of these optimization problems and a more general problem (p-Minimum Dominating Set), which proved that a belief of (1 + o(1))-approximation algorithm for these problems on power law graphs is not always true. In order to show the above theoretical results, we propose a general cycle-based embedding technique to embed any d-bounded graphs into a power law graph. In addition, we present a brief description of the relationship between the exponential factor β and constant greedy approximation algorithms.
机译：在许多大型真实网络中发现度数顺序（即度数为i的顶点的数目与i〜（-β）成正比）的幂律分布的发现，使人们相信更容易解决许多这种网络中的优化问题。我们的工作集中在幂律图（PLG）上优化问题的难点和难点。在本文中，我们证明了最小支配集，最小顶点覆盖和最大独立集在幂律图中仍然是APX-haxd。我们进一步展示了这些优化问题的不可逼近因素以及更普遍的问题（p-最小支配集），这证明了幂律图上对这些问题的（1 + o（1））-逼近算法的信念并不总是真正。为了显示上述理论结果，我们提出了一种基于周期的通用嵌入技术，将任何d界图嵌入到幂律图中。此外，我们还简要介绍了指数因子β与常数贪婪近似算法之间的关系。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号