Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-141 | 28th September 2021 18:50

On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization



We study a natural and quite general model of branch-and-bound algorithms. In this model, an algorithm attempts to minimize (or maximize) a function $f : D \to \mathbb{R}_{\geq 0}$ by making oracle queries to a heuristic $h_f$ satisfying
\min_{x \in S} f(x) \leq h_f(S) \leq \gamma \cdot \min_{x \in S} f(x)
for some $\gamma \geq 1$ and any subset $S$ in some allowed class of subsets $\mathcal{S}$ of the domain $D$. We show tight upper and lower bounds on the number of queries $q$ needed to find even a $\gamma'$-approximate minimizer for quite large $\gamma'$ in a number of interesting settings, as follows.

- For arbitrary functions $f : \{0,1\}^n \to \mathbb{R}_{\geq 0}$, where $\mathcal{S}$ contains all subsets of the domain, we show that no branch-and-bound algorithm can achieve $\gamma' \approx\gamma^{n/\log q}$, while a simple greedy algorithm achieves essentially $\gamma^{n/\log q}$.

- For a large class of MAX-CSPs, where $\mathcal{S} := \{ S_w\}$ contains each set of assignments to the variables induced by a partial assignment $w$, we show that no branch-and-bound algorithm can do significantly better than essentially a random guess, even for $\gamma \approx 1+\sqrt{\log(q)/n}$.

- For the Traveling Salesperson Problem (TSP), where $\mathcal{S} := \{S_p\}$ contains each set of tours extending a path $p$, we show that no branch-and-bound algorithm can achieve $\gamma' \approx (\gamma-1) n/\log q$. We also prove a nearly matching upper bound in our model.

Behind these results is a "useless oracle lemma," which allows us to argue that under certain conditions the heuristic $h_f$ is "useless," and which might be of independent interest.

We also note two alternative interpretations of our model and results. If we interpret the heuristic $h_f$ as an oracle for an approximate decision problem, then our results unconditionally rule out a large and natural class of approximate search-to-decision reductions (which we think of as "branch-and-bound" search-to-decision reductions). We therefore show an oracle model in which approximate search and decision are strongly separated. (In particular, our lower bound for TSP can be viewed as a negative answer to a question posed by Bellare and Goldwasser (SIAM J. Comput. 1994), though only in an oracle model.) By instead interpreting $h_f$ as a data structure, we see that our results unconditionally rule out black-box search-to-decision reductions for data structures.

ISSN 1433-8092 | Imprint