We study random number generators (RNGs), both in the fixed to variable-length (FVR) and the variable to fixed-length (VFR) regimes, in a universal setting in which the input is a finite memory source of arbitrary ord...
详细信息
We study random number generators (RNGs), both in the fixed to variable-length (FVR) and the variable to fixed-length (VFR) regimes, in a universal setting in which the input is a finite memory source of arbitrary order and unknown parameters, with arbitrary input and output (finite) alphabet sizes. Applying the method of types, we characterize essentially unique optimal universal RNGs that maximize the expected output (respectively, minimize the expected input) length in the FVR (respectively, VFR) case. For the FVR case, the RNG studied is a generalization of Elias's scheme, while in the VFR case the general scheme is new. We precisely characterize, up to an additive constant, the corresponding expected lengths, which include second-order terms similar to those encountered in universal data compression and universal simulation. Furthermore, in the FVR case, we consider also a twice-universal setting, in which the Markov order k of the input source is also unknown.
The method of fundamental solutions (MFS) is used to solve backward heat conduction problem, inverse heat source problem, inverse Cauchy problem and inverse Robin problem. In order to overcome the ill-posedness of res...
详细信息
The method of fundamental solutions (MFS) is used to solve backward heat conduction problem, inverse heat source problem, inverse Cauchy problem and inverse Robin problem. In order to overcome the ill-posedness of resulting linear equations, two optimal algorithms with optimal descent vectors that consist of m vectors in a Krylov subspace are developed, of which the m weighting parameters are determined by minimizing a properly defined merit function in terms of a quadratic quotient. The optimal algorithms OA1 and OA2 are convergent fast, accurate and robust against large noise, which are confirmed through numerical tests. (C) 2014 Elsevier Ltd. All rights reserved.
We consider a rho-weighted L-q approximation in the space of univariate functions f : R+ -> R with finite parallel to f((r)) psi parallel to L-p. Let alpha = r - 1/p + 1/q and omega = rho/psi. Assuming that psi and...
详细信息
We consider a rho-weighted L-q approximation in the space of univariate functions f : R+ -> R with finite parallel to f((r)) psi parallel to L-p. Let alpha = r - 1/p + 1/q and omega = rho/psi. Assuming that psi and omega are non-increasing and the quasi-norm parallel to omega parallel to L-1/alpha is finite, we construct algorithms using function/derivatives evaluations at n points with the worst case errors proportional to parallel to omega parallel to L-1/alpha n(-r+(1/p-1/q)+). In addition we show that this bound is sharp;in particular, if parallel to omega parallel to L-1/alpha = infinity then the rate n(-r+(1/p-1/q)+) cannot be achieved. Our results generalize known results for bounded domains such as [0, 1] and rho = psi equivalent to 1. We also provide a numerical illustration. (C) 2015 Elsevier Inc. All rights reserved.
Iterated (repeated, successive) integration is used for integrating functions satisfying the Lipschitz condition. To construct an optimal (minimax) algorithm, it is necessary to integrate optimally functions evaluated...
详细信息
Iterated (repeated, successive) integration is used for integrating functions satisfying the Lipschitz condition. To construct an optimal (minimax) algorithm, it is necessary to integrate optimally functions evaluated with indefinite errors. Such a problem is solved by generalization of an algorithm from Ref. 1 which is sequentially optimal for one-dimensional problems.
It is shown that the complete linkage clustering of n points in R-d, where d greater than or equal to 1 is a constant, can be computed in optimal O(nlogn) time and linear space, under the L-1 and L-infinity-metrics. F...
详细信息
It is shown that the complete linkage clustering of n points in R-d, where d greater than or equal to 1 is a constant, can be computed in optimal O(nlogn) time and linear space, under the L-1 and L-infinity-metrics. Furthermore, for every other fixed L-t-metric, it is shown that it can be approximated within an arbitrarily small constant factor in O(nlogn) time and linear space. (C) 2002 Elsevier Science B.V. All rights reserved.
In this paper, we study the problem of replica placement in tree networks subject to server capacity and distance constraints. The client requests are known beforehand, while the number and location of the servers are...
详细信息
ISBN:
(纸本)9780769546759
In this paper, we study the problem of replica placement in tree networks subject to server capacity and distance constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The Single policy enforces that all requests of a client are served by a single server in the tree, while in the Multiple policy, the requests of a given client can be processed by multiple servers, thus distributing the processing of requests over the platform. For the Single policy, we prove that all instances of the problem are NP-hard, and we propose approximation algorithms. The problem with the Multiple policy was known to be NP-hard with distance constraints, but we provide a polynomial time optimal algorithm to solve the problem in the particular case of binary trees when no request exceeds the server capacity.
Given a function F : N+ --> {X,Y} with the property that if F(n0) = Y then F(n) = Y for all n > n0, the unbounded search problem is to use tests of the form "is F(i) = X?" to determine the smallest n s...
详细信息
Given a function F : N+ --> {X,Y} with the property that if F(n0) = Y then F(n) = Y for all n > n0, the unbounded search problem is to use tests of the form "is F(i) = X?" to determine the smallest n such that F(n) = Y;the "cost" of a search algorithm is a function c(n), the number of such tests used when the location of the first Y is n. In Part I of this paper it is shown how to construct an infinite sequence of algorithms, each of which is much closer to optimality than its predecessor. Diagonalizing over this sequence yields a new algorithm that is far better than any of the algorithms in the sequence: this "omega-th" algorithm is within an additive factor of alpha-(n) + 2 of the corresponding lower bound, where alpha-(n) is a functional inverse of Ackermann's function-an extremely slowly growing function. In this paper the construction techiques are generalized to get dramatically better algorithms and lower bounds ad infinitum. Specifically, for each ordinal-iota less-than-or-equal-to epsilon-0, an algorithm is given that is dramatically closer to optimality than the algorithm corresponding to a smaller ordinal. All algorithms constructed for iota < epsilon-0 are proved to be optimal in a strong sense. Parallel results for the asymmetric case are also given.
In wireless sensor networks, rotating dominating set is an efficient method for balancing the energy consumption of nodes, and thereby extending the network operational time. This method can be abstracted as k-Lifetim...
详细信息
In wireless sensor networks, rotating dominating set is an efficient method for balancing the energy consumption of nodes, and thereby extending the network operational time. This method can be abstracted as k-Lifetime Dominating Set in bipartite graph, that partitions the set of graph vertices representing sensors into k disjoint dominating sets. However, the considered problem has been proven to be NP-hard, and there is no hope of solving it in polynomial time unless P = NP. Existing studies mainly focus on developing approximation or heuristic algorithms, which usually cannot guarantee a solution for a given problem yes instance. In this study, we first propose a randomized algorithm that can generate a solution with guaranteed probability 1-epsilon (0 < epsilon < 1). Using the color coding method, we show that the randomized algorithm can be improved to guarantee the generation of a solution for a given problem yes instance in exponential time. Based on the idea of randomized partition, we further present a more practical centralized greedy algorithm, and then a distributed implementation. Simulation results indicate that the centralized algorithm can efficiently generate optimal solutions for almost all the given problem instances if the partition redundancy is above a certain limit. Compared with existing algorithm, the centralized algorithm increases the number of dominating sets by factors between 0% and 21%.
Given a function F : N+ --> {X,Y} with the property that if F(n0) = Y then F(n) = Y for all n > n0, the unbounded search problem is to use tests of the form "is F(i) = X?" to determine the smallest n s...
详细信息
Given a function F : N+ --> {X,Y} with the property that if F(n0) = Y then F(n) = Y for all n > n0, the unbounded search problem is to use tests of the form "is F(i) = X?" to determine the smallest n such that F(n) = Y;the "cost" of a search algorithm is a function c(n), the number of such tests used when the location of the first Y is n. A solution to this search problem specifies a prefix-free, binary encoding of the positive integers in which the cost c(n) is the number of bits used to encode n. It is shown that the "ultimate algorithm," of Bentley and Yao [Inform. Process. Lett., 5 (1976), pp. 82-87], which is within an additive THETA-(lg* n) factor of a lower bound on the cost of this problem, is "far" from optimal in the sense that it is just the second in an infinite sequence of search algorithms, each of which is much closer to optimality than its predecessor. A corresponding sequence of lower bounds is also given, based on Kraft's inequality, each of which is much stronger than its predecessor. Diagonalizing over this sequence of search algorithms yields an algorithm, which is given explicitly in a Pascal-like notation, that is within an additive factor of alpha-(n) + 2 of the corresponding lower bound, where alpha-(n) is a functional inverse of Ackermann's function-an extremely slowly growing function. For each search algorithm, the corresponding prefix-free, binary encoding of the integers, is given, together with the decoding algorithm. Finally, algorithms/encodings are constructed that differ from the lower bounds by only negligible amounts even for the asymmetric case in which the cost of a Y answer and the cost of an X answer are not the same. In Part II it is shown how to continue the construction to get a transfinite sequence of dramatically better algorithms/encodings and lower bounds.
A selective introduction to the field of information-based complexity is presented in the context of the question raised in the title. After introducing some of the basic ideas of this relatively new area that interfa...
详细信息
A selective introduction to the field of information-based complexity is presented in the context of the question raised in the title. After introducing some of the basic ideas of this relatively new area that interfaces mathematics and theoretical computer science, the article surveys results on the existence of linear optimal algorithms for linear problems. Several illustrative examples are given along with an indication of the variety of disciplines in which techniques of information-based complexity are being applied.
暂无评论