ABSTRACT
Typically, a combinatorial optimization problem involves a set E of elements (called ground set) and the goal is to arrange, group, order, or select a subset of elements from E that optimizes a given objective function. Classical examples of combinatorial optimization problems include the minimum spanning tree problem, the shortest paths problem, and the traveling salesman problem. This chapter explores the use of local search in the design of approximation algorithms with provable performance guarantee for NP-hard combinatorial optimization problems. Rardin and Sudit introduced paroid search, a generic local optimization algorithm, that under very general conditions is guaranteed to produce in polynomial time a local optimum solution for any combinatorial optimization problem with a paroid structure. The problem with a local search algorithm based on the jump neighborhood is that it might get “trapped” in a local optimum solution of value far away from the optimum.
