Grade of Service Steiner Minimum Trees in the Euclidean Plane

Abstract. Let P = {p ₁ , p ₂ , \ldots, p _n } be a set of n {\lilsf terminal points} in the Euclidean plane, where point p _i has a {\lilsf service request of grade} g(p _i ) ∈ {1, 2, \ldots, n} . Let 0 < c(1) < c(2) < ⋅s < c(n) be n real numbers. The {\lilsf Grade of Service Steiner Minimum Tree (GOSST)} problem asks for a minimum cost network interconnecting point set P and some {\lilsf Steiner points} with a service request of grade 0 such that (1) between each pair of terminal points p _i and p _j there is a path whose minimum grade of service is at least as large as \min(g(p _i ), g(p _j )) ; and (2) the cost of the network is minimum among all interconnecting networks satisfying (1), where the cost of an edge with service of grade g is the product of the Euclidean length of the edge with c(g) . The GOSST problem is a generalization of the Euclidean Steiner minimum tree problem where all terminal points have the same grade of service request. When there are only two (three, respectively) different grades of service request by the terminal points, we present a polynomial time approximation algorithm with performance ratio \frac 4 3 ρ (((5+4\sqrt 2 )/7)ρ , respectively), where ρ is the performance ratio achieved by an approximation algorithm for the Euclidean Steiner minimum tree problem. For the general case, we prove that there exists a GOSST that is the minimum cost network under a full Steiner topology or its degeneracies. A powerful interior-point algorithm is used to find a (1+ε) -approximation to the minimum cost network under a given topology or its degeneracies in O(n ^1.5 (log n + log (1/ε))) time. We also prove a lower bound theorem which enables effective pruning in a branch-and-bound method that partially enumerates the full Steiner topologies in search for a GOSST. We then present a k -optimal heuristic algorithm to compute good solutions when the problem size is too large for the branch-and-bound algorithm. Preliminary computational results are presented.     

Approximating Shortest Paths on Weighted Polyhedral Surfaces

One common problem in computational geometry is that of computing shortest paths between two points in a constrained domain. In the context of Geographical Information Systems (GIS), terrains are often modeled as Triangular Irregular Networks (TIN) which are a special class on non-convex polyhedra. It is often necessary to compute shortest paths on the TIN surface which takes into account various weights according to the terrain features. We have developed algorithms to compute approximations of shortest paths on non-convex polyhedra in both the unweighted and weighted domain. The algorithms are based on placing Steiner points along the TIN edges and then creating a graph in which we apply Dijkstra's shortest path algorithm. For two points s and t on a non-convex polyhedral surface P , our analysis bounds the approximate weighted shortest path cost as || Π'(s,t)|| ≤ ||Π(s,t)|| + W |L| , where L denotes the longest edge length of \cal P and W denotes the largest weight of any face of P . The worst case time complexity is bounded by O(n ⁵ ) . An alternate algorithm, based on geometric spanners, is also provided and it ensures that ||Π' (s,t)|| ≤β(||Π(s,t)|| + W|L|) for some fixed constant β >1 , and it runs in O(n ³ log n) worst case time. We also present detailed experimental results which show that the algorithms perform much better in practice and the accuracy is near-optimal. Received April 15, 1998; revised February 15, 1999.     

Exact Algorithms for the Bottleneck Steiner Tree Problem

Given n points, called terminals, in the plane ℝ² and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ² and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ², usually, the Euclidean or the L ₁ metric. This problem is known to be NP-hard. In this paper, we study this problem in the L _p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog ² n time for the L ₁ and the L _∞ metrics, and the first exact algorithm for the L _p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n ^k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L ₂ metric.     

On Exact Solutions for the Rectilinear Steiner Tree Problem Part I: Theoretical Results

