32794956
The Steiner Ratio Conjecture Is True for Five Points
Abstract The long-standing conjecture of Gilbert and Pollak states that for any set of n given points in the Euclidean plane, the ratio of the length of a Steiner minimal tree and the length of a minimal (spanning) tree is at least 3 2 . This conjecture was shown to be true for n = 3 by Gilbert and Pollak, and for n = 4 by Pollak. Recently, Du, Yao and Hwang used a different approach to give a shorter proof for n = 4. In this paper we continue this approach to prove the conjecture for n = 5. Such results for small n are useful in obtaining bounds for the ratio of the two lengths in the general case.
36038781
A proof of the Gilbert-Pollak conjecture on the Steiner ratio
LetP be a set ofn points on the euclidean plane. LetLs(P) andLm(P) denote the lengths of the Steiner minimum tree and the minimum spanning tree onP, respectively. In 1968, Gilbert and Pollak conjectured that for anyP,Ls(P)≥(√3/2)Lm(P). We provide a proof for their conjecture in this paper.
30354625
A class of full Steiner minimal trees
A Steiner minimal tree for a given set of points in the plane is a tree which interconnects these points using lines of shortest possible total length. We construct an infinite class of trees which are the unique full Steiner minimal trees for their sets of endpoints (vertices of degree one).
43203779
The k-Steiner ratio in graphs
A Steiner minimum tree, SMT, is the shortest length tree in a metric space interconnecting a set of points, called the regular points, possibly using additional vertices. A k-size Steiner minimum tree, kSMT, is one that can be split into components where all regular points are leaves and all components have at most k leaves. The k-$lteiner ratio, pk, is the infimum of the ratios SMT/kSMT over all sets of regular points in all possible metric spaces, where the distances are given by a complete graph. Previously only p2 and p3 in graphs had been known exactly, and some bounds where know for the others. In this paper we determine pk exactly for all k.
14358235
New bounds on a hypercube coloring problem
In studying the scalability of optical networks, one problem which arises involves coloring the vertices of the n-cube with as few colors as possible such that any two vertices whose Hamming distance is at most k are colored differently. Determining the exact value of χ??(n), the minimum number of colors needed, appears to be a difficult problem. In this note, we improve the known lower and upper bounds of χ??(n) and indicate the connection of this coloring problem to linear codes.
2453836
On connectivity of consecutive-d digraphs
The concept of a consecutive-d digraph was proposed by Du, Hsu and Hwang as a generalization of de Bruijn digraphs, Kautz digraphs, and their generalizations given by Imase and Itoh and Reddy, Pradhan and Kuhl. In this paper, we determine the connectivity of consecutive-d digraphs and study how to modify consecutive-d digraphs to reach maximum connectivity. Our results will generalize and improve several existing results on the connectivity of de Bruijn digraphs, Kautz digraphs and Imase-Itoh digraphs.
16471624
Preemptive on-line scheduling for two uniform processors
This paper considers the problem of preemptive on-line scheduling for two uniform processors in which one of the processors has speed 1 and the other has speed s>=1. The objective is to minimize the makespan. A best possible algorithm with competitive ratio of (1+s)^2/(1+s+s^2) is proposed for this problem.
9780632
An integrated admission control scheme for the delivery of streaming media
Quality of service (QoS) assurance is a major concern in media-on-demand (MoD) systems. Admission control is one of the most important issues that need to be addressed for QoS assurance. Also, smoothing is a basic technique for the media server to improve its bandwidth and buffer utilization. However, existing approaches cannot achieve the best resource utilization because (1) they cannot fully utilize the time-varying buffer spaces available at both server and client sides due to the separation of admission control and smoothing processes, and (2) the computing time is unacceptable for media of long duration. In this paper, we formulate the admission control as an integer programming problem and propose several heuristic methods for solving the problem. Specially, we introduce an efficient scheme, called batched admission (BA) scheme, which integrates admission control, transmission rate smoothing, and batching, to achieve best resource utilization with guaranteed QoS. Experimental studies show that the BA scheme outperforms existing approaches.
16666020
On-line Network Synthesis
We consider on-line network synthesis problems. Let N = {1, , n} be a set of n sites. Trafﬁc ﬂow requirements between pairs of sites are revealed one by one. Whenever a new request rij = rji (i < j) between sites i and j is revealed, an on-line algorithm must install the additional necessary capacity without decreasing the existing network capacity such that all the trafﬁc requirements are met. The objective is to minimize the total capacity installed by the algorithm. The performance of an on-line algorithm is measured by the competitive ratio, deﬁned to be the worst-case ratio between the total capacity by the on-line algorithm and the total optimal (off-line) capacity assuming we have priori information on all the requirements initially. We distinguish between two on-line versions of the problem depending on whether the entire set of sites is known a prior or not. For the ﬁrst version where the entire set of site is unknown, we present a best possible algorithm along with a matching lower bound. For the second version where the entire set of sites is known a priori, we present a best possible algorithm for n ≤ 6. 
 
Key words: On-line algorithm; Approximation algorithm; Network synthesis; Competitive analysis
9933311
The k-Steiner Ratio in the Rectilinear Plane
A Steiner minimum tree (SMT) in the rectilinear plane is the shortest length tree interconnecting a set of points, called the regular points, possibly using additional vertices. Ak-size Steiner minimum tree (kSMT) is one that can be split into components where all regular points are leaves and all components have at mostkleaves. Thek-Steiner ratio in the rectilinear plane, ?k, is the infimum of the ratios SMT/kSMT over all finite sets of regular points. Thek-Steiner ratio is used to determine the performance ratio of several recent polynomial-time approximations for Steiner minimum trees. Previously it was known that in the rectilinear plane, ?2=2/3, ?3=4/5, and (2k?2)/(2k?1)??k(L1)?(2k?1)/(2k) fork?4. In 1991, P. Berman and V. Ramaiyer conjectured that in fact ?k=(2k?1)/(2k) fork?4. In this paper we prove their conjecture.
17041567
On-line scheduling of small open shops
We investigate the problem of on-line scheduling open shops of two and three machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive scheduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines, which is most competitive.