Approximation algorithms for constructing spanning K-trees using stock pieces of bounded length
Approximation algorithms for constructing spanning K-trees using stock pieces of bounded length
复制标题
使用有界长度的库存片段构造生成 K 树的近似算法
DOI：
10.1007/s11590-016-1078-5
复制
发表时间：
2016-09
影响因子：
1.6
通讯作者：
Ko-Wei Lih
中科院分区：
文献类型：
--
作者：
Junran Lichen;Jianping Li;Ko-Wei Lih
给定一个权图Gon顶点，定义G的扩张K-树为G的一个生成树T，其中G的K条不同边不是T的边。最小生成K-树问题的目标是选择一个边的子集，以形成一个具有最小权值的生成K-树。本文研究了生成K树问题，它是最小生成K树问题的推广。我们需要构造一个生成K-树，它的边是由一些有界长度L的库存块组装而成的。设为每一长度的库存件的销售价格，以及用于构建边缘的最小库存件的数量。对于每个边缘G，c（e）为该边缘的建造成本。我们的新目标是最小化构造生成K-树的总代价，即，。本文得到的主要结果如下。(1)构造生成K-树问题的一个2-近似算法。(2)A-近似算法解决了边的构造成本为常数的特殊情况。(3)APTAS是针对这种特殊情况的。
Given a weighted graphGonvertices, aspanning K-treeofGis defined to be a spanning treeTofGtogether withKdistinct edges ofGthat are not edges ofT. The objective of the minimum-cost spanningK-tree problem is to choose a subset of edges to form a spanningK-tree with the minimum weight. In this paper, we considerthe constructing spanning K-tree problemthat is a generalization of the minimum-cost spanningK-tree problem. We are required to construct a spanningK-treewhoseedges are assembled from some stock pieces of bounded lengthL. Letbe the sale price of each stock piece of lengthLandthe number of minimum stock pieces to construct theedges in. For each edgeeinG, letc(e) be the construction cost of that edgee. Our new objective is to minimize the total cost of constructing a spanningK-tree, i.e.,. The main results obtained in this paper are as follows. (1) A 2-approximation algorithm to solve the constructing spanningK-tree problem. (2) A-approximation algorithm to solve the special case for constant construction cost of edges. (3) An APTAS for this special case.
登录
查看更多内容
DOI：
10.1287/ijoc.5.4.426
发表时间：
1993-11
期刊：
INFORMS J. Comput.
影响因子：
--
作者：
M. Fischetti;P. Toth
通讯作者：
M. Fischetti;P. Toth
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)
影响因子：
--
作者：
通讯作者：
--
影响因子：
3.7
作者：
C. Berge;A. Ghouila-Houri;M. Merrington;C. Ramanujacharyulu
通讯作者：
C. Berge;A. Ghouila-Houri;M. Merrington;C. Ramanujacharyulu
DOI：
10.1093/comjnl/9.2.166
发表时间：
1966-08
期刊：
The Computer Journal
影响因子：
--
作者：
K. Haley
通讯作者：
K. Haley
DOI：
10.1109/cdc.1977.271650
发表时间：
1977-12
期刊：
1977 IEEE Conference on Decision and Control including the 16th Symposium on Adaptive Processes and A Special Symposium on Fuzzy Set Theory and Applications
影响因子：
--
作者：
Edwin Roberts
通讯作者：
Edwin Roberts