Алгоритм Биркгофа

• Алгоритм Биркгофа и его применение

  • Алгоритм Биркгофа используется для разложения бистохастических матриц на выпуклые комбинации матриц перестановок. 
  • Применяется в задаче справедливого случайного распределения, где позволяет представить случайное распределение в виде лотереи с детерминированным распределением. 

• Терминология и свойства бистохастических матриц

  • Бистохастическая матрица — это матрица с элементами, равными или большими нуля, и суммой элементов в каждой строке и столбце равной единице. 
  • Матрица перестановок — это частный случай бистохастической матрицы с элементами, равными 0 или 1. 
  • Разложение Биркгофа представляет бистохастическую матрицу как сумму матриц перестановок с неотрицательными весами. 

• Теоремы и инструменты

  • Теорема Денеса Кенига утверждает, что каждая бистохастическая матрица имеет набор перестановок с положительными элементами. 
  • Граф положительности матрицы представляет собой двудольный граф, и идеальное соответствие на этом графе эквивалентно нахождению набора перестановок с положительными элементами. 
  • Алгоритм Биркгофа является жадным алгоритмом, который находит идеальные соответствия и удаляет их из матрицы. 

• Сложность и обобщения

  • Сложность алгоритма Биркгофа составляет O(n2), но может быть улучшена до O(n2 − 2n + 2) в некоторых случаях. 
  • Алгоритм может быть обобщен на неквадратичные матрицы и недвудольные графы, а также на задачу минимизации расхождения в ожидаемых значениях.