✦ LIBER ✦

An approximation scheme for some Steiner tree problems in the plane

✍ Scribed by Wang, Lusheng; Jiang, Tao

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 536 KB
Volume: 28
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199612)28:4<187::aid-net3>3.0.co;2-h

No coin nor oath required. For personal study only.

✦ Synopsis

We design a polynomial-time approximation scheme for the Steiner tree problem in the plane when the given set of regular points is c-local, i.e., in the minimum-cost spanning tree for the given set of regular points, the length of the longest edge is at most c times the length of the shortest edge. The algorithm works for both Euclidean and rectilinear metrics. For a fixed number k , the performance ratio of our algorithm is 1 + (35c/&) for the Euclidean metric and 1 + (9c/k) for the rectilinear metric. Thus, when k increases, the performance ratio approaches 1.

📜 SIMILAR VOLUMES

An improved approximation scheme for the

An improved approximation scheme for the Group Steiner Problem

✍ C. S. Helvig; Gabriel Robins; Alexander Zelikovsky 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 322 KB 👁 1 views

the Group Steiner Problem asks for a minimumcost tree which contains at least one node from each group N i N i N i . In this paper, we give polynomial-time O O O(k k k )approximation algorithms for any fixed > > > 0. This result improves the previously known O O O(k k k)-approximation. We also apply

A Polylogarithmic Approximation Algorith

A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem

✍ Naveen Garg; Goran Konjevod; R. Ravi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 130 KB

The group Steiner tree problem is a generalization of the Steiner tree problem where we are given several subsets (groups) of vertices in a weighted graph, and the goal is to find a minimum-weight connected subgraph containing at least one vertex from each group.The problem was introduced by Reich a

A New Approximation Algorithm for the St

A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3

✍ Hans Jürgen Prömel; Angelika Steger 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 100 KB

In this paper we present an RNC approximation algorithm for the Steiner tree problem in graphs with performance ratio 5r3 and RNC approximation algorithms for the Steiner tree problem in networks with performance ratio 5r3 q ⑀ for all ⑀ ) 0. This is achieved by considering a related problem, the min

Local search with perturbations for the

Local search with perturbations for the prize-collecting Steiner tree problem in graphs

✍ S. A. Canuto; M. G. C. Resende; C. C. Ribeiro 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB

Probabilistic analysis of an lp relaxati

Probabilistic analysis of an lp relaxation bound for the steiner problem in networks

✍ Anjani Jain 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 395 KB

Posing an inverse problem for the Helmho

Posing an inverse problem for the Helmholtz equation in a half plane

✍ Frank Penzel 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB 👁 1 views

## Abstract In this paper we shall define an inverse problem for the Helmholtz equation with imaginary part of the wave number being positive. The Cauchy data are known on the boundary of the half plane, but it is not known where the half axis, lying vertically in the upper half plane, is situated.