The rectilinear Steiner tree problem asks for a shortest tree connecting given points in the plane with rectilinear distance. The best theoretically analyzed algorithms for this problem are based on dynamic programming and have a running time of O(n ² . . . 2.62 ⁿ ) (Ganley and Cohoon), resp. (Smith). The first algorithm can solve problems of size 27, the second one is highly impractical because of the large constant in the exponent. The best implementations perform poorly even on small problem instances; the best practical results can be reached using a Branch \& Bound approach (Salowe and Warme); this implementation can solve random problems of size 35 within a day, while the dynamic programming approach of Ganley and Cohoon can handle only 27 point examples. In this paper we improve the theoretical worst-case time bound to O(n ² . . . 2.38 ⁿ ) , for random problem instances we prove a running time of α ⁿ with a constant α < 2 . We have implemented our algorithms and can now solve problems of 40 points in a day using a provably good dynamic programming approach, and can solve problems of 55 points with a Branch \& Bound strategy. For exponential-time algorithms, this is an enormous improvement. Received April 2, 1997; revised January 5, 1998.     

Steiner Minimal Trees with One Polygonal Obstacle

In this paper we study the Steiner minimal tree T problem for a point set Z with cardinality n and one polygonal obstacle ω in the Euclidean plane. We assume ω touches only one convex path in T that joins two terminals and that the number of extreme points of the obstacle is k . If all degree 2 vertices are omitted, then the topology of T is called the primitive topology of T . Given a full primitive topology along with ω convex, we prove that T can be determined in O(n ² +nlog ² k) time. Further, if ω is nonconvex, we then show that O(n ² +nklog k) time is required. Received April 16, 1996; revised August 18, 1997.     

A 3-Party Simultaneous Protocol for SUM-INDEX

Abstract. We show that the SUM-INDEX function can be computed by a 3-party simultaneous protocol in which one player sends only O(n ^ɛ ) bits and the other sends O(n ^1-C(ɛ) ) bits (0<C(ɛ)<1 ). This implies that, in the Valiant—Nisan—Wigderson approach for proving circuit lower bounds, the SUM-INDEX function is not suitable as a target function.     

Covering Many or Few Points with Unit Disks

Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems. In the first problem we want to place m unit disks, for a given constant m≥1, such that the total weight of the points from P inside the union of the disks is maximized. We present algorithms that compute, for any fixed ε>0, a (1−ε)-approximation to the optimal solution in O(nlog n) time. In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that computes, for any fixed ε>0, in O(nlog ² n) expected time a disk that is, with high probability, a (1+ε)-approximation to the optimal solution. A preliminary version of this work has appeared in Approximation and Online Algorithms—WAOA 2006, LNCS, vol. 4368.     

Grade of Service Steiner Minimum Trees in the Euclidean Plane

Abstract. Let P = {p ₁ , p ₂ , \ldots, p _n } be a set of n {\lilsf terminal points} in the Euclidean plane, where point p _i has a {\lilsf service request of grade} g(p _i ) ∈ {1, 2, \ldots, n} . Let 0 < c(1) < c(2) < ?s < c(n) be n real numbers. The {\lilsf Grade of Service Steiner Minimum Tree (GOSST)} problem asks for a minimum cost network interconnecting point set P and some {\lilsf Steiner points} with a service request of grade 0 such that (1) between each pair of terminal points p _i and p _j there is a path whose minimum grade of service is at least as large as \min(g(p _i ), g(p _j )) ; and (2) the cost of the network is minimum among all interconnecting networks satisfying (1), where the cost of an edge with service of grade g is the product of the Euclidean length of the edge with c(g) . The GOSST problem is a generalization of the Euclidean Steiner minimum tree problem where all terminal points have the same grade of service request. When there are only two (three, respectively) different grades of service request by the terminal points, we present a polynomial time approximation algorithm with performance ratio \frac 4 3 ρ (((5+4\sqrt 2 )/7)ρ , respectively), where ρ is the performance ratio achieved by an approximation algorithm for the Euclidean Steiner minimum tree problem. For the general case, we prove that there exists a GOSST that is the minimum cost network under a full Steiner topology or its degeneracies. A powerful interior-point algorithm is used to find a (1+ε) -approximation to the minimum cost network under a given topology or its degeneracies in O(n ^1.5 (log n + log (1/ε))) time. We also prove a lower bound theorem which enables effective pruning in a branch-and-bound method that partially enumerates the full Steiner topologies in search for a GOSST. We then present a k -optimal heuristic algorithm to compute good solutions when the problem size is too large for the branch-and-bound algorithm. Preliminary computational results are presented.     

