We give a (Las Vegas) randomized algorithm for linear programming in a fixed dimensiond for which the expected computation time is \(O(d^{(3 + \varepsilon _d )d} n)\) , where lim d→∞ ε d = 0. This improves the ...
详细信息
We give a (Las Vegas) randomized algorithm for linear programming in a fixed dimensiond for which the expected computation time is \(O(d^{(3 + \varepsilon _d )d} n)\) , where lim d→∞ ε d = 0. This improves the corresponding worst-case complexity, \(O(3^{d^2 } n)\) . The method is based on a recent idea of Clarkson. Two variations on the algorithm are examined briefly.
In this work we propose and analyze a simple randomized algorithm for 3-SAT (i.e. an algorithm to find a satisfiable assignment for a Boolean formula in conjunctive normal form (CNF) having at most 3 literals in every...
详细信息
In this work we propose and analyze a simple randomized algorithm for 3-SAT (i.e. an algorithm to find a satisfiable assignment for a Boolean formula in conjunctive normal form (CNF) having at most 3 literals in every clause). Given a k-CNF formula phi on n variables, and alpha is an element of {0, 1}(n) that satisfies phi, a clause of phi is critical if exactly one literal of that clause is satisfied under assignment alpha. Paturi et al. (Chicago J. Theor. Comput. Sci. 115, 1999) proposed a simple randomized algorithm (PPZ) for k-SAT for which success probability increases with the number of critical clauses (with respect to a fixed satisfiable solution of the input formula). Here, we first describe another simple randomized algorithm DEL which performs better if the number of critical clauses in input formula are less (with respect to a fixed satisfiable solution of the input formula). Subsequently, we combine these two simple algorithms such that the success probability of the combined algorithm is maximum of the success probabilities of PPZ and DEL on every input instance. We show that when the average number of clauses for a variable that appear as unique true literals in one or more critical clauses in phi is between 1 and 2/(3 center dot log (3/2)), combined algorithm performs better than the PPZ algorithm.
The problem considered in this paper is: given an integer k > 0 and a set P of n points in the plane each with a corresponding non-negative weight, find a step function f with k steps that minimize the maximum weig...
详细信息
ISBN:
(纸本)9783642174575
The problem considered in this paper is: given an integer k > 0 and a set P of n points in the plane each with a corresponding non-negative weight, find a step function f with k steps that minimize the maximum weighted vertical distance between f and all the points in P. We present a randomized algorithm to solve the problem in O(n log n) expected running time. The bound is obviously optimal for the unsorted input. The previously best known algorithm runs in O(n log(2) n) worst-case time. Another merit of the algorithm is its simplicity. The algorithm is just a randomized implementation of Frederickson and Johnson's matrix searching technique, and it only exploits a simple data structure.
It is the first time that bounded degree graph is proven to be computed for a big class of TSP in polynomial time based on frequency quadrilaterals. As TSP conforms to the properties of frequency quadrilaterals, a pol...
详细信息
ISBN:
(纸本)9789811981517;9789811981524
It is the first time that bounded degree graph is proven to be computed for a big class of TSP in polynomial time based on frequency quadrilaterals. As TSP conforms to the properties of frequency quadrilaterals, a polynomial algorithm is given to reduce complete graph of TSP to bounded degree graph in which the optimal Hamiltonian cycle is preserved with a probability above 0.5. For TSP on such bounded degree graphs, there are more competitive exact and approximation algorithms.
A set of n distinct points in the plane defines ((n)(2)) lines by joining each pair of distinct points. The median slope of these O(n(2)) lines was proposed by Theil as a robust estimator for the slope of the line of ...
详细信息
A set of n distinct points in the plane defines ((n)(2)) lines by joining each pair of distinct points. The median slope of these O(n(2)) lines was proposed by Theil as a robust estimator for the slope of the line of best fit for the points. We present a randomized algorithm for selecting the k-th smallest slope of such a set of lines which runs in expected O(n log n) time. An efficient implementation of the algorithm and practical experience with the algorithm are discussed.
This paper proposes a method for solving the monostatic radar cross section of the target with the iterative solution of the method of moments. In this method, the randomized algorithm is adapted to enhance the comput...
详细信息
ISBN:
(纸本)9780996007894
This paper proposes a method for solving the monostatic radar cross section of the target with the iterative solution of the method of moments. In this method, the randomized algorithm is adapted to enhance the computational efficiency of the matrix solution step by compressing the impedance matrix and the excitation matrix. The results of calculation examples show that the method is efficient and reliable.
Cloud computing is one of the highly discussed topics in the field of Internet and communication technology. It is responsible for the on-demand provision of computing resources, mainly data and computing power to the...
详细信息
ISBN:
(纸本)9781728127910
Cloud computing is one of the highly discussed topics in the field of Internet and communication technology. It is responsible for the on-demand provision of computing resources, mainly data and computing power to the end-users. More than one server works together in a cloud network. So, the incoming request for resources must be distributed among all servers in the network for better performance. The process of efficiently distributing incoming tasks and sharing the workload among a group of servers is called load balancing. In this paper, we propose a randomized algorithm for load balancing in a containerized cloud. The approach we have used is called Balls into Bins via Local Search. In our algorithm, we have considered tasks as balls and servers as bins. First, we construct a fully connected undirected graph of nodes(server) and then convert it to a minimum edge weight graph to reduce the network cost. Our experimental result shows that the load is distributed among all servers almost equally. The difference between the highest and lowest workload in the network is minimized
Effective testing is essential for assuring software quality. While regression testing is time-consuming, the fault detection capability may be compromised if some test cases are discarded. Test case prioritization is...
详细信息
ISBN:
(纸本)9781467379892
Effective testing is essential for assuring software quality. While regression testing is time-consuming, the fault detection capability may be compromised if some test cases are discarded. Test case prioritization is a viable solution. To the best of our knowledge, the most effective test case prioritization approach is still the additional greedy algorithm, and existing search-based algorithms have been shown to be visually less effective than the former algorithms in previous empirical studies. This paper proposes a novel Proportion-Oriented randomized algorithm (PORA) for test case prioritization. PORA guides test case prioritization by optimizing the distance between the prioritized test suite and a hierarchy of distributions of test input data. Our experiment shows that PORA test case prioritization techniques are as effective as, if not more effective than, the total greedy, additional greedy, and ART techniques, which use code coverage information. Moreover, the experiment shows that PORA techniques are more stable in effectiveness than the others.
The problem considered in this paper is: Given an integer k > 0 and a set P of n points in the plane each with a corresponding nonnegative weight, find a step function f with k steps that minimize the maximum weigh...
详细信息
The problem considered in this paper is: Given an integer k > 0 and a set P of n points in the plane each with a corresponding nonnegative weight, find a step function f with k steps that minimize the maximum weighted vertical distance between f and all the points in P. We present a randomized algorithm to solve the problem in O(n log n) expected running time. The bound is obviously optimal for the unsorted input. The previously best known algorithm runs in O(n log(2) n) worst-case time. Another merit of the algorithm is its simplicity. The algorithm is just a randomized implementation of Frederickson and Johnson's matrix searching technique, and it only exploits a simple data structure.
Both H-infinity optimization techniques and eigenstructure assignment have their unique significances in control engineering. The first one is an effective method to ensure the robust stability of the closed loop syst...
详细信息
ISBN:
(纸本)9781509026388
Both H-infinity optimization techniques and eigenstructure assignment have their unique significances in control engineering. The first one is an effective method to ensure the robust stability of the closed loop system whereas the second one is very useful in shaping the transient response of the closed loop system by placing the eigenvalues and eigenvectors in the desired locations. Hence, to design a controller which not only ensures the robust stability of the closed loop system but also shapes the closed loop transient response very well, these two methods are combined by minimizing a mixed time and frequency domain performance index. A directed search based method already exists in the literature to solve such an optimization problem. But such a directed search based method is computationally tedious as it requires gradient calculation of the objective function and does not guarantee to yield the global minimum of the objective function. The present work proposes a randomized algorithm based solution to the aforementioned optimization problem. This randomized algorithm based method is computationally easier than the directed search based method and gives improved results due to the increased chance of reaching the global minimum of the objective function.
暂无评论