# The Power of Human-Algorithm Collaboration in Solving Combinatorial Optimization Problems
###### Abstract  
Many combinatorial optimization problems are often considered intractable to solve exactly or by approximation. An example of such a problem is _maximum clique_, which--under standard assumptions in complexity theory--cannot be solved in sub-exponential time or be approximated within the polynomial factor efficiently. However, we show that if a _polynomial time_ algorithm can query informative Gaussian priors from an expert \(poly(n)\) times, then a class of combinatorial optimization problems can be solved efficiently up to a multiplicative factor \(\epsilon\), where \(\epsilon\) is arbitrary constant. In this paper, we present proof of our claims and show numerical results to support them. Our methods can cast new light on how to approach optimization problems in domains where even the approximation of the problem is not feasible. Furthermore, the results can help researchers to understand the structures of these problems (or whether these problems have any structure at all). While the proposed methods can be used to approximate combinatorial problems in NPO, we note that the scope of the problems solvable might well include problems that are provable intractable (problems in EXPTIME).  
combinatorial optimization; bayesian optimization; NP-hardness; human-algorithm collaboration +
Footnote †: journal: Applied Soft Computing  
1
Footnote 1: email: {[PERSON], [PERSON], M.  
during the execution. Combinatorial complexity means the size of the problem's search space. For instance, in the maximum clique, the combinatorial complexity is \(O(2^{n})\) but in the travelling salesman problem, the combinatorial complexity is \(O(n!)\). Note that _any_ NP optimization problem can be reduced into, say, a clique problem, which _has_ a combinatorial complexity of \(O(2^{n})\). Further, we show that the scope of possible problems solvable with the proposed method includes even problems with super-exponential search spaces.  
Bayesian optimization is a framework to solve hard function problems and is based on Bayesian statistics. Usually, before the actual Bayesian optimization, an _expert_ provides the algorithm with some information about the problem that is being optimized in a form of a _Gaussian prior_. It reflects one's understanding on shape and smoothness of the objective function. Querying Gaussian priors from human experts is a very common assumption in Bayesian optimization literature [12]. In the _fully_ Bayesian approach to AI and global optimization, the optimization procedure based on Gaussian processes expects the Gaussian prior \(G(\mu,\Sigma)\) as part the input [13]. That is, the prior is decided by a human expert. Additionally, in fully Bayesian cases, the prior is expected to be correct. More specifically, the function being optimized is a realization of the previously given Gaussian prior (in Figure 1, 3 realizations of Wiener processes, for instance). In this paper, we make similar assumptions. We expect that the priors are _consistent_ and _informative_. These assumptions are quite realistic and very standard, because the expert has access to previous function evaluations, problem instances and multiple prior sampling heuristics such as the maximum likehood estimation.  
Nevertheless, we stress that we do not claim to solve any notoriously hard problem in theoretical computer science. Instead, we show that human-algorithm collaboration can help us solve even those problems considered intractable in the future as this field matures.  
This paper is organized as follows. First, we introduce the concept of Bayesian optimization. Second, we show how to reduce a class of combinatorial optimization problem instances to a _univariate_ finite domain function, which can then be approximated by our human-algorithm collaboration Bayesian optimization algorithm that we introduce thereafter. Finally, we conclude our research and mention some future directions.  
Figure 1: 3 realizations of the Wiener process.