Query strategies for priced information, revisited

We consider the problem of designing query strategies for priced information, introduced by Charikar et al. In this problem the algorithm designer is given a function f : {0, 1}n → {±1} and a price associated with each of the n coordinates. The goal is to design a query strategy for determining f's value on unknown inputs for minimum cost.