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.
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.
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.
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.
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.
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
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.
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.
36724744
A decomposition theorem on Euclidean Steiner minimal trees
The Euclidean Steiner minimal tree problem is known to be an NP-complete problem and current alogorithms cannot solve problems with more than 30 points. Thus decomposition theorems can be very helpful in extending the boundary of workable problems. There have been only two known decomposition theorems in the literature. This paper provides a 50% increase in the reservoir of decomposition theorems.
39689433
On 1-rate Wide-sense Nonblocking for 3-stage Clos Networks
Abstract This paper considers the multirate environment in which each network link has a unity capacity and each call is associated with a rate w, 1 ⩾ w>0. The multirate environment is reduced to the 1 -rate environment if all rates are identical. Circuit switching is a special case of 1 -rate in which the constant rate is w = 1. We establish some general relations between wide-sense nonblocking in circuit switching and 1-rate wide-sense nonblocking for the 3-stage Clos network. We also give necessary and sufficient conditions for a 3-stage Clos network with two input switches and two output switches to be wide-sense nonblocking, and give a necessary condition when there are three input switches and three output switches. We conjecture that 1-rate wide-sense nonblocking implies circuit switching wide-sense nonblocking and give some partial evidence.
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.