期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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:DR0 by making oracle queries to a heuristic hf satisfying minxSf(x)hf(S)minxSf(x) for some 1 and any subset S in some allowed class of subsets of the domain D. We show tight upper and lower bounds on the number of queries q needed to find even a -approximate minimizer for quite large in a number of interesting settings, as follows. - For arbitrary functions f:01nR0 , where contains all subsets of the domain, we show that no branch-and-bound algorithm can achieve nlogq , while a simple greedy algorithm achieves essentially nlogq . - For a large class of MAX-CSPs, where :=Sw 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 1+log(q)n . - For the Traveling Salesperson Problem (TSP), where :=Sp contains each set of tours extending a path p, we show that no branch-and-bound algorithm can achieve (−1)nlogq . 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 hf 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 hf 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 hf as a data structure, we see that our results unconditionally rule out black-box search-to-decision reductions for data structures.
关键词：Approximation Algorithms;Inapproximability;MAX-CSP;oracle model;search-to-decision reductions;Traveling Salesman Problem
