Let S be a set of n points in 2. Given an integer 1 &le k &le n, we wish to find a maximally separated subset I ⊆ S of size k;this is a subset for which the minimum among the (k/2) pairwise distances between i...
详细信息
Let S be a set of n points in 2. Given an integer 1 &le k &le n, we wish to find a maximally separated subset I ⊆ S of size k;this is a subset for which the minimum among the (k/2) pairwise distances between its points is as large as possible. The decision problem associated with this problem is to determine whether there exists I ⊆ S, |I| = k, so that all (k/2) pairwise distances in I are at least 2, say. This problem can also be formulated in terms of disk-intersection graphs: Let D be the set of unit disks centered at the points of S. The disk-intersection graph G of D connects pairs of disks by an edge if they have nonempty intersection. I is then the set of centers of disks that form an independent set in the graph G. This problem is known to be NP-Complete if k is part of the input. In this paper we first present a linear-time approximation algorithm for any constant k. Next we give O(n4/3polylog(n)) exact algorithms for the cases k = 3 and k = 4. We also present a simpler nO(√k))-time algorithm (as compared with the recent algorithm in [5]) for arbitrary values of k.
In this paper, we present an analytical TCP model that takes into account of several issues that were ignored in the other existing models (such as those in), i.e., (i) the congestion window is not gradually decreased...
详细信息
ISBN:
(纸本)0780377524
In this paper, we present an analytical TCP model that takes into account of several issues that were ignored in the other existing models (such as those in), i.e., (i) the congestion window is not gradually decreased at the rate of w2p/2, but suddenly halved upon receipt of congestion indication and (ii) the congestion window is halved at most once during one round-trip time (RTT). We also include the delayed ACK option in the model. With the use of state feedback control theory, we then design, based on the enhanced TCP model, an AQM controller to stabilize the queue length at routers. The performance of the new controller is shown, via ns-2 simulation to outperform several other schemes under a variety of network scenarios and traffic loads, in terms of fluctuation in the queue length, link utilization, and packet loss ratio.
We present a parallel algorithm for the Concave Least Weight Subsequence (CLWS) problem that exhibits the following work-time trade-off: Given a parameter p, the algorithm runs in time using p processors. By a known r...
详细信息
We present a parallel algorithm for the Concave Least Weight Subsequence (CLWS) problem that exhibits the following work-time trade-off: Given a parameter p, the algorithm runs in time using p processors. By a known reduction of the Huffman Tree problem to the CLWS problem, we obtain the same complexity bounds for the Huffman Tree problem. However, as we show, for the later problem there exists a simpler (and, in fact, slightly better) algorithm that exhibits a similar trade-off: Namely, for a given parameter p, p≥1, the algorithm runs in time using p processors.
Path protection requires finding a working path and a protection path that are link disjoint. In this paper, we consider the dynamic lightpath protection problem in WDM mesh networks where a single risk factor may cau...
详细信息
Path protection requires finding a working path and a protection path that are link disjoint. In this paper, we consider the dynamic lightpath protection problem in WDM mesh networks under the wavelength continuity co...
详细信息
In this paper, we examine on-line learning problems in which the target concept is allowed to change over time. In each trial a master algorithm receives predictions from a large set of n experts. Its goal is to predi...
详细信息
In this paper, we examine on-line learning problems in which the target concept is allowed to change over time. In each trial a master algorithm receives predictions from a large set of n experts. Its goal is to predict almost as well as the best sequence of such experts chosen off-line by partitioning the training sequence into k + 1 sections and then choosing the best expert for each section. We build on methods developed by Herbster and Warmuth and consider an open problem posed by Freund where the experts in the best partition are from a small pool of size m. Since k m, the best expert shifts back and forth between the experts of the small pool. We propose algorithms that solve this open problem by mixing the past posteriors maintained by the master algorithm. We relate the number of bits needed for encoding the best partition to the loss bounds of the algorithms. Instead of paying log n for choosing the best expert in each section we first pay log (mn) bits in the bounds for identifying the pool of m experts and then log m bits per new section. In the bounds we also pay twice for encoding the boundaries of the sections.
In this paper, we present a matching method that can improve the classification performance of a fuzzy decision tree (FDT). This method takes into consideration prediction strength of leave nodes of a fuzzy decision t...
详细信息
ISBN:
(纸本)0780378652
In this paper, we present a matching method that can improve the classification performance of a fuzzy decision tree (FDT). This method takes into consideration prediction strength of leave nodes of a fuzzy decision tree by combining true degrees (CF) of fuzzy rules, generated from a fuzzy decision tree, with membership degrees of antecedent parts of rules when applied to cases for classification. We illustrate the importance of CF through an example. An experiment shows by using this method, we can obtain more accurate results of classification when compared to the original method and to those obtained using the C5.0 decision tree.
In order to model and analyze the data traffic behaviors with feedback mechanism in high-speed data communication system, we start from the feedback control model proposed by Rauf Izmailov, which is based on different...
详细信息
In order to model and analyze the data traffic behaviors with feedback mechanism in high-speed data communication system, we start from the feedback control model proposed by Rauf Izmailov, which is based on differential delay equations. But, instead of specifying the processing rate to be constant, we extend it to a general functional model. We also add a random item for describing the uncertainties in a real communication system. We analyze the stability and robust stability of systems with these models. Theoretically the results show that the system can be stabilized and that the buffer size can be controlled even if the system is suffering from a large delay or has variations in its delay, or if some other uncertain situations are present.
暂无评论