In this paper we present a sublinear-time (1 + epsilon)-approximation randomized algorithm to estimate the weight of the minimum spanning tree of an n-point metric space. The running time of the algorithm is (O) over ...
详细信息
In this paper we present a sublinear-time (1 + epsilon)-approximation randomized algorithm to estimate the weight of the minimum spanning tree of an n-point metric space. The running time of the algorithm is (O) over tilde (n/epsilon(O(1))). Since the full description of an n-point metric space is of size Theta(n(2)), the complexity of our algorithm is sublinear with respect to the input size. Our algorithm is almost optimal as it is not possible to approximate in o(n) time the weight of the minimum spanning tree to within any factor. We also show that no deterministic algorithm can achieve a B-approximation in o(n(2)/B-3) time. Furthermore, it has been previously shown that no o(n(2)) algorithm exists that returns a spanning tree whose weight is within a constant times the optimum.
The bin packing problem is defined as follows: given a set of n items with sizes 0 0, we present an algorithm A, that has sampling access to the input instance and outputs a value k such that C-opt <= k <= (1 +...
详细信息
The bin packing problem is defined as follows: given a set of n items with sizes 0 < w(1), w(2), .... w(n) <= 1, find a packing of these items into a minimum number Of Unit-size bins possible. We present a sublinear-time asymptotic approximation scheme for the bin packing problem;that is, for any epsilon > 0, we present an algorithm A, that has sampling access to the input instance and outputs a value k such that C-opt <= k <= (1 + epsilon) . C-opt + 1, where C-opt is the cost of an optimal solution. It is clear that uniform sampling by itself will not allow a sublinear-time algorithm in this setting;a small number of items might constitute most of the total weight and uniform samples will not hit them. In this work we use weighted samples, where item i is sampled with probability proportional to its weight: that is, with probability w(i)/Sigma w(i). In the presence of weighted samples, the approximation algorithm runs in (O) over tilde root n . poly(1/epsilon)) +g(1/x) time, where g(x) is an exponential function of x. When both weighted sampling and uniform sampling are allowed, (O) over tilde (n(1/3).poly(1/epsilon)) + g(1/epsilon) time suffices. In addition to an approximate value to Copt, our algorithm can also output a constant-size "template" of a packing that can later be used to find a near-optimal packing in linear time. (C) 2009 Elsevier B.V. All rights reserved.
Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average dist...
详细信息
Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinearalgorithms, these algorithms access the input graph via queries to an adequate oracle. We consider two types of queries. The first type is standard neighborhood queries (i.e., what is the ith neighbor of vertex v?), whereas the second type are queries regarding the quantities that we need to find the average of (i.e., what is the degree of vertex v? and what is the distance between u and v?, respectively). Loosely speaking, our results indicate a difference between the two problems: For approximating the average degree, the standard neighbor queries suffice and in fact are preferable to degree queries. In contrast, for approximating average distances, the standard neighbor queries are of little help whereas distance queries are crucial. (c) 2008 Wiley Periodicals, Inc.
We consider approximate PCPs for multidimensional bin-packing problems. In particular, we show how a verifier can be quickly convinced that a set of multidimensional blocks can be packed into a small number of bins. T...
详细信息
We consider approximate PCPs for multidimensional bin-packing problems. In particular, we show how a verifier can be quickly convinced that a set of multidimensional blocks can be packed into a small number of bins. The running time of the verifier is bounded by O(log(d) n) where n is the number of blocks and d is the dimension. (C) 2004 Elsevier Inc. All rights reserved.
暂无评论