Pairwise Similarity Estimation for Discrete Optimization Problems

Abstract

In this paper, we propose a new method, called the pairwise similarity method, for assessing the similarity of instances of optimization problems. This method is a generalization of the metric approach proposed earlier for scheduling problems. It relaxes the requirements to the structure of the problem constraints. The method involves a dissimilarity function for the comparison of instances. It identifies “simple” instances that can be solved in polynomial time and uses them to get good approximations for other instances. We apply the pairwise similarity method to two discrete optimization problems: the majority domination problem and the maximum cut problem.