We consider the problem of answering a series of on-line queries on a static data set. The conventional approach to such problems involves a preprocessing phase which constructs a data structure with good search behav...
详细信息
We consider the problem of answering a series of on-line queries on a static data set. The conventional approach to such problems involves a preprocessing phase which constructs a data structure with good search behavior. The data structure representing the data set then remains fixed throughout the processing of the queries. Our approach involves dynamic or query-driven structuring of the data set; our algorithm processes the data set only when doing so is required for answering a query. A data structure constructed progressively in this fashion is called a deferred data structure.
Given an undirected graph, a minimum cut cover is a collection of cuts covering the whole set of edges and having minimum cardinality. This paper is dedicated to the fractional version of this problem where a fraction...
详细信息
Given an undirected graph, a minimum cut cover is a collection of cuts covering the whole set of edges and having minimum cardinality. This paper is dedicated to the fractional version of this problem where a fractional weight is computed for each cut such that, for each edge, the sum of the weights of all cuts containing it is no less than 1, while the sum of all weights is minimized. The fractional cover is computed for different graph classes among which are the weakly bipartite graphs. Efficient algorithms are described to compute lower and upper bounds with worst-case performance guarantees. A general randomized approach is also presented giving new insights into Goemans and Williamson's algorithm for the maximum cut problem. Some numerical experiments are included to assess the quality of bounds. (C) 2019 Elsevier B.V. All rights reserved.
Adding Laplacian noise is a standard approach in differential privacy to sanitize numerical data before releasing it. In this paper, we propose an alternative noise adding mechanism: the staircase mechanism, which is ...
详细信息
Adding Laplacian noise is a standard approach in differential privacy to sanitize numerical data before releasing it. In this paper, we propose an alternative noise adding mechanism: the staircase mechanism, which is a geometric mixture of uniform random variables. The staircase mechanism can replace the Laplace mechanism in each instance in the literature and for the same level of differential privacy, the performance in each instance improves;the improvement is particularly stark in medium-low privacy regimes. We show that the staircase mechanism is the optimal noise adding mechanism in a universal context, subject to a conjectured technical lemma (which we also prove to be true for one and two dimensional data).
This paper introduces the interpolative butterfly factorization for nearly optimal implementation of several transforms in harmonic analysis, when their explicit formulas satisfy certain analytic properties and the ma...
详细信息
This paper introduces the interpolative butterfly factorization for nearly optimal implementation of several transforms in harmonic analysis, when their explicit formulas satisfy certain analytic properties and the matrix representations of these transforms satisfy a complementary low-rank property. A preliminary interpolative butterfly factorization is constructed based on interpolative low-rank approximations of the complementary low-rank matrix. A novel sweeping matrix compression technique further compresses the preliminary interpolative butterfly factorization via a sequence of structure-preserving low-rank approximations. The sweeping procedure propagates the low-rank property among neighboring matrix factors to compress dense submatrices in the preliminary butterfly factorization to obtain an optimal one in the butterfly scheme. For an N x N matrix, it takes O(N log N) operations and complexity to construct the factorization as a product of O(log N) sparse matrices, each with O(N) nonzero entries. Hence, it can be applied rapidly in O(N log N) operations. Numerical results are provided to demonstrate the effectiveness of this algorithm.
In the rendezvous problem, two computing entities (called agents) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous neighborhood rendezvous problem, w...
详细信息
In the rendezvous problem, two computing entities (called agents) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous neighborhood rendezvous problem, where the agents are initially located at two adjacent vertices. While this problem can be trivially solved in O(Delta) rounds (Delta is the maximum degree of the graph), it is highly challenging to reveal whether that problem can be solved in o(Delta) rounds, even assuming the rich computational capability of agents. The only known result is that the time complexity of O(root n) rounds is achievable if the graph is complete and agents are probabilistic, asymmetric, and can use whiteboards placed at vertices. Our main contribution is to clarify the situation (with respect to computational models and graph classes) admitting such a sublinear-time rendezvous algorithm. More precisely, we present two algorithms achieving fast rendezvous additionally assuming bounded minimum degree, unique vertex identifier, accessibility to neighborhood IDs, and randomization. The first algorithm runs within (O) over tilde( root n Delta/delta + n/delta) rounds for graphs of the minimum degree larger than root n, where n is the number of vertices in the graph, and delta is the minimum degree of the graph. The second algorithm assumes that the largest vertex ID is O(n), and achieves (O) over tilde (n/root delta)-round time complexity without using whiteboards. These algorithms attain o(Delta)-round complexity in the case of delta = omega(root n log n) and delta = omega(n(2/3) log(4/3) n) respectively. We also prove that four unconventional assumptions of our algorithm, bounded minimum degree, accessibility to neighborhood IDs, initial distance one, and randomization are all inherently necessary for attaining fast rendezvous. That is, one can obtain the Omega(n)-round lower bound if either one of them is removed.
In this paper, we introduce a new randomized, partition-based algorithm for the problem of computing the number of inversion pairs in an unsorted array of n numbers. The algorithm runs in expected time O(n . log n) an...
详细信息
In this paper, we introduce a new randomized, partition-based algorithm for the problem of computing the number of inversion pairs in an unsorted array of n numbers. The algorithm runs in expected time O(n . log n) and uses O(n) extra space. The expected time analysis of the new algorithm is different from the analyses existing in the literature, in that it explicitly uses inversion pairs. The problem of determining the inversion pair cardinality of an array finds applications in a number of design domains, including but not limited to real-time scheduling and operations research. At the heart of our algorithm is a new inversion pair conserving partition procedure that is different from existing partition procedures such as Hoare-partition and Lomuto-partition. Although the algorithm is not fully adaptive, we believe that it is the first step towards the design of an adaptive, partition-based sorting algorithm whose running time is proportional to the number of inversion pairs in the input.
The paper introduces the butterfly factorization as a data-sparse approximation for the matrices that satisfy a complementary low-rank property. The factorization can be constructed efficiently if either fast algorith...
详细信息
The paper introduces the butterfly factorization as a data-sparse approximation for the matrices that satisfy a complementary low-rank property. The factorization can be constructed efficiently if either fast algorithms for applying the matrix and its adjoint are available or the entries of the matrix can be sampled individually. For an N x N matrix, the resulting factorization is a product of O(log N) sparse matrices, each with O(N) nonzero entries. Hence, it can be applied rapidly in O(N log N) operations. Numerical results are provided to demonstrate the effectiveness of the butterfly factorization and its construction algorithms.
We prove that RANDOM EDGE, the simplex algorithm that always chooses a random improving edge to proceed on, can take a mildly exponential number of steps in the model of abstract objective functions (introduced by Wil...
详细信息
We prove that RANDOM EDGE, the simplex algorithm that always chooses a random improving edge to proceed on, can take a mildly exponential number of steps in the model of abstract objective functions (introduced by Williamson Hoke [Completely unimodal numberings of a simple polytope, Discrete Appl. Math. 20 (1988) 69-81.] and by Kalai [A simple way to tell a simple polytope from its graph, J. Combin. Theory Ser. A 49(2) (1988) 381-383.] under different names). We define an abstract objective function on the n-dimensional cube for which the algorithm, started at a random vertex, needs at least exp(const.n(1/3)) steps with high probability. The best previous lower bound was quadratic. So in order for RANDOM EDGE to succeed in polynomial time, geometry must help. (C) 2005 Elsevier Inc. All rights reserved.
In this paper, we survey online algorithms in computational geometry that have been designed for mobile robots for searching a target and for exploring a region in the plane. (C) 2010 Elsevier Inc. All rights reserved.
In this paper, we survey online algorithms in computational geometry that have been designed for mobile robots for searching a target and for exploring a region in the plane. (C) 2010 Elsevier Inc. All rights reserved.
A simple randomized algorithm for generating a uniformly distributed random permutation of size n is investigated. It works in time O(n/P + T-comm(n/P, P) + T-prefix (P)) on P processors with high probability, where T...
详细信息
A simple randomized algorithm for generating a uniformly distributed random permutation of size n is investigated. It works in time O(n/P + T-comm(n/P, P) + T-prefix (P)) on P processors with high probability, where T-comm(k, P) is the time for randomly sending or receiving k elements on each processor and T-prefix(P) is the time for computing a prefix sum. The algorithm can be directly translated into an optimal external memory algorithm if fast memory for root nB(1 + o(1)) + O(B) elements is available where B is the page size. Due to its simplicity, the same algorithm even outperforms the straightforward method on mainstream workstations if the cache is taken to be the fast memory and the main memory is treated like external memory. The algorithm is almost four times faster on a MIPS R10000 machine. (C) 1998 Elsevier Science B.V. All rights reserved.
暂无评论