Алгоритм Биркгофа
-
Алгоритм Биркгофа и его применение
- Алгоритм Биркгофа используется для разложения бистохастических матриц на выпуклые комбинации матриц перестановок.
- Применяется в задаче справедливого случайного распределения, где позволяет представить случайное распределение в виде лотереи с детерминированным распределением.
-
Терминология и свойства бистохастических матриц
- Бистохастическая матрица — это матрица с элементами, равными или большими нуля, и суммой элементов в каждой строке и столбце равной единице.
- Матрица перестановок — это частный случай бистохастической матрицы с элементами, равными 0 или 1.
- Разложение Биркгофа представляет бистохастическую матрицу как сумму матриц перестановок с неотрицательными весами.
-
Теоремы и инструменты
- Теорема Денеса Кенига утверждает, что каждая бистохастическая матрица имеет набор перестановок с положительными элементами.
- Граф положительности матрицы представляет собой двудольный граф, и идеальное соответствие на этом графе эквивалентно нахождению набора перестановок с положительными элементами.
- Алгоритм Биркгофа является жадным алгоритмом, который находит идеальные соответствия и удаляет их из матрицы.
-
Сложность и обобщения
- Сложность алгоритма Биркгофа составляет O(n2), но может быть улучшена до O(n2 − 2n + 2) в некоторых случаях.
- Алгоритм может быть обобщен на неквадратичные матрицы и недвудольные графы, а также на задачу минимизации расхождения в ожидаемых значениях.
Полный текст статьи: