An official website of the United States government
We study search trees with 2-way comparisons (2WCST’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3WCST’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum-cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ− is the largest ratio that forces the less-than test, and λ+ is the smallest ratio that forces the equal-to test. They determined that λ− = 41 , but for the higher threshold they only showed that λ+ ∈ [ 3/7 , 4/9 ]. We give the tight bound for the higher threshold, by proving that in fact λ+ = 3/7 .
more »
« less
This content will become publicly available on December 1, 2026
A tight threshold bound for search trees with 2-way comparisons
We study search trees with 2-way comparisons (2WCST’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3WCST’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum- cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. In 2002, Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ− is the largest ratio that forces the less-than test, and λ+ is the smallest −1 ratio that admits the equal-to test. They determined that λ = 4 , but for the higher threshold they only showed that λ+ ∈ [ 37 , 49 ]. We give the tight bound for the higher threshold, by proving that in fact +3 λ=7.
more »
« less
- Award ID(s):
- 2153723
- PAR ID:
- 10694082
- Publisher / Repository:
- Elsevier
- Date Published:
- Journal Name:
- Theoretical Computer Science
- Volume:
- 1058
- Issue:
- C
- ISSN:
- 0304-3975
- Page Range / eLocation ID:
- 115589
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Chen, Xujin; Li, Bo (Ed.)We study search trees with 2-way comparisons (2WCST’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3WCST’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum-cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ− is the largest ratio that forces the less-than test, and λ+ −1 is the smallest ratio that forces the equal-to test. They determined that λ = 4 , but for the higher threshold they only showed that λ+ ∈ [ 37 , 49 ]. We give the tight +3 bound for the higher threshold, by proving that in fact λ = 7 .more » « less
-
We study search trees with 2-way comparisons (2WCST’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3WCST’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum- cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ− is the largest ratio that forces the less-than test, and λ+ is the smallest ratio that −1 forces the equal-to test. They determined that λ = 4 , but for the higher threshold they only showed that +34 +3 λ ∈ [7, 9]. We give the tight bound for the higher threshold, by proving that in fact λ = 7.more » « less
-
Abstract Huang and Wong (Acta Inform 21(1):113–123, 1984) proposed a polynomial-time dynamic-programming algorithm for computing optimal generalized binary split trees. We show that their algorithm is incorrect. Thus, it remains open whether such trees can be computed in polynomial time. Spuler (Optimal search trees using two-way key comparisons, PhD thesis, 1994) proposed modifying Huang and Wong’s algorithm to obtain an algorithm for a different problem: computing optimal two-way comparison search trees. We show that the dynamic program underlying Spuler’s algorithm is not valid, in that it does not satisfy the necessary optimal-substructure property and its proposed recurrence relation is incorrect. It remains unknown whether the algorithm is guaranteed to compute a correct overall solution.more » « less
-
null (Ed.)A bstract A search for nonresonant production of Higgs boson pairs via gluon-gluon and vector boson fusion processes in final states with two bottom quarks and two photons is presented. The search uses data from proton-proton collisions at a center-of-mass energy of $$ \sqrt{s} $$ s = 13 TeV recorded with the CMS detector at the LHC, corresponding to an integrated luminosity of 137 fb − 1 . No significant deviation from the background-only hypothesis is observed. An upper limit at 95% confidence level is set on the product of the Higgs boson pair production cross section and branching fraction into $$ \gamma \gamma \mathrm{b}\overline{\mathrm{b}} $$ γγ b b ¯ . The observed (expected) upper limit is determined to be 0.67 (0 . 45) fb, which corresponds to 7.7 (5.2) times the standard model prediction. This search has the highest sensitivity to Higgs boson pair production to date. Assuming all other Higgs boson couplings are equal to their values in the standard model, the observed coupling modifiers of the trilinear Higgs boson self-coupling κ λ and the coupling between a pair of Higgs bosons and a pair of vector bosons c 2V are constrained within the ranges − 3 . 3 < κ λ < 8 . 5 and − 1 . 3 < c 2V < 3 . 5 at 95% confidence level. Constraints on κ λ are also set by combining this analysis with a search for single Higgs bosons decaying to two photons, produced in association with top quark-antiquark pairs, and by performing a simultaneous fit of κ λ and the top quark Yukawa coupling modifier κ t .more » « less
