20341554
On greedy heuristics for steiner minimum trees
We disprove a conjecture of Shor and Smith on a greedy heuristic for the Steiner minimum tree by showing that the length ratio between the Steiner minimum tree and the greedy tree constructed by their method for the same set of points can be arbitrarily close to√3/2. We also propose a new conjecture.
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.
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.
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.
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.
206027538
A coloring problem on the n-cube
Abstract In this paper, we consider a coloring problem on the n-cube that arises in the study of scalability of optical networks. Let χ k (n) be the minimum number of colors needed to color the vertices of the n-cube so that every two vertices with Hamming distance ⩽k have different colors. We show that for k=3, 2n⩽χ 3 (n)⩽2 ⌈ log 2 n⌉+1 . We also provide upper and lower bounds on χ k (n) for general k.
2477251
PCR-assist CBR for delivering pre-recorded MPEG-2 transport streams
Transmitting compressed variable bit-rate (VBR) video with a traditional constant bit-rate (CBR) service for continuous playback requires a large buffer on the viewer's side. In this paper, we study a new CBR transmission scheme which employs the program clock references (PCR) that are embedded in the MPEG-2 transport streams to reduce the buffer requirement. The scheme is called "PCR-assist CBR" (PCBR). The PCBR scheme uses PCRs to examine its transmission regularly. It holds up the transmission if it is ahead of schedule. Based on experimental results with video traces, the PCBR scheme reduces the buffer requirement at the cost of a higher transmission rate.
8600977
Optimal preemptive semi-online scheduling on two uniform processors
We investigate a preemptive semi-online scheduling problem. Jobs with sizes within a certain range [1, r] (r≥1 ) arrive one by one to be scheduled on two uniform parallel processors with speed 1 and s≥1, respectively. The objective is to minimize makespan. We characterize the optimal competitive ratio as a function of both s and r by devising a deterministic on-line scheduling algorithm along with a matching lower bound, which also holds for randomized algorithms.
18860643
The multiroute maximum flow problem revisited
We are given a directed network G = (V, A, u) with vertex setV , arc setA, a source vertexs ∈ V , a destination vertex t ∈ V , a finite capacity vector u = {uij}ij∈A, and a positive integerm ∈ Z+. The multiroute maximum flow problem ( m-MFP) generalizes the ordinary maximum flow problem by seeking a maximum flow from s to t subject to not only the regular flow conservation constraints at the vertices (except s andt) and the flow capacity constraints at the arcs, but also the extra constraints that any flow must be routed alon g m arc-disjoints-t paths. In this paper, we devise two new combinatorial algorithms for m-MFP. One is based on Newton’s method and another is based on augmenting-path technique. We also show how the Newton-based algorithm unifies two existing algorithms, and how the augmen ting-path algorithm is strongly polynomial for case m = 2.
11088545
Supporting Random Access on Real-Time Retrieval of Digital Continuous Media
In addition to the large data size requirement and real-time constraint in continuous media, future video applications such as video editing demand a random access capability at the video-frame level. This paper introduces our study on effective buffering control for the real-time retrieval of jitter-free digital video medium. We adopt a video-frame level approach to maintaining the flexibility on placement and analysing the efficiency of the buffering schemes. An integrated solution which offers efficient buffering schemes and flexible storage placement to support random access is our goal. We present two buffering schemes: the two-buffer scheme and the k-buffer compensation scheme. The two-buffer scheme requires that all the frames in a block are stored consecutively, while providing random access between blocks. However, this intuitive buffering scheme potentially requires a large block size and buffer space. The k-buffer compensation scheme is proposed to resolve this large buffer space requirement, by using more than two buffers and requiring a minimal number of blocks randomly placed in each cylinder. This scheme differs from the contiguous placement scheme because individual blocks can be stored anywhere in each cylinder. Compared to the two-buffer scheme, the k-buffer compensation scheme requires less buffer space, has higher disk utilization and finer granularity on disk data transfer. The placement requirements are more flexible and implementable than the contiguous and storage pattern placement schemes. Experimental measurement results reveal the significant improvements on the buffer-size reduction and placement flexibility by using the k-buffer compensation scheme. Extensions of the k-buffer compensation scheme to support multiple streams are also addressed.
7236819
Creating a virtual network laboratory
Networking courses are traditionally conceptual in nature, with little opportunity for students to apply what they have learned in order to strengthen their knowledge. To support these courses, the University of Minnesota established a hands-on network laboratory. Educational and operational concerns have surfaced throughout the years due to the physical laboratory constraints and difficulty of satisfying the high demand. To address these issues, and to overcome the shortcomings of current approaches, we are developing a virtual network laboratory environment to eliminate most of the constraints, though it is not necessarily replacing all of the physical settings at once. The kernel consists of a collection of online multimedia learning modules which integrate the key laboratory devices with instructional material. The modules are designed to allow students to carry out hands-on networking in a virtual environment or through remote access. This virtual laboratory is easily accessible over the Internet.