Premium
On provably best construction heuristics for hard combinatorial optimization problems
Author(s) -
KahrumanAnderoglu Sera,
Buchanan Austin,
Butenko Sergiy,
Prokopyev Oleg A.
Publication year - 2016
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21620
Subject(s) - heuristics , vertex connectivity , heuristic , clique , mathematics , vertex (graph theory) , computer science , combinatorics , parameterized complexity , time complexity , metaheuristic , mathematical optimization , graph , discrete mathematics
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. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 238–245 2016