On provably best construction heuristics for hard combinatorial optimization problems

In this article, a heuristic is said to be provably best if, assuming P N P , no other heuristic always finds a better solution (when one exists). This extends the usual notion of ‘best possible’ approximation algorithms to include a larger class of heuristics. We illustrate the idea on several problems that are somewhat stylized versions of real‐life network optimization problems, including the maximum clique, maximum k‐club, minimum (connected) dominating set, and minimum vertex coloring problems. The corresponding provably best construction heuristics resemble those commonly used within popular metaheuristics. Along the way, we show that it is hard to recognize whether the clique number and the k‐club number of a graph are equal, yet a polynomial‐time computable function is ‘sandwiched’ between them. This is similar to the celebrated Lovász function wherein an efficiently computable function lies between two graph invariants that are N P ‐hard to compute.