Approximation Algorithms for Packing Directed Acyclic Graphs into Two-Size Blocks
Approximation Algorithms for Packing Directed Acyclic Graphs into Two-Size Blocks
复制标题
将有向无环图打包成两种大小的块的近似算法
DOI：
10.1007/978-3-319-95165-2_43
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Yagita Tsuyoshi
中科院分区：
文献类型：
--
作者：
Asahiro Yuichi;Miyano Eiji;Yagita Tsuyoshi
在本文中，我们考虑以下变体的聚类或布局问题的图：给定一个有向无环图（DAG的简称）和一个integerB，目标是找到一个映射的节点到块的大小最多B，最大限度地减少外部弧的最大数量在遍历的无环结构的以下路径从根到叶。外弧定义为连接两个不同块的弧。本文以案例为研究对象。即使DAG的高度为3，已知该问题是NP难的，而且，除非P = NP，否则没有因子逼近算法。另一方面，先前示出的最佳近似比是3。在本文中，我们改进的逼近比严格小于2。此外，我们研究了输入DAG的高度与不可近似性之间的关系，因为上述不可近似性边界仅针对高度为3的DAG示出。
In this paper we consider the following variant of clustering or laying out problems of graphs: Given a directed acyclic graph (DAG for short) and an integerB, the objective is to find a mapping of its nodes into blocks of size at mostBthat minimizes the maximum number of external arcs during traversals of the acyclic structure by following paths from the roots to the leaves. An external arc is defined as an arc connecting two distinct blocks. This paper focuses on the case. Even ifand the height of the DAG is three, it is known that the problem is NP-hard, and furthermore, there is nofactor approximation algorithm forand a small positiveunless P = NP. On the other hand, the best approximation ratio previously shown is 3. In this paper we improve the approximation ratio into strictly smaller than 2. Also, we investigate the relationship between the height of input DAGs and the inapproximability, since the above inapproximability boundis shown only for DAGs of height 3.