Pairwise Similarity Estimation for Discrete Optimization Problems

Main Article Content

Darya Lemtyuzhnikova
Pavel Chebotarev
Mikhail Goubko
Nikita Shushko
Mikhail Somov


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.


Download data is not yet available.

Article Details

How to Cite
Lemtyuzhnikova, D., Chebotarev, P., Goubko, M., Shushko, N., & Somov, M. (2023). Pairwise Similarity Estimation for Discrete Optimization Problems. Advances in Systems Science and Applications, 23(2), 164-177.