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 2016
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jul 01, 2015
- Source ID
- 10.1002/net.21620
Entities
People
- Austin Buchanan
- Oleg A. Prokopyev
- Sera Kahruman‐anderoglu
- Sergiy Butenko
Organizations
- Air Force Office of Scientific Research
- United States Air Force
- University of Pittsburgh