Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

In the classical Steiner tree problem, given an undirected, connected graph G =( V , E ) with nonnegative edge costs and a set of terminals T ⊆ V , the objective is to find a minimumcost tree E &prime ⊆ E that spans the terminals. The problem is APXhard; the bestknown approximation algorithm has a ratio of ρ = ln (4)+ε < 1.39. In this article, we study a natural generalization, the multilevel Steiner tree (MLST) problem: Given a nested sequence of terminals T ℓ ⊂ … ⊂ T 1 ⊆ V , compute nested trees E ℓ ⊆ … ⊆ E 1 ⊆ E that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names, including Multilevel Network Design, QualityofService Multicast tree, GradeofService Steiner tree, and Multitier tree. Several approximation results are known. We first present two simple O (ℓ)approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most 2ℓ Steiner tree computations. We compare these heuristicsmore »

We consider the online facility assignment problem, with a set of facilities F of equal capacity l in metric space and customers arriving one by one in an online manner. We must assign customer ci to facility fj before the next customer ci+1 arrives. The cost of this assignment is the distance between ci and fj. The total number of customers is at most Fl and each customer must be assigned to a facility. The objective is to minimize the sum of all assignment costs. We first consider the case where facilities are placed on a line so that the distance between adjacent facilities is the same and customers appear anywhere on the line. We describe a greedy algorithm with competitive ratio 4F and another one with competitive ratio F. Finally, we consider a variant in which the facilities are placed on the vertices of a graph and two algorithms in that setting.