Властивості квадратичної задачі про максимальний k-плекс у неорієнтованому графі
Loading...
Date
2017
Authors
Стецюк, Петро
Ляшко, Володимир
Бардадим, Тамара
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
У статті розглянуто властивості верхніх оцінок для квадратичної задачі про максимальний
k-плекс у неорієнтованому графі. Проаналізовано зв’язок квадратичної задачі для 1-плекса з відомим формулюванням квадратичної задачі для знаходження максимальної кліки графа. Наведено
лагранжеві двоїсті оцінки для найпростіших квадратичних задач та показано, що їх можна покращити при додаванні функціонально надлишкових обмежень.
The paper considers properties of upper bounds in the quadratic problem about maximum k-plex in undirected graph. The notion of k-plex is introduced to make the notion of clique to be less restrictive. These notions are widely used in sociology to identify specific subgroups of the population. They also can be used to clusterize data, to optimize information flows in networks, to find targeted subgroups for advertising and promotion, etc. In a general case, optimization problems of finding maximum cliques and k-plexes are NP-hard. For this reason, in the maximum clique problem, finding dual bounds is a widely used approach. These bounds may be used directly, especially if the exact bound can be found, or they may be an integral part of other algorithms similar, for example, to the branch-and-bound algorithm. The relationship between the quadratic problem for 1-plex and a known formulation of the quadratic problem for finding the maximum clique in a graph is analyzed. Lagrangian dual quadratic bounds for the simplest quadratic problems are reported; it is shown that these bounds can be improved by adding functionally superfluous constraints. This approach was proposed by N. Z. Shor for the maximum clique problem and also used in polynomial optimization. Different ways to generate functionally superfluous constraints are proposed. On the example of maximum 2-plex problem different formulation of the resulting quadratic programming problem are discussed and compared. This does not mean, however, that the considered superfluous constraints give an exact dual bound in any quadratic problem. To improve Lagrangian dual quadratic bounds, other ways of generation of superfluous constraints can also be used.
The paper considers properties of upper bounds in the quadratic problem about maximum k-plex in undirected graph. The notion of k-plex is introduced to make the notion of clique to be less restrictive. These notions are widely used in sociology to identify specific subgroups of the population. They also can be used to clusterize data, to optimize information flows in networks, to find targeted subgroups for advertising and promotion, etc. In a general case, optimization problems of finding maximum cliques and k-plexes are NP-hard. For this reason, in the maximum clique problem, finding dual bounds is a widely used approach. These bounds may be used directly, especially if the exact bound can be found, or they may be an integral part of other algorithms similar, for example, to the branch-and-bound algorithm. The relationship between the quadratic problem for 1-plex and a known formulation of the quadratic problem for finding the maximum clique in a graph is analyzed. Lagrangian dual quadratic bounds for the simplest quadratic problems are reported; it is shown that these bounds can be improved by adding functionally superfluous constraints. This approach was proposed by N. Z. Shor for the maximum clique problem and also used in polynomial optimization. Different ways to generate functionally superfluous constraints are proposed. On the example of maximum 2-plex problem different formulation of the resulting quadratic programming problem are discussed and compared. This does not mean, however, that the considered superfluous constraints give an exact dual bound in any quadratic problem. To improve Lagrangian dual quadratic bounds, other ways of generation of superfluous constraints can also be used.
Description
Keywords
функціонально надлишкове обмеження, лагранжева двоїста оцінка, квадратична задача, functionally superfluous constraints, quadratic problem, стаття, стаття
Citation
Стецюк П. І. Властивості квадратичної задачі про максимальний k-плекс у неорієнтованому графі / Стецюк П. І., Ляшко В. І., Бардадим Т. О. // Наукові записки НаУКМА. Комп'ютерні науки. - 2017. - Т. 198. - С. 8-13.