Krygin V., Khomenko R.
Self-driven algorithm for solving supermodular (max, +) labeling problems based on subgradient descent

An algorithm presented in this article gives one of two answers to any (max,+) labeling problem with integer weights given at the input, namely, either a solution in the form of the optimal labeling or the phrase “The problem is not supermodular” with any of these answers guaranteed to be correct. The self-driven properties of the algorithm are in the fact that the user cannot decide, which of the two questions are to be answered, as it is up to the algorithm what is in its area of competence. Another special feature of the algorithm is the fact that it does not need to know the order of labels in the case of supermodular problems. The finite number of steps of the algorithm is guaranteed by using subgradient descent and the integer weights of vertices and edges. © 2022, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: (max,+), discrete optimization, graphical models, labeling problems, self-driven pattern recognition, structural pattern recognition, supermodular labeling problems, Optimization, (max,+), Discrete optimization, GraphicaL model, Labeling problem, Labelings, Self-driven, Self-driven pattern recognition, Structural pattern recognition, Supermodular, Supermodular labeling problem, Pattern recognition

Cite:
Krygin V., Khomenko R. (2022). Self-driven algorithm for solving supermodular (max, +) labeling problems based on subgradient descent. Cybernetics and Systems Analysis, 58 (4), 24–31. doi: https://doi.org/10.1007/s10559-022-00485-8 http://jnas.nbuv.gov.ua/article/UJRN-0001335516 [In Ukrainian].