Fast Kemeny consensus by searching over standard matrices distanced to the averaged expert ranking by minimal difference

Скорочена інформація про документ
dc.contributor.authorRomanuke, Vadim V.
dc.contributor.authorРоманюк, Вадим Васильович
dc.contributor.authorРоманюк, Вадим Васильевич
dc.date.accessioned2016-11-19T09:59:05Z
dc.date.available2016-11-19T09:59:05Z
dc.date.issued2016
dc.description.abstractenBackground. The problem of ranking a finite set of objects is considered. Objective. The goal is to develop an algorithm that would let speed up the search of the Kemeny consensus along with substantiation of a metric to compare rankings. Methods. An approach for aggregating experts’ rankings is suggested and substantiated. Also a metric to compare rankings is suggested and substantiated. Results. The developed algorithm finds a set of Kemeny rankings much faster than the classical straightforward search. Also this set often contains a single Kemeny consensus, what fails by the straightforward search. Besides, a single Kemeny consensus is determined at one stroke if the averaged expert ranking turns out acyclic. Thus the problem of selecting a single Kemeny consensus is solved. Conclusions. For 10 objects and more, where most known approaches become intractable, the algorithm still is tractable due to searching over only those standard matrices whose distance to the first ranking differs minimally from the distance between this ranking and the averaged expert ranking.uk
dc.description.abstractruПроблематика. Рассматривается задача ранжирования конечного множества объектов. Цель исследования. Разработка алгоритма, который позволил бы ускорить поиск согласованности по Кемени вместе с обоснованием метрики для сравнения ранжирований. Методика реализации. Предлагается и обосновывается подход относительно объединения экспертных ранжирований. Также предлагается и обосновывается метрика для сравнения ранжирований. Результаты исследования. Разработанный алгоритм находит множество ранжирований Кемени гораздо быстрее, чем классический прямой поиск. Также это множество часто содержит единственную согласованность по Кемени, что не удается при прямом поиске. Кроме этого, единственная согласованность по Кемени определяется сразу, если усредненное экспертное ранжирование оказывается ациклическим. Так решается задача выбора единственной согласованности по Кемени. Выводы. Для 10 и более объектов, где большинство известных подходов становятся неисполнимыми, алгоритм является осуществимым благодаря поиску по только тем стандартным матрицам, чье расстояние к первому ранжированию отличается от расстояния между этим ранжированием и усредненным экспертным ранжированием на минимальную величину.uk
dc.description.abstractukПроблематика. Розглядається задача ранжування скінченної множини об’єктів. Мета дослідження. Розробка алгоритму, який дав би змогу пришвидшити пошук узгодженості за Кемені поряд з обґрунтуванням метрики для порівняння ранжувань. Методика реалізації. Пропонується й обґрунтовується підхід щодо об’єднання експертних ранжувань. Також пропонується й обґрунтовується метрика для порівняння ранжувань. Результати дослідження. Розроблений алгоритм знаходить множину ранжувань Кемені значно швидше, ніж класичний прямий пошук. Також ця множина часто містить єдину узгодженість за Кемені, що не вдається за прямого пошуку. Крім цього, єдина узгодженість за Кемені визначається відразу, якщо усереднене експертне ранжування виявляється ациклічним. Так розв’язується задача вибору єдиної узгодженості за Кемені. Висновки. Для 10 і більше об’єктів, де більшість відомих підходів стають незастосовними, алгоритм є реалізовним завдяки пошуку по тільки тих стандартних матрицях, чия відстань до першого ранжування відрізняється від відстані між цим ранжуванням та усередненим експертним ранжуванням на мінімальну величину.uk
dc.format.pagerangeС. 58-65uk
dc.identifier.citationRomanuke V. V. Fast Kemeny consensus by searching over standard matrices distanced to the averaged expert ranking by minimal difference / V. V. Romanuke // Наукові вісті НТУУ «КПІ» : міжнародний науково-технічний журнал. – 2016. – № 1(105). – С. 58–65. – Бібліогр.: 14 назв.uk
dc.identifier.doihttps://doi.org/10.20535/1810-0546.2016.1.59784
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/18126
dc.language.isoenuk
dc.publisherНТУУ «КПІ»uk
dc.publisher.placeКиївuk
dc.sourceНаукові вісті НТУУ «КПІ» : міжнародний науково-технічний журнал, 2016, № 1(105)uk
dc.status.pubpublisheduk
dc.subjectrankingen
dc.subjectKemeny consensusen
dc.subjectaveraged expert rankingen
dc.subjectранжуванняuk
dc.subjectузгодженість за Кеменіuk
dc.subjectусереднене експертне ранжуванняuk
dc.subjectранжированиеru
dc.subjectсогласованность по Кемениru
dc.subjectусредненное экспертное ранжированиеru
dc.subject.udc510.3+519.1+519.2uk
dc.titleFast Kemeny consensus by searching over standard matrices distanced to the averaged expert ranking by minimal differenceuk
dc.title.alternativeШвидка узгодженість за Кемені на основі пошуку по стандартних матрицях з мінімальною відстанню до усередненого експертного ранжуванняuk
dc.title.alternativeБыстрая согласованность по Кемени на основе поиска по стандартным матрицам с минимальным расстоянием до усредненного экспертного ранжированияuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
07_Romaniuk.pdf
Розмір:
236.44 KB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
7.71 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Наукові вісті НТУУ «КПІ»: міжнародний науково-технічний журнал, № 1(105)