On the performance of Dijkstra’s third self-stabilizing algorithm for mutual exclusion and related algorithms

In Dijkstra (Commun ACM 17(11):643–644, 1974) introduced the notion of self-stabilizing algorithms and presented three such algorithms for the problem of mutual exclusion on a ring of n processors. The third algorithm is the most interesting of these three but is rather non intuitive. In Dijkstra (Distrib Comput 1:5–6, 1986) a proof of its correctness was presented, but the question of determining its worst case complexity—that is, providing an upper bound on the number of moves of this algorithm until it stabilizes—remained open. In this paper we solve this question and prove an upper bound of 3\frac1318 n² + O(n){3\frac{13}{18} n^2 + O(n)} for the complexity of this algorithm. We also show a lower bound of 1\frac56 n² - O(n){1\frac{5}{6} n^2 - O(n)} for the worst case complexity. For computing the upper bound, we use two techniques: potential functions and amortized analysis. We also present a new-three state self-stabilizing algorithm for mutual exclusion and show a tight bound of \frac56 n² + O(n){\frac{5}{6} n^2 + O(n)} for the worst case complexity of this algorithm. In Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) presented a similar three-state algorithm, with an upper bound of 5\frac34n²+O(n){5\frac{3}{4}n^2+O(n)} and a lower bound of \frac18n²-O(n){\frac{1}{8}n^2-O(n)} for its stabilization time. For this algorithm we prove an upper bound of 1\frac12n² + O(n){1\frac{1}{2}n^2 + O(n)} and show a lower bound of n ²−O(n). As far as the worst case performance is considered, the algorithm in Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) is better than the one in Dijkstra (Commun ACM 17(11):643–644, 1974) and our algorithm is better than both.     

近乎最佳的Manhattan型Steiner树近似算法

求解最佳的Manhattan型Steiner树问题(minimum rectilinear Steiner tree,简记为MRST问题)是在VLSI布线、网络通信中所遇到的组合优化问题,同时也是一个NP-难解问题.该文给出对该问题的O(n²)时间复杂性的近似算法.该算法在最坏情况下的近似比严格小于3/2.计算机实验结果表明,所求得的支撑树的平均费用与最佳算法的平均费用仅相差0.8%.该算法稍加修改,可应用到三维或多维的Manhattan空间对Steiner问题求解,且易于在并行与分布式环境下编程实现     

Subcubic Cost Algorithms for the All Pairs Shortest Path Problem

In this paper we give three subcubic cost algorithms for the all pairs shortest distance (APSD) and path (APSP) problems. The first is a parallel algorithm that solves the APSD problem for a directed graph with unit edge costs in O(log ² n) time with processors where μ = 2.688 on an EREW PRAM. The second parallel algorithm solves the APSP, and consequently APSD, problem for a directed graph with nonnegative general costs (real numbers) in O(log ² n) time with o(n ³ ) subcubic cost. Previously this cost was greater than O(n ³ ) . Finally we improve with respect to M the complexity O((Mn) ^μ ) of a sequential algorithm for a graph with edge costs up to M to O(M ^1/3 n ^(6+ω)/3 (log n) ^2/3 (log log n) ^1/3 ) in the APSD problem, where ω = 2.376 . Received October 15, 1995; revised June 21, 1996.     

Minimum Weight Convex Steiner Partitions

New tight bounds are presented on the minimum length of planar straight line graphs connecting n given points in the plane and having convex faces. Specifically, we show that the minimum length of a convex Steiner partition for n points in the plane is at most O(log n/log log n) times longer than a Euclidean minimum spanning tree (EMST), and this bound is the best possible. Without Steiner points, the corresponding bound is known to be Θ(log n), attained for n vertices of a pseudo-triangle. We also show that the minimum length convex Steiner partition of n points along a pseudo-triangle is at most O(log log n) times longer than an EMST, and this bound is also the best possible. Our methods are constructive and lead to O(nlog n) time algorithms for computing convex Steiner partitions having O(n) Steiner points and weight within the above worst-case bounds in both cases.     

Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols

