Abstract
We study the question of when an approximate search optimization problem is harder than the associated decision problem. Specifically, we study a natural and quite general model of blackbox searchtodecision reductions, which we call branchandbound reductions (in analogy with branchandbound algorithms). In this model, an algorithm attempts to minimize (or maximize) a function f: D → ℝ_{≥ 0} by making oracle queries to h_f : 𝒮 → ℝ_{≥ 0} satisfying
min_{x ∈ S} f(x) ≤ h_f(S) ≤ γ ⋅ min_{x ∈ S} f(x) (*)
for some γ ≥ 1 and any subset S in some allowed class of subsets 𝒮 of the domain D. (When the goal is to maximize f, h_f instead yields an approximation to the maximal value of f over S.) We show tight upper and lower bounds on the number of queries q needed to find even a γ'approximate minimizer (or maximizer) for quite large γ' in a number of interesting settings, as follows.
 For arbitrary functions f : {0,1}ⁿ → ℝ_{≥ 0}, where 𝒮 contains all subsets of the domain, we show that no branchandbound reduction can achieve γ' ≲ γ^{n/log q}, while a simple greedy approach achieves essentially γ^{n/log q}.
 For a large class of MAXCSPs, where 𝒮 := {S_w} contains each set of assignments to the variables induced by a partial assignment w, we show that no branchandbound reduction can do significantly better than essentially a random guess, even when the oracle h_f guarantees an approximation factor of γ ≈ 1+√{log(q)/n}.
 For the Traveling Salesperson Problem (TSP), where 𝒮 := {S_p} contains each set of tours extending a path p, we show that no branchandbound reduction can achieve γ' ≲ (γ1) n/log q. We also prove a nearly matching upper bound in our model.
These results show an oracle model in which approximate search and decision are strongly separated. (In particular, our result 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.) We also note two alternative interpretations of our results. First, if we view h_f as a data structure, then our results unconditionally rule out blackbox searchtodecision reductions for certain data structure problems. Second, if we view h_f as an efficiently computable heuristic, then our results show that any reasonably efficient branchandbound algorithm requires more guarantees from its heuristic than simply Eq. (*).
Behind our results is a "useless oracle lemma," which allows us to argue that under certain conditions the oracle h_f is "useless," and which might be of independent interest. See also the full version [Alexander Golovnev et al., 2022].
BibTeX  Entry
@InProceedings{golovnev_et_al:LIPIcs.APPROX/RANDOM.2023.10,
author = {Golovnev, Alexander and Guo, Siyao and Peters, Spencer and StephensDavidowitz, Noah},
title = {{The (Im)possibility of Simple SearchToDecision Reductions for Approximation Problems}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {10:110:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772969},
ISSN = {18688969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18835},
URN = {urn:nbn:de:0030drops188351},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.10},
annote = {Keywords: searchtodecision reductions, oracles, constraint satisfaction, traveling salesman, discrete optimization}
}
Keywords: 

searchtodecision reductions, oracles, constraint satisfaction, traveling salesman, discrete optimization 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) 
Issue Date: 

2023 
Date of publication: 

04.09.2023 