Four questions on Birkhoff polytopes
type: Item
instance of: scholarly article
title: Four questions on Birkhoff polytopes
zbMATH Open document ID: 0974.52010
DOI: 10.1007/PL00001277
author: Igor Pak
published in: Annals of Combinatorics
publication date: 2001-12-09T00:00:00Z
review text: In this article, the author asks four questions about the Birkhoff polytopes. The Birkhoff polytope \(P_n\) is the \((n-1)^2\) dimensional polytope consisting of all \(n\) by \(n\) matrices whose entries are non-negative and whose rows and columns all sum to \(1\). The author addresses the question of the volume of \(P_n\), proving that it has the same volume as a different polytope. He also shows that the simplex method runs in exponential time in \(n\) in the worst case, but in polynomial time in the average case. He also shows that (certain) random walks mix fast on \(P_n\), and shows that this is not true of the prism whose top and bottom are \(P_n\).
Mathematics Subject Classification ID: 52B05
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 1449073
zbMATH Keywords: Birkhoff polytope
zbMATH Keywords: simplex method
zbMATH Keywords: random walk
zbMATH Keywords: symmetric group
zbMATH Keywords: mixing time
Wikidata QID: Q56003270
reviewed by: Michael I. Hartley
MaRDI profile type: Publication
full work available at URL: pl00001277
OpenAlex ID: W2126244582
description: scientific article; zbMATH DE number 1449073