eKMAIR

Властивості квадратичної задачі про максимальний k-плекс у неорієнтованому графі

Show simple item record

dc.contributor.author Стецюк, Петро
dc.contributor.author Ляшко, Володимир
dc.contributor.author Бардадим, Тамара
dc.date.accessioned 2018-01-27T19:00:26Z
dc.date.available 2018-01-27T19:00:26Z
dc.date.issued 2017
dc.identifier.citation Стецюк П. І. Властивості квадратичної задачі про максимальний k-плекс у неорієнтованому графі / Стецюк П. І., Ляшко В. І., Бардадим Т. О. // Наукові записки НаУКМА. Комп'ютерні науки. - 2017. - Т. 198. - С. 8-13. uk_UA
dc.identifier.uri http://ekmair.ukma.edu.ua/handle/123456789/12540
dc.description.abstract У статті розглянуто властивості верхніх оцінок для квадратичної задачі про максимальний k-плекс у неорієнтованому графі. Проаналізовано зв’язок квадратичної задачі для 1-плекса з відомим формулюванням квадратичної задачі для знаходження максимальної кліки графа. Наведено лагранжеві двоїсті оцінки для найпростіших квадратичних задач та показано, що їх можна покращити при додаванні функціонально надлишкових обмежень. uk_UA
dc.description.abstract 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. en_US
dc.language.iso uk uk_UA
dc.subject функціонально надлишкове обмеження uk_UA
dc.subject лагранжева двоїста оцінка uk_UA
dc.subject квадратична задача uk_UA
dc.subject functionally superfluous constraints en_US
dc.subject quadratic problem en_US
dc.subject стаття uk_UA
dc.subject стаття uk_UA
dc.title Властивості квадратичної задачі про максимальний k-плекс у неорієнтованому графі uk_UA
dc.title.alternative Properties of the Quadratic Problem about Maximum k-plex in Undirected Graph en_US
dc.type Article uk_UA
dc.status published earlier uk_UA
dc.relation.source Наукові записки НаУКМА: Комп'ютерні науки uk_UA


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Browse

My Account

Statistics