The minimum degree Group Steiner problem
The minimum degree Group Steiner problem
复制标题
最小度斯坦纳群问题
DOI：
10.1016/j.dam.2021.12.003
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Nutov, Zeev
中科院分区：
文献类型：
--
作者：
Kortsarz, Guy;Nutov, Zeev
给定一个无向图G (V， E)，一个群集合S={S i} i= 1 q, S i≥≥1 q， S i≥≥≥≥1个顶点的树，使得最大度最小。这个问题是由在线算法Hajiaghayi（2016）激发的，并且在VLSI设计和快速广播中有应用。在WDB-GST问题中，每个顶点v都有单独的度界dv，每个e∈e都有一个代价c (e) >0 0。目标是找到一棵树，在每一组中至少包含一个终端，使得对于每一个v， d eg T (v)≤d v，并且在这样的树中找到代价最小的一个。我们给出了这个问题的第一个近似值，一个(O （log 2 n), O (log 2 n)）双标准近似值比的WDB-GST问题在树的输入。这意味着DB-GST在树输入上的近似为O （log 2 n）。以前最著名的关于树木WDB-GST问题的比率是一个双标准(O (log 2n), O (log 3n))（度的近似值是O (log 3n)）比率，这是民间传说。得到O （log 2n）近似值需要仔细的案例分析，这是未知的。我们关于WDB-GST的结果概括了Garg等人（2016）的经典结果，该结果将成本近似为O (log 2 n)，但并未近似于程度。我们的主要结果是有界树宽图上BD-GST的O （log 3n）近似值。给定一个无向图G (V， E)，一个终端S的集合，一个数k，求一棵树T (V ', E ')，其中包含至少k个最小最大度的终端。我们证明，如果DB-GST问题允许一个ρ比近似，那么DB-Steiner k树问题，允许一个O （log 2 k·ρ）的期望近似。我们还证明了如果有k个组，存在一种算法能够覆盖k/4个最小极大度的组，那么对于DB-Steiner k-tree问题存在一个确定性的O （log n⋅ρ）近似。利用Guo等人（2020）的工作，我们推导了一般图上的DB-Steiner k-tree问题的O （log 3n）近似，该问题在拟多项式时间内运行。
The DB-GST problem is given an undirected graph G (V, E), and a collection of groups S={S i} i= 1 q, S i⊆ V, find a tree that contains at least one vertex from every group S i, so that the maximum degree is minimal. This problem was motivated by On-Line algorithms Hajiaghayi (2016), and has applications in VLSI design and fast Broadcasting. In the WDB-GST problem, every vertex v has individual degree bound d v, and every e∈ E has a cost c (e)> 0. The goal is, to find a tree that contains at least one terminal from every group, so that for every v, d e g T (v)≤ d v, and among such trees, find the one with minimum cost. We give the first approximation for this problem, an (O (log 2 n), O (log 2 n)) bicriteria approximation ratio the WDB-GST problem on trees inputs. This implies an O (log 2 n) approximation for DB-GST on tree inputs. The previously best known ratio for the WDB-GST problem on trees was a bicriterion (O (log 2 n), O (log 3 n))(the approximation for the degrees is O (log 3 n)) ratio which is folklore. Getting O (log 2 n) approximation requires careful case analysis and was not known. Our result for WDB-GST generalizes the classic result of Garg et al.(2016) that approximated the cost within O (log 2 n), but did not approximate the degree. Our main result is an O (log 3 n) approximation for BD-GST on Bounded Treewidth graphs. The DB-Steiner k-tree problem is given an undirected graph G (V, E), a collection of terminals S⊆ V, and a number k, find a tree T (V′, E′) that contains at least k terminals, of minimum maximum degree. We prove that if the DB-GST problem admits a ρ ratio approximation, then the DB-Steiner k-tree problem, admits an O (log 2 k⋅ ρ) expected approximation. We also show that if there are k groups, there exists an algorithm that is able to cover k/4 of the groups with minimum maximal degree, then there is a deterministic O (log n⋅ ρ) approximation for DB-Steiner k-tree problem. Using the work of Guo et al.(2020) we derive an O (log 3 n) approximation for DB-Steiner k-tree problem on general graphs, that runs in quasi-polynomial time.
具有度数约束的网络设计
DOI：
--
发表时间：
2011
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
R. Khandekar;G. Kortsarz;Zeev Nutov
通讯作者：
Zeev Nutov
超越度量嵌入：在有界树宽图上近似群 Steiner 树
DOI：
10.1137/1.9781611974782.47
发表时间：
2017
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Parinya Chalermsook;Syamantak Das;Bundit Laekhanukit;Daniel Vaz
通讯作者：
Daniel Vaz
一种用于 VLSI/ULSI 物理设计的高效低度 RMST 算法
DOI：
--
发表时间：
2004
期刊：
International Workshop on Power and Timing Modeling, Optimization and Simulation
影响因子：
--
作者：
Yin Wang;Xianlong Hong;Tong Jing;Yang Yang;Xiaodong Hu;G. Yan
通讯作者：
G. Yan