• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual Symposium on Theoretical Aspects of Computer Science(STACS 2004); 20040325-20040327; Montpellier; FR >On Minimum Circular Arrangement
【24h】

On Minimum Circular Arrangement

机译：关于最低限度的通函安排

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

摘要

Motivated by a scheduling problem encountered in multicast environments, we study a vertex labelling problem, called Minimum Circular Arrangement (MCA), that requires one to find an embedding of a given weighted directed graph into a discrete circle which minimizes the total weighted arc length. Its decision version is already known to be NP-complete when restricted to sparse weighted instances. We prove that the decision version of even un-weighted MCA is NP-complete in case of sparse as well as dense graphs. We also consider complementary version of MCA, called MaxCA. We prove that it is MAX-SNP[π] complete and, therefore, has no PTAS unless P=NP. A similar proof technique shows that MCA is MAX-SNP[π]-Hard and hence admits no PTAS as well. Then we prove a conditional lower bound of 2~(1/2) — ε for MCA approximation under some hardness assumptions, and conclude with a PTAS for MCA on dense instances.
机译：受多播环境中遇到的调度问题的启发，我们研究了一种称为最小圆排列（MCA）的顶点标记问题，该问题要求人们将给定的加权有向图嵌入到离散的圆中，以最小化总的加权弧长。当仅限于稀疏加权实例时，它的决策版本是NP完全的。我们证明即使在稀疏图和密集图的情况下，即使未加权的MCA的决策版本也是NP完全的。我们还考虑了称为MaxCA的MCA的补充版本。我们证明它是MAX-SNP [π]完整的，因此，除非P = NP，否则没有PTAS。类似的证明技术表明MCA是MAX-SNP [π] -Hard，因此也不接受PTAS。然后我们在某些硬度假设下证明了MCA逼近的2〜（1/2）-ε的条件下界，并在密集情况下以MCAS的PTAS得出结论。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号