Parallel searching of multidimensional cubes

DOI10.1016/0012-365X(93)90381-3MaRDI QIDQ685702zbMATH OpenOpenAlexFDO

Authors Miklos Santha, Umesh V. Vazirani

Publication date 24 October 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(93)90381-3

zbMATH Keywords

lower bounds multidimensional cube searching

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Review text

Let \((P,\leq)\) be a finite partially ordered set and let \(f:P \to R\) be an order-preserving, injective, real-valued function. The search problem associated with \(P\) is: Given a real number \(x\), determine if there exists \(p \in P\) such that \(f(p) = x\), and find such a \(p\) if it exists. An elementary step is the evaluation of \(f\) at some \(p \in P\). The complexity \(c(P)\) of the search problem is the minimum, over all algorithms for the problem, of the maximum number of steps taken by the algorithm. When \(k\) processors are used, the complexity is denoted by \(c_ k (P)\). In this paper the authors consider the search problem when \(P\) is a product of several chains of the same length. \(Q_{nd}\) denotes the \(d\)- dimensional cube of side length \(n\), and we write \(W(n,d,k)\) for \(c_ k (Q_{nd})\). The authors prove that \(W(n,d,n^{d-1}) = \Theta (\log \log n)\) and that, moreover, any randomized algorithm using \(n^{d-1}\) processors for searching \(Q_{nd}\) takes time \(\Omega (\log \log n)\).

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Parallel searching of multidimensional cubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685702)