Optimal search for rationals

DOI10.1016/S0020-0190(02)00455-6zbMath1173.68826MaRDI QIDQ1007565

Kurt Mehlhorn, Stephen S. Kwek

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

algorithmscombinatorial algorithmsbinary searchrational numbers

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (13)

Order statistics in the Farey sequences in sublinear time and counting primitive lattice points in polygons ⋮ Characteristic function games with restricted agent interactions: core-stability and coalition structures ⋮ Solving generic nonarchimedean semidefinite programs using stochastic game algorithms ⋮ Improved bounds for the CF algorithm ⋮ Operations research applications of dichotomous search ⋮ A note on the approximation of mean-payoff games ⋮ Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata ⋮ Exact quantitative probabilistic model checking through rational search ⋮ On the complexity of real root isolation using continued fractions ⋮ Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches ⋮ Parametric integer programming algorithm for bilevel mixed integer programs ⋮ Faster algorithms for quantitative verification in bounded treewidth graphs ⋮ On a class of covering problems with variable capacities in wireless networks

Cites Work

• On search over rationals
• Rational search
• Efficient search for rationals
• An optimal algorithm for finding all the jumps of a monotone step-function
• A generalization of binary search
• Unnamed Item
• Unnamed Item

This page was built for publication: Optimal search for rationals