Consider the problem of locating servers in a network for the purpose of storing data, performing an application, etc., so that at least one server will be available to clients even if up to k component failures occur...
详细信息
Consider the problem of locating servers in a network for the purpose of storing data, performing an application, etc., so that at least one server will be available to clients even if up to k component failures occur throughout the network. Letting G = (V, E) be the graph with vertex set V and edge set E representing the topology of the network, and letting L subset of V be a set of potential locations for the servers, a fundamental problem is to determine a minimum-size set S subset of L such that the network remains connected to S even if up to k component failures occur throughout the network. We say that such a set S is k-fault-tolerant. In this paper we present an algebraic characterization of k-fault-tolerant sets in terms of a. ne embeddings of G in k-dimensional Euclidean space. Employing this characterization, we present a polynomial-time Monte Carlo algorithm for computing a minimum-size k-fault-tolerant subset S of L. In fact, we solve the following more general problem for directed networks: given a digraph G = (V, E) (an undirected graph is equivalent to a symmetric digraph) and a subset L subset of V, we find a k-fault-tolerant subset S of L having minimum cost, where a unary integer cost c(v) is associated with locating a server at vertex v epsilon V.
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of object...
详细信息
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of objects with minimum total cost. randomized parallel algorithms are proposed to solve MAPs appearing in multi-sensor multi-target applications. A parallel construction heuristic is described, together with some variations, as well as a parallel local search heuristic. Experimental results using the proposed algorithms are discussed. (C) 2003 IMACS. Published by Elsevier B.V. All rights reserved.
Given a planar polygonal subdivision S, point location involves preprocessing this subdivision into a data structure so that given any query point q, the cell of the subdivision containing q can be determined efficien...
详细信息
Given a planar polygonal subdivision S, point location involves preprocessing this subdivision into a data structure so that given any query point q, the cell of the subdivision containing q can be determined efficiently. Suppose that for each cell z in the subdivision, the probability p, that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. This problem has been considered before, but existing data structures are all quite complicated. It has long been known that the entropy H of the probability distribution is the dominant term in the lower bound on the average-case search time. In this article, we show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point-location queries in O(H) average time. We also present empirical evidence for the practical efficiency of this approach.
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of object...
详细信息
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of objects with minimum total cost. randomized parallel algorithms are proposed to solve MAPs appearing in multi-sensor multi-target applications. A parallel construction heuristic is described, together with some variations, as well as a parallel local search heuristic. Experimental results using the proposed algorithms are discussed. (C) 2003 IMACS. Published by Elsevier B.V. All rights reserved.
This paper deals with probabilistic methods and randomized algorithms for robust control design. The main contribution is to introduce a new technique, denoted as "pack-based strategy". When combined with re...
详细信息
ISBN:
(纸本)9781424414970;1424414970
This paper deals with probabilistic methods and randomized algorithms for robust control design. The main contribution is to introduce a new technique, denoted as "pack-based strategy". When combined with recent results available in the literature, this technique leads to significant improvements in terms of sample size reduction. One of the main results is to show that for fixed confidence delta, the required sample size increases as 1/E, where E denotes the guaranteed accuracy. Using this technique for non-convex optimization problems involving Boolean expressions consisting of polynomials, we prove that the number of required samples grows with the accuracy parameter E as 1/E ln 1/E.
In this paper, we study two general semi-infinite programming problems by means of statistical learning theory. The sample size results obtained with this approach are generally considered to be very conservative by t...
详细信息
ISBN:
(纸本)9781424414970;1424414970
In this paper, we study two general semi-infinite programming problems by means of statistical learning theory. The sample size results obtained with this approach are generally considered to be very conservative by the control community. The main contribution of this paper is to demonstrate that this is not necessarily the case. Using as a starting point one-side results from statistical learning theory, we obtain bounds on the number of required samples that are manageable for "reasonable" values of confidence delta and accuracy E. In particular, we provide sample size bounds growing with 1/E ln 1/E instead of the usual 1/E~(2) ln 1/E~(2) dependence.
We introduce a new methodology for the design of cautious adaptive controllers based on the following two-step procedure: (i) a probability measure describing the likelihood of different models is updated on-line base...
详细信息
We introduce a new methodology for the design of cautious adaptive controllers based on the following two-step procedure: (i) a probability measure describing the likelihood of different models is updated on-line based on observations, and (ii) a controller with certain robust control specifications is tuned to the updated probability by means of randomized algorithms. The robust control specifications are assigned as average specifications with respect to the estimated probability measure, and randomized algorithms are used to make the controller tuning computationally tractable. This paper provides a general overview of the proposed new methodology. Still, many issues remain open and represent interesting topics for future research. (C) 2003 Elsevier Science B.V. All rights reserved.
We establish the first polynomial-strength time-space lower bounds for problems in the linear-time hierarchy on randomized machines with two-sided error. We show that for any integer l > 1 and constant c = 3. In fa...
详细信息
We establish the first polynomial-strength time-space lower bounds for problems in the linear-time hierarchy on randomized machines with two-sided error. We show that for any integer l > 1 and constant c < l, there exists a positive constant d such that QSAT(l) cannot be computed by such machines in time n(c) and space n(d), where QSAT(l) denotes the problem of deciding the validity of a quantified Boolean formula with at most l-1 quantifier alternations. Moreover, d approaches 1/2 from below as c approaches 1 from above for l = 2, and d approaches 1 from below as c approaches 1 from above for l >= 3. In fact, we establish the stronger result that for any constants a <= 1 and c < 1 + (l - 1) a, there exists a positive constant d such that linear-time alternating machines using space n(a) and l - 1 alternations cannot be simulated by randomized machines with two-sided error running in time n(c) and space n(d), where d approaches a/2 from below as c approaches 1 from above for l = 2, and d approaches a from below as c approaches 1 from above for l >= 3. Corresponding to l = 1, we prove that there exists a positive constant d such that the set of Boolean tautologies cannot be decided by a randomized machine with one-sided error in time n(1.759) and space n(d). As a corollary, this gives the same lower bound for satisfiability on deterministic machines, improving on the previously best known such result.
We propose an advanced randomized coloring algorithm for the problem of balanced colorings of hypergraphs (discrepancy problem). Instead of independently coloring the vertices with a random color, we try to use struct...
详细信息
We propose an advanced randomized coloring algorithm for the problem of balanced colorings of hypergraphs (discrepancy problem). Instead of independently coloring the vertices with a random color, we try to use structural information about the hypergraph in the design of the random experiment by imposing suitable dependencies. This yields colorings having smaller discrepancy. We also obtain more information about the coloring, or, conversely, we may enforce the random coloring to have special properties. There are some algorithmic advantages as well. We apply our approach to hypergraphs of d-dimensional boxes and to finite geometries. Among others results, we gain a factor 2(d/2) decrease in the discrepancy of the boxes, and reduce the number of random bits needed to generate good colorings for the geometries down to O(root n) (from n). The latter also speeds up the corresponding derandomization by a factor of root n. (c) 2005 Elsevier B.V. All rights reserved.
作者：
Oishi, YKimura, HUniv Tokyo
Grad Sch Informat Sci & Technol Dept Math Informat Bunkyo Ku Tokyo 1138656 Japan Univ Tokyo
Grad Sch Frontier Sci Dept Complex Sci & Engn Bunkyo Ku Tokyo 1130033 Japan
randomized algorithms are proposed for solving parameter-dependent linear matrix inequalities and their computational complexity is analyzed. The first proposed algorithm is an adaptation of the algorithms of Polyak a...
详细信息
randomized algorithms are proposed for solving parameter-dependent linear matrix inequalities and their computational complexity is analyzed. The first proposed algorithm is an adaptation of the algorithms of Polyak and Tempo [(Syst. Control Lett. 43(5) (2001) 343)] and Calafiore and Polyak [(IEEE Trans. Autom. Control 46 (11) (2001) 1755)] for the present problem. It is possible however to show that the expected number of iterations necessary to have a deterministic solution is infinite. In order to make this number finite, the improved algorithm is proposed. The number of iterations necessary to have a probabilistic solution is also considered and is shown to be independent of the parameter dimension. A numerical example is provided. (C) 2003 Elsevier Ltd. All rights reserved.
暂无评论