Heuristic with worst-case exponential complexity

Question

I have been working with some colleagues on a metaheuristic for an NP-Hard optimization problem. It is a genetic algorithm using a steady-state population replacement strategy (at each iteration a single new chromosome is created and used to replace an older one). The algorithm iterates until it fails to find a solution which is better than the current incumbent optimum for a pre-set number of consecutive iterations. The algorithm has been tested on benchmark instances and proved empirically to be fast and effective, outperforming previous approaches.

We submitted our work to a journal and received rather favorable reviews. Among the modification requests, we were asked to state the time complexity of the procedure. While we have no difficulty to evaluate the (polynomial) complexity of a single iteration, we realized that, given the exponentially large solution space and our termination criterion, our algorithm could theoretically iterate an exponential number of times. Is this considered acceptable for a heuristic? After all, I was thinking, the same conclusion may even apply to a simple local search scheme, should it keep finding marginal improvements in its neighborhoods indefinitely without getting trapped in a local optimum.

Should we look into complexity analysis different from worst-case? Do you have references to works we may look into? Apologies if the question is too trivial, we are not "pure" computer scientists (although we submitted this work to a CS journal since we thought it was the right outlet for it).

Answer 1

While there are many heuristics (arguably all of them) that take exponential time in the worst-case, what usually makes them attractive (and marketable) is that they "appear" to perform much better in practice, and in fact it's hard to find examples where they are provably exponential.

Two canonical examples are the simplex algorithm for linear programming and the $k$-means heuristic for clustering.

It seems highly unlikely that you'll be able to show a worst-case running time that's better than exponential for a GA-like heuristic. As Tobias points out, it would be useful to know if there's some kind of guarantee of quality if the heuristic is terminated early - but I'm pessimistic that this can be done as well.

Answer 2

SAT-solvers are another common class of heuristics. There are many and of course they take exponential time in the worst case.

My suggestion is to explain to the reviewers that the problem is NP-complete and cannot be solved or approximated in less than exponential time if there are such results. That should suffice if your algorithm outperforms the best known algorithm on standard benchmarks for the problem.

Also you might want to submit your paper to a venue which had published heuristics for the problem before.

Answer 3

As I understand your algorithm, whether or not the worst-case running time is exponential does not depend on the size of the search space. If the number of different possible solution values happened to be upper bounded by a polynomial in the input size, then the complexity of your heuristic would be polynomial, too. This is true for many canonical NP-hard problems. Otherwise, additional information about the problem would probably allow for better advice.

Regarding your question whether exponential runtime would be acceptable for a heuristic, my guess is that a good approximation guaranty would be a minimum requirement. I assume that the problem we are dealing with is already solvable in exponential time without error, so why use a less reliable heuristic if it does not save us time?