Посредничество
Посредственность — это алгоритмическая проблема в теории порядка, касающаяся упорядочивания набора элементов с учетом ограничений, согласно которым некоторые элементы должны быть помещены между другими. [1] Имеет применение в биоинформатике. [2] и как было показано NP-полно Опатрным (1979), . [3]
Постановка задачи
[ редактировать ]Входными данными для задачи промежуточного взаимодействия является набор упорядоченных троек элементов. Элементы, перечисленные в этих тройках, должны быть помещены в общий порядок с тем свойством, что для каждой из данных троек средний элемент тройки появляется в выводе где-то между двумя другими элементами. Элементы каждой тройки не обязательно должны быть последовательными в выводе. [1] [3]
Примеры
[ редактировать ]Например, коллекция входных троек
- (2,1,3), (3,4,5), (1,4,5), (2,4,1), (5,2,3)
удовлетворяется порядком вывода
- 3, 1, 4, 2, 5
но не через
- 3, 1, 2, 4, 5.
В первом из этих выходных упорядочений для всех пяти входных троек средний элемент тройки появляется между двумя другими элементами. Однако для второго порядка вывода элемент 4 не находится между элементами 1 и 2, что противоречит требованию, заданному тройкой (2,4,1).
Если входные данные содержат две тройки, такие как (1,2,3) и (2,3,1), с одинаковыми тремя элементами, но с другим выбором среднего элемента, то правильного решения не существует. Однако существуют более сложные способы формирования набора троек без допустимого решения, которые не содержат такой пары противоречивых троек.
Сложность
[ редактировать ]Опатрный (1979) показал, что версия решения проблемы посредничества (в которой алгоритм должен решить, существует или нет допустимое решение) является NP-полной двумя способами: за счет редукции от 3-выполнимости , а также за счет другой редукции из гиперграфа 2-раскраски . [3] Однако ее можно легко решить, если все неупорядоченные тройки элементов представлены упорядоченной тройкой входных данных, выбрав один из двух элементов, которые не находятся между другими, в качестве начала упорядочивания, а затем используя тройки, включающие это item для сравнения относительных положений каждой пары оставшихся элементов.
Связанная с этим проблема поиска порядка, который максимизирует количество удовлетворенных троек, является MAXSNP-трудной , подразумевая, что невозможно достичь коэффициента аппроксимации , сколь угодно близкого к 1, за полиномиальное время, если только P = NP . [1] По-прежнему трудно решить или аппроксимировать даже плотные примеры, которые включают упорядоченную тройку для каждой возможной неупорядоченной тройки элементов. [4] Было доказано, что минимальная версия задачи, ограниченная турнирами, имеет схемы аппроксимации полиномиального времени (PTAS). [5] Можно достичь коэффициента аппроксимации 1/3 (в ожидании), упорядочивая элементы случайным образом, и эта простая стратегия дает наилучшую возможную аппроксимацию за полиномиальное время, если гипотеза об уникальных играх верна. [6] Также возможно использовать полуопределенное программирование или комбинаторные методы, чтобы найти порядок, который удовлетворяет хотя бы половине троек любого выполнимого экземпляра, за полиномиальное время. [1] [7]
В параметризованной сложности проблема удовлетворения как можно большего количества ограничений из набора C ограничений решается с фиксированным параметром, если параметризована разностью q - | C |/3 между качеством решения q, найденным параметризованным алгоритмом, и | Качество C |/3 гарантировано в ожидании случайным упорядочиванием. [8]
Хотя успех не гарантирован, жадная эвристика может найти решения во многих случаях проблемы посредничества, возникающей на практике. [2]
Приложения
[ редактировать ]Одно из применений посредничества возникает в биоинформатике как часть процесса картирования генов . Определенные типы генетических экспериментов могут использоваться для определения порядка троек генетических маркеров, но не позволяют отличить генетическую последовательность от ее обратной, поэтому информация, полученная в результате такого эксперимента, определяет только то, какой из трех маркеров является средним. Проблема посредничества представляет собой абстракцию проблемы сборки набора маркеров в единую последовательность при наличии экспериментальных данных такого типа. [1] [2]
Проблема посредничества также использовалась для моделирования теорий вероятности , причинности и времени . [9]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д и Чор, Бенни ; Судан, Мадху (1998), «Геометрический подход к взаимосвязи», SIAM Journal on Discrete Mathematics , 11 (4): 511–523 (электронный), doi : 10.1137/S0895480195296221 , MR 1640920 .
- ^ Перейти обратно: а б с Слоним, Донна; Кругляк Леонид; Штейн, Линкольн; Ландер, Эрик (1997), «Построение карт генома человека с помощью радиационных гибридов», Journal of Computational Biology , 4 (4): 487–504, doi : 10.1089/cmb.1997.4.487 , PMID 9385541 .
- ^ Перейти обратно: а б с Опатрны, Дж. (1979), «Проблема тотального порядка», SIAM Journal on Computing , 8 (1): 111–114, doi : 10.1137/0208008 , MR 0522973 .
- ^ Эйлон, Нир; Алон, Нога (2007), «Трудность полностью плотных задач», Information and Computation , 205 (8): 1117–1129, doi : 10.1016/j.ic.2007.02.006 , MR 2340896 .
- ^ Карпински, Марек; Шуди, Уоррен (2011), «Схемы аппроксимации проблемы взаимосвязи в турнирах и связанных с ней проблем ранжирования», в Л. А. Голдберге, К. Янсене, Р. Рави и JDP Ролиме (ред.), Proc. ПРИБЛИЗИТЕЛЬНО 2011, СЛУЧАЙНЫЙ 2011 , Конспект лекций по информатике , вып. 6845, стр. 277–288, arXiv : 0911.2214 , doi : 10.1007/978-3-642-22935-0_24 , S2CID 7180847
- ^ Чарикар, Моисей ; Гурусвами, Венкатесан ; Манокаран, Райсекар (2009), «Каждая перестановка CSP арности 3 устойчива к аппроксимации», 24-я ежегодная конференция IEEE по вычислительной сложности , стр. 62–73, doi : 10.1109/CCC.2009.29 , MR 2932455 , S2CID 257225 .
- ^ Макарычев, Юрий (2012), «Простой алгоритм аппроксимации линейного времени для взаимосвязи», Operations Research Letters , 40 (6): 450–452, doi : 10.1016/j.orl.2012.08.008 , MR 2998680 .
- ^ Гутин, Григорий ; Ким, Ын Чжон ; Мних, Матиас; Йео, Андерс (2010), «Параметризация промежутка выше жесткой нижней границы», Journal of Computer and System Sciences , 76 (8): 872–878, arXiv : 0907.5427 , doi : 10.1016/j.jcss.2010.05.001 , MR 2722353 , S2CID 3408698 .
- ^ Hvátal, Вашек ; Ву, Баойиндуренг (2011), «О причинной связи Райхенбаха», Erkenntnis , 76 (1): 41–48, arXiv : 0902.1763 , doi : 10.1007/s10670-011-9321-z , S2CID 14123568 .