Power of human-algorithm collaboration in solving combinatorial optimization problems
This work provides a theoretical framework for potentially solving intractable combinatorial problems, though it is incremental as it relies on idealized expert priors.
The authors tackled combinatorial optimization problems, such as maximum clique, which are typically intractable, by showing that with polynomial-time queries to expert Gaussian priors, these problems can be solved efficiently in expectation up to an arbitrary constant multiplicative factor ε.
Many combinatorial optimization problems are often considered intractable to solve exactly or by approximation. An example of such problem is maximum clique which -- under standard assumptions in complexity theory -- cannot be solved in sub-exponential time or be approximated within polynomial factor efficiently. 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 in expectation up to a multiplicative factor $ε$ where $ε$ is arbitrary constant. While our proposed methods are merely theoretical, they cast new light on how to approach solving these problems that have been usually considered intractable.