We propose a randomized divide-and-conquer technique that leads to improved randomized and deterministic algorithms for NP-hard PATH, MATCHING, and PACKING problems. For the parameterized max-path problem, our randomi...
详细信息
We propose a randomized divide-and-conquer technique that leads to improved randomized and deterministic algorithms for NP-hard PATH, MATCHING, and PACKING problems. For the parameterized max-path problem, our randomized algorithm runs in time O(4(k)k(2.7)m) and polynomial space (where m is the number of edges in the input graph), improving the previous best randomized algorithm for the problem that runs in time O(5.44(k)km) and exponential space. Our randomized algorithms for the parameterized MAX r-d MATCHING and MAX r-set PACKING problems run in time 4((r-1)k)n(O(1)) and polynomial space, improving the previous best algorithms for the problems that run in time 10.88(rk)n(O(1)) and exponential space. Moreover, our randomized algorithms can be derandomized to result in significantly improved deterministic algorithms for the problems, and they can be extended to solve other matching and packing problems.
The problem Local Search, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory, and many other areas in...
详细信息
The problem Local Search, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to combinatorial optimization, complexity theory, and many other areas in theoretical computer science. In this paper, we study the problem in both the randomized and the quantum query models and give new lower and upper bound techniques in both models. The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube {0, 1}(n) and the constant-dimensional grids [n](d), two particular product graphs that recently drew much attention, we get the following tight results: RLS({0, 1}(n)) = Theta(2(n)/(2)n(1/2)), QLS({0, 1}(n)) = Theta(2(n/3)n(1/6)), RLS([n](d)) = Theta(n(d/2)) for d >= 4, QLS([n](d)) = Theta(n(d/3)) for d >= 6. Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465-474], Ambainis (unpublished), and Santha and Szegedy [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 494-501]. Our new algorithms work well when the underlying graph expands slowly. As an application to [n](2), a new quantum algorithm using O(root n(log log n)(1.5)) queries is given. This improves the previously best known upper bound of O(n(2/3)) (see Aaronson [in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 465-474]), and implies that Local Search on grids exhibits different properties in low dimensions.
We present a simple, efficient, and stable method for computing-with any desired precision-the medial axis of simply connected planar domains. The domain boundaries are assumed to be given as polynomial spline curves....
详细信息
We present a simple, efficient, and stable method for computing-with any desired precision-the medial axis of simply connected planar domains. The domain boundaries are assumed to be given as polynomial spline curves. Our approach combines known results from the field of geometric approximation theory with a new algorithm from the field of computational geometry. Challenging steps are (1) the approximation of the boundary spline such that the medial axis is geometrically stable, and (2) the efficient decomposition of the domain into base cases where the medial axis can be computed directly and exactly. We solve these problems via spiral biarc approximation and a randomized divide & conquer algorithm. (C) 2008 Elsevier Ltd. All rights reserved.
In this paper, we study parameterized algorithms for the set splitting problem, for both weighted and unweighted versions. First, we develop a new and effective technique based on a probabilistic method that allows us...
详细信息
In this paper, we study parameterized algorithms for the set splitting problem, for both weighted and unweighted versions. First, we develop a new and effective technique based on a probabilistic method that allows us to develop a simpler and more efficient deterministic kernelization algorithm for the unweighted set splitting problem. We then propose a randomized algorithm for the weighted set splitting problem that is based on a new subset partition technique and has its running time bounded by O (*)(2 (k) ), which is significantly better than that of the previous best deterministic algorithm (which only works for the simpler unweighted set splitting problem) of running time O (*)(2.65 (k) ). We also show that our algorithm can be de-randomized, which leads to a deterministic parameterized algorithm of running time O (*)(4 (k) ) for the weighted set splitting problem and gives the first proof that the problem is fixed-parameter tractable.
Constrained least-squares regression problems, such as the Non-negative Least Squares (NNLS) problem, where the variables are restricted to take only nonnegative values, often arise in applications. Motivated by the r...
详细信息
Constrained least-squares regression problems, such as the Non-negative Least Squares (NNLS) problem, where the variables are restricted to take only nonnegative values, often arise in applications. Motivated by the recent development of the fast Johnson-Lindestrauss transform, we present a fast random projection type approximation algorithm for the NNLS problem. Our algorithm employs a randomized Hadamard transform to construct a much smaller NNLS problem and solves this smaller problem using a standard NNLS solver. We prove that our approach finds a nonnegative solution vector that, with high probability, is close to the optimum nonnegative solution in a relative error approximation sense. We experimentally evaluate our approach on a large collection of term-document data and verify that it does offer considerable speedups without a significant loss in accuracy. Our analysis is based on a novel random projection type result that might be of independent interest. In particular, given a tall and thin matrix Phi is an element of R-nxd (n >> d) and a vector y is an element of R-d, we prove that the Euclidean length of Phi y can be estimated very accurately by the Euclidean length of (Phi) over tildey, where (Phi) over tilde consists of a small subset of (appropriately rescaled) rows of Phi. (c) 2009 Elsevier Inc. All rights reserved.
This paper describes a novel algorithm for approximate nearest neighbor searching. For solving this problem especially in high dimensional spaces, one of the best-known algorithm is Locality-Sensitive Hashing (LSH). T...
详细信息
This paper describes a novel algorithm for approximate nearest neighbor searching. For solving this problem especially in high dimensional spaces, one of the best-known algorithm is Locality-Sensitive Hashing (LSH). This paper presents a variant of the LSH algorithm that outperforms previously proposed methods when the dataset consists of vectors normalized to unit length, which is often the case in pattern recognition. The LSH scheme is based on a family of hash functions that preserves the locality of points. This paper points out that for our special case problem we can design efficient hash functions that map a point on the hypersphere into the closest vertex of the randomly rotated regular polytope. The computational analysis confirmed that the proposed method could improve the exponent p, the main indicator of the performance of the LSH algorithm. The practical experiments also supported the efficiency of our algorithm both in time and in space.
The computational complexity of counting the number of matchings of size k in a given triple set has been open. It is conjectured that the problem is not fixed parameter tractable. In this paper, we present a fixed pa...
详细信息
The computational complexity of counting the number of matchings of size k in a given triple set has been open. It is conjectured that the problem is not fixed parameter tractable. In this paper, we present a fixed parameter tractable randomized approximation scheme (FPTRAS) for the problem. More precisely, we develop a randomized algorithm that, on given positive real numbers is an element of and delta, and a given set S of n triples and an integer k, produces a number h in time O(5.48(3k)n(2)ln(2/delta)/is an element of(2)) such that Prob[(1 - is an element of)h(0) <= h <= (1 + is an element of)h(0)] >= 1 - delta, where h(0) is the total number of matchings of size k in the triple set S. Our algorithm is based on the recent improved color-coding techniques and the Monte-Carlo self-adjusting coverage algorithm developed by Karp, Luby and Madras.
We study numerical integration of Lipschitz functionals on a Banach space by means of deterministic and randomized (Monte Carlo) algorithms. This quadrature problem is shown to be closely related to the problem of qua...
详细信息
We study numerical integration of Lipschitz functionals on a Banach space by means of deterministic and randomized (Monte Carlo) algorithms. This quadrature problem is shown to be closely related to the problem of quantization and to the average Kolmogorov widths of the underlying probability measure. In addition to the general setting, we analyze, in particular, integration with respect to Gaussian measures and distributions of diffusion processes. We derive lower bounds for the worst case error of every algorithm in terms of its cost, and we present matching upper bounds, up to logarithms, and corresponding almost optimal algorithms. As auxiliary results, we determine the asymptotic behavior of quantization numbers and Kolmogorov widths for diffusion processes.
Let f : 2(N) -> Z(+) be a polymatroid (an integer-valued non-decreasing submodular set function with f(empty set) = 0). We call S (subset of) under bar N a base if f (S) = f (N). We consider the problern of finding...
详细信息
Let f : 2(N) -> Z(+) be a polymatroid (an integer-valued non-decreasing submodular set function with f(empty set) = 0). We call S (subset of) under bar N a base if f (S) = f (N). We consider the problern of finding, a maximum number of disjoint bases;we denote by m* be this base packing number. A simple upper bound on m* is given by k* = max{k : Sigma(i is an element of N)f(A)(i) >= kfa(N), for all A (subset of) under bar N) where f(A)(S) = f (A boolean OR S) - f (A). This upper bound is a natural generalization of the bound for matroids where it is known that m* = k* For polymatroids, we prove that m* >= (1 - o(1))k*/In f (N) and give a randomized polynomial time algorithm to find (1 - o(1))k*/In f (N) disjoint bases, assuming an oracle for f. We also derandomize the algorithm using minwise independent permutations and give a deterministic algorithm that finds (1 - is an element of)k*/In f(N) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m* < (1 + o(1))k*/In f(N). Moreover it is known that unless NP <(subset of)under bar> DTIME(n(log log n)), for any is an element of > 0, there is no polynomial time algorithm to obtain a (1 + is an element of)/In f(N)-approximation to m*. Our result generalizes and unifies two results in the literature. (C) 2009 Wiley Periodicals, Inc. Random Struct. Alg., 35, 418-430, 2009
暂无评论