Approximation algorithms for constructing required subgraphs using stock pieces of fixed length
Approximation algorithms for constructing required subgraphs using stock pieces of fixed length
复制标题
使用固定长度的库存片段构造所需子图的近似算法
DOI：
10.1007/s10878-020-00543-x
复制
发表时间：
2020-02
影响因子：
1
通讯作者：
Xingxing Yu
中科院分区：
文献类型：
--
作者：
Junran Lichen;Jianping Li;Ko-Wei Lih;Xingxing Yu
本文讨论了用固定长度的库存块（stock pieces of fixed - length，简称CRS-SPFL）构造所需子图的问题，这是最小成本边加权子图（minimum-cost edge-weighted subgraph，简称MCEWS）问题的一个新变体。具体来说，对于MCEWS问题mq，要求从给定的图中选择一个最小代价的边子集，使得这些边可以形成所需的子图。对于CRS-SPFL问题，进一步要求用一些固定长度l的库存块通过加法来构造这样一个所需子图中的这些边。然而，新的目标是最小化构建这样一个所需子图的总成本，其中总成本是购买固定长度的库存件的成本和构建这样一个子图中所有边的成本的总和。我们得到以下三个主要结果。(1)给定求解MCEWS问题的近似算法，其中MCEWS问题的最优解为多项式时间精确算法，分别设计求解CRS-SPFL问题的近似算法和渐近近似算法；(2)当q是最小生成树问题时，我们分别提供了一种近似算法和一种AFPTAS来解决使用固定长度的库存块l构建生成树的问题；(3)对于单源最短路径树问题，我们分别提出了一种近似算法和一种AFPTAS来解决使用固定长度的库存碎片构建单源最短路径树的问题。
In this paper, we address the problem of constructing required subgraphs using stock pieces of fixed length (CRS-SPFL, for short), which is a new variant of the minimum-cost edge-weighted subgraph (MCEWS, for short) problem. Concretely, for the MCEWS problemQ, it is asked to choose a minimum-cost subset of edges from a given graphGsuch that these edges can form a required subgraph. For the CRS-SPFL problem, these edges in such a required subgraphare further asked to be constructed by plus using some stock pieces of fixed lengthL. The new objective, however, is to minimize the total cost to construct such a required subgraph, where the total cost is sum of the cost to purchase stock pieces of fixed lengthLand the cost to construct all edges in such a subgraph. We obtain the following three main results. (1) Given an-approximation algorithm to solve the MCEWS problem, where(for the case, the MCEWS problemQis solved optimally by a polynomial-time exact algorithm), we design a-approximation algorithm and another asymptotic-approximation algorithm to solve the CRS-SPFL problem, respectively; (2) WhenQis the minimum spanning tree problem, we provide a-approximation algorithm and an AFPTAS to solve the problemof constructing a spanning tree using stock pieces of fixed lengthL, respectively; (3) WhenQis the single-source shortest paths tree problem, we present a-approximation algorithm and an AFPTAS to solve the problemof constructing a single-source shortest paths tree using stock pieces of fixed lengthL, respectively.
登录
查看更多内容
DOI：
10.1007/978-0-387-30162-4_28
发表时间：
2021-08
期刊：
Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)
影响因子：
--
作者：
通讯作者：
--
影响因子：
1.8
作者：
Donghui Chen;D. Du;Xiaodong Hu;Guohui Lin;Lusheng Wang;G. Xue
通讯作者：
Donghui Chen;D. Du;Xiaodong Hu;Guohui Lin;Lusheng Wang;G. Xue
影响因子：
1.1
作者：
J. Remy;A. Steger
通讯作者：
J. Remy;A. Steger
DOI：
10.1007/springerreference_6200
发表时间：
2012-04
期刊：
--
影响因子：
--
作者：
F. Hwang;D. Richards;P. Winter
通讯作者：
F. Hwang;D. Richards;P. Winter
DOI：
10.1109/infcom.1997.635138
发表时间：
1997-04
期刊：
Proceedings of INFOCOM '97
影响因子：
--
作者：
B. Ramamurthy;Jason Iness;B. Mukherjee
通讯作者：
B. Ramamurthy;Jason Iness;B. Mukherjee