Query strategies for priced information

DOI10.1006/jcss.2002.1828zbMath1015.68244OpenAlexW2130519052WikidataQ57904549 ScholiaQ57904549MaRDI QIDQ696973

Moses Charikar, Venkatesan Guruswami, Prabhakar Raghavan, Ronald Fagin, Jon M. Kleinberg

Publication date: 12 September 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/fbfefe2f1ecc097fd267a7e351985c3cf5224fc2

zbMATH Keywords

analysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Related Items

The hardness of the expected decision depth problem, A note on the size of minimal covers, Computing similarity distances between rankings, Decision trees for function evaluation: simultaneous optimization of worst and expected cost, Operations research applications of dichotomous search, Competitive evaluation of threshold functions in the priced information model, A randomized competitive algorithm for evaluating priced AND/OR trees, Finding optimal satisficing strategies for and-or trees, Evaluation of monotone DNF formulas, The binary identification problem for weighted trees, Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case, Sorting and Selection with Random Costs, Explorable uncertainty in scheduling with non-uniform testing times

Cites Work

• Randomized vs. deterministic decision tree complexity for read-once Boolean functions
• Lower bounds on probabilistic linear decision trees
• The minimum latency problem
• On the Optimality of Randomized $\alpha$-$\beta$ Search
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item