On provably best construction heuristics for hard combinatorial optimization problems
Abstract
In this article, a heuristic is said to be provably best if, assuming , 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 ‐hard to compute. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 238–245 2016Keywords
Funding Information
- AFRL Mathematical Modeling and Optimization Institute
- AFOSR (FA9550-12-1-0103, FA8651-12-2-0011, FA9550-11-1-0037)
- US Air Force Summer Faculty Fellowship
This publication has 40 references indexed in Scilit:
- On inclusionwise maximal and maximum cardinality -clubs in graphsDiscrete Optimization, 2012
- Δ-List vertex coloring in linear timeInformation Processing Letters, 2006
- On NP-hardness of the clique partition—Independence number gap recognition and related problemsDiscrete Mathematics, 2006
- Metaheuristics in Combinatorial OptimizationAnnals of Operations Research, 2005
- Recognizing Berge GraphsCombinatorica, 2005
- A fast algorithm for the maximum clique problemDiscrete Applied Mathematics, 2002
- Greedy Randomized Adaptive Search ProceduresJournal of Global Optimization, 1995
- An exact algorithm for the maximum clique problemOperations Research Letters, 1990
- A fast parallel algorithm to color a graph with Δ colorsJournal of Algorithms, 1988
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976