We give a deterministic algorithm which, on input an integer n , collection \cal F of subsets of {1,2,\ldots,n} , and ɛ∈ (0,1) , runs in time polynomial in n| \cal F |/ɛ and produces a \pm 1 -matrix M with n columns and m=O(log | \cal F |/ɛ ² ) rows with the following property: for any subset F ∈ \cal F , the fraction of 1's in the n -vector obtained by coordinatewise multiplication of the column vectors indexed by F is between (1-ɛ)/2 and (1+ɛ)/2 . In the case that \cal F is the set of all subsets of size at most k , k constant, this gives a polynomial time construction for a k -wise ɛ -biased sample space of size O(log n/ɛ ² ) , compared with the best previous constructions in [NN] and [AGHP] which were, respectively, O(log n/ɛ ⁴ ) and O(log ² n/ɛ ² ) . The number of rows in the construction matches the upper bound given by the probabilistic existence argument. Such constructions are of interest for derandomizing algorithms. As an application, we present a family of essentially optimal deterministic communication protocols for the problem of checking the consistency of two files. Received October 30, 1997; revised September 17, 1999, and April 17, 2000.     

Computing the Greedy Spanner in Near-Quadratic Time

The greedy algorithm produces high-quality spanners and, therefore, is used in several applications. However, even for points in d-dimensional Euclidean space, the greedy algorithm has near-cubic running time. In this paper, we present an algorithm that computes the greedy spanner for a set of n points in a metric space with bounded doubling dimension in O(n²logn)\ensuremath {\mathcal {O}}(n^{2}\log n) time. Since computing the greedy spanner has an Ω(n ²) lower bound, the time complexity of our algorithm is optimal within a logarithmic factor.     

Geometry Helps in Bottleneck Matching and Related Problems

Let A and B be two sets of n objects in \reals ^d , and let Match be a (one-to-one) matching between A and B . Let min(Match ), max(Match ), and Σ(Match) denote the length of the shortest edge, the length of the longest edge, and the sum of the lengths of the edges of Match , respectively. Bottleneck matching— a matching that minimizes max(Match )— is suggested as a convenient way for measuring the resemblance between A and B . Several algorithms for computing, as well as approximating, this resemblance are proposed. The running time of all the algorithms involving planar objects is roughly O(n ^1.5 ) . For instance, if the objects are points in the plane, the running time of the exact algorithm is O(n ^1.5 log n ) . A semidynamic data structure for answering containment problems for a set of congruent disks in the plane is developed. This data structure may be of independent interest. Next, the problem of finding a translation of B that maximizes the resemblance to A under the bottleneck matching criterion is considered. When A and B are point-sets in the plane, an O(n ⁵ log n) -time algorithm for determining whether for some translated copy the resemblance gets below a given ρ is presented, thus improving the previous result of Alt, Mehlhorn, Wagener, and Welzl by a factor of almost n . This result is used to compute the smallest such ρ in time O(n ⁵ log ² n ) , and an efficient approximation scheme for this problem is also given. The uniform matching problem (also called the balanced assignment problem, or the fair matching problem) is to find Match ^* _U , a matching that minimizes max (Match)-min(Match) . A minimum deviation matching Match ^* _D is a matching that minimizes (1/n)Σ(Match) - min(Match) . Algorithms for computing Match ^* _U and Match ^* _D in roughly O(n ^10/3 ) time are presented. These algorithms are more efficient than the previous O(n ⁴ ) -time algorithms of Martello, Pulleyblank, Toth, and de Werra, and of Gupta and Punnen, who studied these problems for general bipartite graphs. Received October 21, 1997; revised July 16, 1998.     

Smallest Enclosing Cylinders

