Paper by Erik D. Demaine
- Reference:
- Stelian Ciurea, Erik D. Demaine, Corina E. Pǎtraşcu, and Mihai Pǎtraşcu, “Finding a Divisible Pair”, ACM SIGSAM Bulletin, volume 38, number 3, September 2004, pages 98–100.
- Abstract:
-
Our problem is the natural algorithmic version of a classic
mathematical result: any
(n + 1)-subset of {1, …, 2n}
contains a pair of divisible numbers. How do we actually find such a
pair? If the subset is accessible only through a membership oracle, we
show a lower bound of (4/3) n − O(1)
and an almost matching upper bound of
(4/3 + 1/24) n + O(1)
on the number of queries necessary in the worst case.
- Length:
- The paper is 2 pages.
- Availability:
- The paper is available in PostScript (105k), gzipped PostScript (43k), and PDF (60k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Yogi_FUN2004 (Finding a Divisible Pair and a Good Wooden Fence)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated November 27, 2024 by
Erik Demaine.