The two-point based sampling technique was introduced by Chor and Goldreich with the purpose of reducing the amount of randomness needed in randomized algorithms. It has since found numerous applications in theoretica...
详细信息
The two-point based sampling technique was introduced by Chor and Goldreich with the purpose of reducing the amount of randomness needed in randomized algorithms. It has since found numerous applications in theoretical computer science. In this note, we point out a connection between two-point based sampling and the combinatorial structures known as orthogonal arrays. We also present an elementary combinatorial analysis of two-point based sampling, which leads to an improved bound on the error probability.
We consider the problem MAX CSP over multi-valued domains with variables ranging over sets of size s(i) less than or equal to s and constraints involving k(j) less than or equal to k variables. We study two algorithms...
详细信息
We consider the problem MAX CSP over multi-valued domains with variables ranging over sets of size s(i) less than or equal to s and constraints involving k(j) less than or equal to k variables. We study two algorithms with approximation ratios A and B, respectively, so we obtain a solution with approximation ratio max(A, B). The first algorithm is based on the linear programming algorithm of Serna, Trevisan, and Xhafa [Proc. 15th Annual Symp. on Theoret. Aspects of Comput. Sci., 1998, pp. 488-498] and gives ratio A which is bounded below by s(1-k). For k = 2, our bound in terms of the individual set sizes is the minimum over all constraints involving two variables of (1/2roots(1) + 1/2roots(2))(2), where s(1) and s(2) are the set sizes for the two variables. We then give a simple combinatorial algorithm which has approximation ratio B, with B > A/e. The bound is greater than s(1-k)/e in general, and greater than s(1-k)(1-(s-1)/2(k- 1)) for s < k-1, thus close to the s(1-k) linear programming bound for large k. For k = 2, the bound is 4/9 if s = 2, 1/2(s-1) if s greater than or equal to 3, and in general greater than the minimum of 1/4s(1) + 1/4s(2) over constraints with set sizes s(1) and s(2), thus within a factor of two of the linear programming bound. For the case of k = 2 and s = 2 we prove an integrality gap of 4/9(1 + O(n(-1/2))). This shows that our analysis is tight for any method that uses the linear programming upper bound. (C) 2002 Elsevier Science B.V. All rights reserved.
We prove that quantum computing is polynomially equivalent to classical probabilistic computing with an oracle for estimating the value of simple sums, quadratically signed weight enumerators (QWGTs). The problem of e...
详细信息
We prove that quantum computing is polynomially equivalent to classical probabilistic computing with an oracle for estimating the value of simple sums, quadratically signed weight enumerators (QWGTs). The problem of estimating these sums is cast in terms of promise problems and has two interesting variants. An oracle for the unconstrained variant may be more powerful than quantum computing, while an oracle for a more constrained variant is efficiently solvable in the one-bit model of quantum computing. Thus, problems involving QWGTs yield new problems in BQPP (BQP promise problems) and a natural BQPP complete problem. They can be used to define and study complexity classes and their relationships to quantum computing. (C) 2001 Elsevier Science B.V. All rights reserved.
We introduce the notion of k-violation linear programming. Given a set of n halplanes, we want to compute an optimal solution with respect to a given linear functional. However, in opposite to classical linear program...
详细信息
We introduce the notion of k-violation linear programming. Given a set of n halplanes, we want to compute an optimal solution with respect to a given linear functional. However, in opposite to classical linear programming [16], we allow to violate at most k of the n constraints, for some fixed k is an element of {0,...,n-1}. We solve this problem in O(beta(k)(n) time and O(n) space, where beta(k)(n) := n log + k log(2) k. This is optimal if k is an element of O(n(alpha)) for any fixed positive alpha < 1. The general idea behind our approach is a new approach is a new technique for computing a minimum of the k-level of an arrangement. Based on recent slope selecting techniques by Cole et al. [4] and Matousek [15], we develop an algorithm for computing a minimum k-level point in O(beta(k)(n)) time and linear space. Our result improves all existing approaches that explicitly compute the entire k-level [3,9,11]. The presented technique is of independent interest and can be applied to several other problems, as well.
We consider the problem of assigning a set of jobs to a system of m identical processors in order to maximize the earliest processor completion time. It was known that the LPT-heuristic gives an approximation of worst...
详细信息
We consider the problem of assigning a set of jobs to a system of m identical processors in order to maximize the earliest processor completion time. It was known that the LPT-heuristic gives an approximation of worst case ratio at most 3/4. In this note we show that the exact worst case ratio of LPT is (3m - 1)/(4m - 2).
We present a cooperative game theory problem encountered while working on broadcast algorithms for local area computer networks. The problem arises when one computer broadcasts or multicasts a message to a set of reci...
详细信息
We present a cooperative game theory problem encountered while working on broadcast algorithms for local area computer networks. The problem arises when one computer broadcasts or multicasts a message to a set of recipients and each recipient replies directly to the broadcast's originator. We study a distributed approach where each recipient waits a random time before responding, drawn from a distribution H(y) defined on y epsilon 0, tau .
The Maximum Agreement Subtree Problem was posed by Finden and Gordon in 1985, and is as follows: given a set S = {s1, S2,.... s(n)) and two trees P and Q leaf-labelled by the elements of S, find a maximum cardinality ...
详细信息
The Maximum Agreement Subtree Problem was posed by Finden and Gordon in 1985, and is as follows: given a set S = {s1, S2,.... s(n)) and two trees P and Q leaf-labelled by the elements of S, find a maximum cardinality subset S0 of S such that P\S0 = Q\S0. This problem arises in evolutionary tree construction, where different methods or data yield (possibly) different trees for the same species on which the trees agree. A superpolynomial time algorithm for finding a maximum agreement subtree of two binary trees was found by Kubicka et al. In this paper, we will present an O(n4,5 log n + V) algorithm to determine the largest agreement subtree of two trees on n leaves, where V is the maximum number of nodes in the trees. For the case of trees of maximum degree k, there are two algorithms presented: one has running time O(k!n2 + V) While the other has running time O(k2.5n2 log n + V). These algorithms also apply when the trees are constrained to be rooted;in this case a maximum agreement subtree is also constrained to be rooted. Each of the algorithms we present can be modified to produce a maximum agreement subtree, rather than computing only the size. Thus, we can solve the search problem in the same running time as above.
The Quadratic Assignment Problem (QAP) is a combinatorial NP-hard optimization problem that is not solvable in a polynomial time. It has a large number of real-world applications in diverse fields (e.g. facility arran...
详细信息
The Quadratic Assignment Problem (QAP) is a combinatorial NP-hard optimization problem that is not solvable in a polynomial time. It has a large number of real-world applications in diverse fields (e.g. facility arrangement in a hospital). The Whale Optimization Algorithm is a new meta-heuristic that achieves a great success in solving the continuous problems. In this paper, we propose a memetic algorithm using the Whale optimization Algorithm (WA) Integrated with a Tabu Search (WAITS) for solving QAP. In fact, this work employs Tabu Search to improve the quality of solution obtained by WA for QAP problem as a local search algorithm. This is an attempt to improve the convergence speed and local search of WA as its main drawbacks. Due to the combinatorial nature of QAP, the continuous values generated from the standard WA were converted to discrete values by the largest real value mapping. The WAITS algorithm is enhanced by a local search that defines a set of neighborhood solutions to improve the accuracy of the obtained solutions. Fourteen different case studies including 122 test problems are employed for analyzing the performance of the proposed WAITS. The results show that the proposed memetic algorithm finds near-optimal solutions with an acceptable computational time. WAITS is compared to several algorithms in the literature. The results show that the proposed algorithm outperforms similar algorithms in the literature. (C) 2018 Elsevier B.V. All rights reserved.
Let G = (V, E) be a graph together with two distinguished nodes s and t, and suppose that to every node v-epsilon-V, a nonnegative integer f(v) less-than-or-equal-to degree(v) is assigned. Suppose, moreover, that each...
详细信息
Let G = (V, E) be a graph together with two distinguished nodes s and t, and suppose that to every node v-epsilon-V, a nonnegative integer f(v) less-than-or-equal-to degree(v) is assigned. Suppose, moreover, that each node can cause at most f(v) of its incident edges to "fail" (these f(v) edges can be arbitrarily chosen). The Reliable Connectivity Problem is to test whether node s remains connected to t by a path of non-failed edges for all possible choices of the failed edges. Although, as expected, the general Reliable Connectivity Problem is co-NP-complete and this remains true even if G is restricted to the class of directed, acyclic graphs, we show that the problem is in P for directed, acyclic graphs if the edges caused to fail by each node v are chosen only from the edges incoming to v. Concerning the parallel complexity of the latter version of the problem, it turns out that it is P-complete. Moreover. approximating the maximum d such that for any choice of failed edges there is a directed path of non-failed edges that starts from s and has length d turns out to be P-complete as well, for any given degree of relative accuracy of the approximation. Furthermore, given that every node v will cause at least f(v) incoming edges to fail, the question whether there is a choice of failed edges such that s remains connected to t via non-failed edges turns out to be in NC, even for general graphs.
We shall establish a systematic one-to-one correspondence between extended binary trees with m leaves and leftist 2,3-trees with m leaves. (C) 1999 Elsevier Science B.V. All rights reserved.
We shall establish a systematic one-to-one correspondence between extended binary trees with m leaves and leftist 2,3-trees with m leaves. (C) 1999 Elsevier Science B.V. All rights reserved.
暂无评论