.
"Berman" .
.
.
"sum" .
"Applied Mathematics" .
_:N374b4455dc1a4e5b85129048fac3c65a _:N27efb7a6c8cb494fb6b937230b52f0e5 .
"best approximation algorithm" .
_:N6af69c86c5a3403cb9983fc70c2cee06 "Advances in Steiner Trees" .
"one" .
"number" .
"Department of Computer Science and Engineering, Penn State University, 16802, University Park, PA, USA" .
"number of terminals" .
"version" .
_:N982b819748914ab8b37292d1a1b61f99 .
_:N3e2f3cd0d01b489c99590063f1d562e6 "dimensions_id" .
_:N802daeba55ad473fbcf916f26b03f872 .
.
.
"2000" .
.
"Department of Computer Science, Georgia State University, University Plaza, 30303-3083, Atlanta, GA, USA" .
_:N476ede3187b94cc5a79393253affd748 "Springer Nature" .
"approximation algorithm" .
_:N885af3df680c4eadb0763b4a975da5f7 "Ding-Zhu" .
_:N802daeba55ad473fbcf916f26b03f872 _:Naf6af941e5584362b766cc4bf1f5a4a8 .
_:N982b819748914ab8b37292d1a1b61f99 "doi" .
_:N374b4455dc1a4e5b85129048fac3c65a .
_:N3e2f3cd0d01b489c99590063f1d562e6 .
"problem" .
.
"2022-09-02T16:16" .
"edge" .
_:N885af3df680c4eadb0763b4a975da5f7 "Du" .
.
_:N27efb7a6c8cb494fb6b937230b52f0e5 "Rubinstein" .
"trees" .
"Many VLSI routing applications, as well as the facility location problem involve computation of Steiner trees with non-linear cost measures. We consider two most frequent versions of this problem. In the power-p Steiner problem the cost is defined as the sum of the edge lengths where each length is raised to the power p > 1. In the bottleneck Steiner problem the objective cost is the maximum of the edge lengths. We show that the power-p Steiner problem is MAX SNP-hard and that one cannot guarantee to find a bottleneck Steiner tree within a factor less than 2, unless P = NP. We prove that in any metric space the minimum spanning tree is at most a constant times worse than the optimal power-p Steiner tree. In particular, for p = 2, we show that the minimum spanning tree is at most 23.3 times worse than the optimum and we construct an instance for which it is 17.2 times worse. We also present a better approximation algorithm for the bottleneck Steiner problem with performance guarantee log2 n, where n is the number of terminals (the minimum spanning tree can be 2 log2 n times worse than the optimum)." .
"metric spaces" .
"Steiner problem" .
_:N6af69c86c5a3403cb9983fc70c2cee06 .
"applications" .
"VLSI" .
"frequent versions" .
"instances" .
_:N5df10e475c79446f83b29fb2f79ac43a _:Nf55ff4c2c1d246b3ab7703de9e7214a3 .
"constant time" .
"MAX SNP" .
_:Naf6af941e5584362b766cc4bf1f5a4a8 .
"NPs" .
_:N27efb7a6c8cb494fb6b937230b52f0e5 "J. H." .
_:Nf55ff4c2c1d246b3ab7703de9e7214a3 _:Ndb1c2f01fd7b4dd2ac9b408ec964e070 .
"edge length" .
_:N5df10e475c79446f83b29fb2f79ac43a _:N885af3df680c4eadb0763b4a975da5f7 .
.
_:N802daeba55ad473fbcf916f26b03f872 .
"cost" .
"2000-01-01" .
"maximum" .
.
"Zelikovsky" .
"Department of Computer Science, Georgia State University, University Plaza, 30303-3083, Atlanta, GA, USA" .
.
"117-135" .
_:N27efb7a6c8cb494fb6b937230b52f0e5 .
_:N8456f4ab719448c481caf29068f830b2 .
_:Naf6af941e5584362b766cc4bf1f5a4a8 .
"approximation" .
"spanning tree" .
"computation" .
_:Ndb1c2f01fd7b4dd2ac9b408ec964e070 "J. M." .
.
"log2 n" .
_:Ndb1c2f01fd7b4dd2ac9b408ec964e070 "Smith" .
_:N982b819748914ab8b37292d1a1b61f99 .
"time" .
_:N476ede3187b94cc5a79393253affd748 .
_:N8456f4ab719448c481caf29068f830b2 .
.
"Piotr" .
.
"minimum spanning tree" .
"facility location problem" .
"location problem" .
"power P" .
_:N6af69c86c5a3403cb9983fc70c2cee06 .
_:N8456f4ab719448c481caf29068f830b2 "Springer Nature - SN SciGraph project" .
"chapter" .
_:N982b819748914ab8b37292d1a1b61f99 "10.1007/978-1-4757-3171-2_7" .
.
.
"power" .
_:N885af3df680c4eadb0763b4a975da5f7 .
"Mathematical Sciences" .
"Steiner tree" .
_:N476ede3187b94cc5a79393253affd748 .
"space" .
.
_:N6af69c86c5a3403cb9983fc70c2cee06 "978-1-4757-3171-2" .
"bottleneck Steiner tree" .
"factors" .
_:Nf55ff4c2c1d246b3ab7703de9e7214a3 _:N374b4455dc1a4e5b85129048fac3c65a .
"false"^^ .
"measures" .
"length" .
_:N3e2f3cd0d01b489c99590063f1d562e6 "pub.1035699208" .
"https://doi.org/10.1007/978-1-4757-3171-2_7" .
"On Approximation of the Power-p and Bottleneck Steiner Trees" .
_:N3e2f3cd0d01b489c99590063f1d562e6 .
_:N5df10e475c79446f83b29fb2f79ac43a .
.
_:N6af69c86c5a3403cb9983fc70c2cee06 "978-1-4419-4824-3" .
"https://scigraph.springernature.com/explorer/license/" .
"chapters" .
"Department of Computer Science and Engineering, Penn State University, 16802, University Park, PA, USA" .
"cost measures" .
"SNPs" .
"Alexander" .
_:Ndb1c2f01fd7b4dd2ac9b408ec964e070 .
"algorithm" .
"terminals" .
"objective cost" .