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.
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.
35793386
An improved algorithm for decomposing arc flows into multipath flows
We consider a multipath maximum flow problem introduced by Kishimoto (Networks 27(4)(1996)279-291). The focus is on efficient transformation from arc flows into multipath flows, where a multipath flow is a nonnegative combination of multipaths. A new algorithm that is more efficient than existing ones is proposed for the transformation.
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
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.
16833982
The k-level facility location game
We propose a cost-sharing scheme for the k-level facility location game that is cross-monotonic, competitive, and 6-approximate cost recovery. This extends the recent result for the 1-level facility location game of Pal and Tardos.
30320002
A Short Proof of a Result of Pollak on Steiner Minimal Trees
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 32. This conjecture was shown to be true for n = 3 by Gilbert and Pollak, and for n = 4 by Pollak. However, the proof for n = 4 by Pollak is sufficiently complicated that no generalization to any other value of n has been found. We use a different approach to give a very short proof for the n = 4 case. This approach also allows us to attack the n = 5 case, though the proof is no longer short (to be reported in a subsequent paper).
42394808
on Component-size Bounded Steiner Trees
A Steiner tree is a tree interconnecting a given set of points in a metric space such that all leaves are given points. A (full) component of a Steiner tree is a subtree which results from splitting the Steiner tree at some given points. A k-size Steiner tree is a Steiner tree in which every component has at most k given points. The k-Steiner ratio is the largest lower bound for the ratio between lengths of a minimum Steiner tree and a minimum k-size Steiner tree for the same set of points. In this paper, we determine the 3-Steiner ratio in weighted graphs.
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.
24107558
Lower Bounds on the Minus Domination and k-Subdomination Numbers
A three-valued function f defined on the vertex set of a graph G = (V,E), f : V → {-1, 0, 1} is a minus dominating function if the sum of its function values over any closed neighborhood is at least one. That is, for every v ∈ V, f(N[v]) ≥ 1, where N[v] consists of v and all vertices adjacent to v. The weight of a minus function is f(V) = Σv∈V f(v). The minus domination number of a graph G, denoted by γ-(G), equals the minimum weight of a minus dominating function of G. In this paper, sharp lower bounds on minus domination of a bipartite graph are given. Thus, we prove a conjecture proposed by J. Dunbar etc. (Discrete Math. 199(1999) 35-47), and we give a lower bound on γks(G) of a graph G.
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.