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

Simple item page
dc.contributor.authorСтецюк, Петро
dc.contributor.authorЛяшко, Володимир
dc.contributor.authorБардадим, Тамара
dc.date.accessioned2018-01-27T19:00:26Z
dc.date.available2018-01-27T19:00:26Z
dc.date.issued2017
dc.description.abstractУ статті розглянуто властивості верхніх оцінок для квадратичної задачі про максимальний k-плекс у неорієнтованому графі. Проаналізовано зв’язок квадратичної задачі для 1-плекса з відомим формулюванням квадратичної задачі для знаходження максимальної кліки графа. Наведено лагранжеві двоїсті оцінки для найпростіших квадратичних задач та показано, що їх можна покращити при додаванні функціонально надлишкових обмежень.uk_UA
dc.description.abstractThe 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.identifier.citationСтецюк П. І. Властивості квадратичної задачі про максимальний k-плекс у неорієнтованому графі / Стецюк П. І., Ляшко В. І., Бардадим Т. О. // Наукові записки НаУКМА. Комп'ютерні науки. - 2017. - Т. 198. - С. 8-13.uk_UA
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/12540
dc.language.isoukuk_UA
dc.relation.sourceНаукові записки НаУКМА: Комп'ютерні наукиuk_UA
dc.statuspublished earlieruk_UA
dc.subjectфункціонально надлишкове обмеженняuk_UA
dc.subjectлагранжева двоїста оцінкаuk_UA
dc.subjectквадратична задачаuk_UA
dc.subjectfunctionally superfluous constraintsen_US
dc.subjectquadratic problemen_US
dc.subjectстаттяuk_UA
dc.subjectстаттяuk_UA
dc.titleВластивості квадратичної задачі про максимальний k-плекс у неорієнтованому графіuk_UA
dc.title.alternativeProperties of the Quadratic Problem about Maximum k-plex in Undirected Graphen_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Stetsiuk_Vlastyvosti_kvadratychnoi.pdf
Size:
336.3 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
198: Комп'ютерні науки
Кафедра інформатики