I often find flights through a search engine like Google Flights. On input some refined subset of the space of all flights (e.g., non-stop only, departing in the morning, from one of two airports, and on a certain date) the search engine returns the cheapest flight in this subset. My goal using the search engine, however, is not so simple as restricting to a subset and finding the cheapest flight. Rather, I mentally place a certain dollar value on how much I am willing to pay extra for various options: e.g., willing to pay \$20 extra for nonstop, willing to pay \$50 extra for closer airport. I want to find the cheapest flight after these dollar values are taken into account.
This raises an algorithmic question: how many queries to the search engine does it take to find the best flight? We can formulate this as the following search problem:
$X$ is a search space (set of flights);
$f: X \to \mathbb{R}^+$ is an unknown price function, where $f(x)$ is the price of $x$;
$g: X \to \mathbb{R}^+$ is a known additional cost to us, which we assume is a weighted sum of $k$ known indicator functions: $$ g(x) = \alpha_1 [x \in A_1] + \alpha_2 [x \in A_2] + \cdots + \alpha_k [x \in A_k], $$ where $\alpha_i \ge 0$ are weights and $[x \in A] = \begin{cases} 1 &\text{if } x \in A \\ 0 &\text{otherwise} \end{cases}$ is the Iverson bracket.
The problem: Determine $\min_{x \in X} (f(x) + g(x))$, using queries to an oracle which, on input any subset $X' \subseteq X$, returns $\min_{x \in X'} f(x)$ and $\arg\min_{x \in X'} f(x)$.
Question 1: As a function of $k$, how many queries to the oracle are needed in the worst case?
It can easily be done in $2^k$ queries: the sets $A_1, A_2, \ldots, A_k$ collectively partition $X$ into $2^k$ regions, so we can query on each subset. Is there a better algorithm in general?
Question 2: Assume that the actual minimum of $f(x) + g(x)$ falls into at most $k' \ll k$ of the indicator sets $A_i$ (so I'm not going to pay too much extra). As a function of $k$ and $k'$, how many queries to the oracle are now needed?