This paper addresses the complexity of computing the smallest-radius infinite cylinder that encloses an input set of n points in 3-space. We show that the problem can be solved in time O(n ⁴ log ^O(1) n) in an algebraic complexity model. We also achieve a time of O(n ⁴ L⋅μ(L)) in a bit complexity model where L is the maximum bit size of input numbers and μ(L) is the complexity of multiplying two L bit integers. These and several other results highlight a general linearization technique which transforms nonlinear problems into some higher-dimensional but linear problems. The technique is reminiscent of the use of Plücker coordinates, and is used here in conjunction with Megiddo's parametric searching. We further report on experimental work comparing the practicality of an exact with that of a numerical strategy. Received September 10, 1997; revised August 28, 1988.     

A Probabilistic Algorithm for k -SAT Based on Limited Local Search and Restart

Abstract. A simple probabilistic algorithm for solving the NP-complete problem k -SAT is reconsidered. This algorithm follows a well-known local-search paradigm: randomly guess an initial assignment and then, guided by those clauses that are not satisfied, by successively choosing a random literal from such a clause and changing the corresponding truth value, try to find a satisfying assignment. Papadimitriou [11] introduced this random approach and applied it to the case of 2-SAT, obtaining an expected O(n ² ) time bound. The novelty here is to restart the algorithm after 3n unsuccessful steps of local search. The analysis shows that for any satisfiable k -CNF formula with n variables the expected number of repetitions until a satisfying assignment is found this way is (2⋅ (k-1)/ k) ⁿ . Thus, for 3-SAT the algorithm presented here has a complexity which is within a polynomial factor of (\frac 4 3 ) ⁿ . This is the fastest and also the simplest among those algorithms known up to date for 3-SAT achieving an o(2 ⁿ ) time bound. Also, the analysis is quite simple compared with other such algorithms considered before.     

Fast heuristic algorithms for rectilinear steiner trees

A fundamental problem in circuit design is how to connectn points in the plane, to make them electrically common using the least amount of wire. The tree formed, a Steiner tree, is usually constructed with respect to the rectilinear metric. The problem is known to be NP-complete; an extensive review of proposed heuristics is given. An early algorithm by Hanan is shown to have anO(n logn) time implementation using computational geometry techniques. The algorithm can be modified to do sequential searching inO(n ²) total time. However, it is shown that the latter approach runs inO(n ^3/2) expected time, forn points selected from anm×m grid. Empirical results are presented for problems up to 10,000 points.     

New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem

Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4 ^k n+n ⁴). In this paper, first we present an O(3.0446 ^k n+n ⁴) fixed-parameter algorithm and an O(2.0162 ^k n ³+n ⁵) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O ^*((1+ε) ^k ) fixed-parameter algorithm, where ε>0 is an arbitrarily small constant.     

Fast Algorithms to Enumerate All Common Intervals of Two Permutations

Given two permutations of n elements, a pair of intervals of these permutations consisting of the same set of elements is called a common interval . Some genetic algorithms based on such common intervals have been proposed for sequencing problems and have exhibited good prospects. In this paper we propose three types of fast algorithms to enumerate all common intervals: (i) a simple O(n ² ) time algorithm (LHP), whose expected running time becomes O(n) for two randomly generated permutations, (ii) a practically fast O(n ² ) time algorithm (MNG) using the reverse Monge property, and (iii) an O(n+K) time algorithm (RC), where K is the number of common intervals. It will also be shown that the expected number of common intervals for two random permutations is O(1) . This result gives a reason for the phenomenon that the expected time complexity O(n) of the algorithm LHP is independent of K . Among the proposed algorithms, RC is most desirable from the theoretical point of view; however, it is quite complicated compared with LHP and MNG. Therefore, it is possible that RC is slower than the other two algorithms in some cases. For this reason, computational experiments for various types of problems with up to n=10 ⁶ are conducted. The results indicate that (i) LHP and MNG are much faster than RC for two randomly generated permutations, and (ii) MNG is rather slower than LHP for random inputs; however, there are cases in which LHP requires Ω(n ² ) time, but MNG runs in o(n ² ) time and is faster than both LHP and RC. Received December 21, 1996; revised June 2, 1998.