Birkhoff algorithm - Revision history

JJMC89 bot III: Moving :Category:Matrices to :Category:Matrices (mathematics) per Wikipedia:Categories for discussion/Speedy

2025-04-14T21:02:00Z

Moving Category:Matrices to Category:Matrices (mathematics) per Wikipedia:Categories for discussion/Speedy

← Previous revision		Revision as of 21:02, 14 April 2025
Line 90:		Line 90:
	{{reflist}}		{{reflist}}

	[[Category:Matrices]]		[[Category:Matrices (mathematics)]]
	[[Category:Algorithms]]		[[Category:Algorithms]]

Mazewaxie: WP:GENFIXES

2024-04-06T20:18:30Z

WP:GENFIXES

← Previous revision		Revision as of 20:18, 6 April 2024
Line 78:		Line 78:
	[[Vijay Vazirani\|Vazirani]]<ref>{{cite arXiv \|last=Vazirani \|first=Vijay V. \|date=2020-10-14 \|title=An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs \|class=cs.DS \|eprint=2010.05984 }}</ref> generalizes Birkhoff's algorithm to '''non-bipartite graphs'''.		[[Vijay Vazirani\|Vazirani]]<ref>{{cite arXiv \|last=Vazirani \|first=Vijay V. \|date=2020-10-14 \|title=An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs \|class=cs.DS \|eprint=2010.05984 }}</ref> generalizes Birkhoff's algorithm to '''non-bipartite graphs'''.

	Valls et al.<ref>{{cite journal\|last1=Valls\|first1=Victor\|last2=Iosifidis\|first2=Georgios\|last3=Tassiulas\|first3=Leandros\|date=Dec 2021\|title=Birkhoff's Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches \|url=https://arxiv.org/pdf/2011.02752.pdf\|journal=IEEE/ACM Transactions on Networking\|volume=29\|pages=~~2399-2412~~\|doi=10.1109/TNET.2021.3088327}}</ref> showed that it is possible to obtain an <math>\epsilon</math>		Valls et al.<ref>{{cite journal\|last1=Valls\|first1=Victor\|last2=Iosifidis\|first2=Georgios\|last3=Tassiulas\|first3=Leandros\|date=Dec 2021\|title=Birkhoff's Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches \|url=https://arxiv.org/pdf/2011.02752.pdf\|journal=IEEE/ACM Transactions on Networking\|volume=29\|pages=2399–2412\|doi=10.1109/TNET.2021.3088327}}</ref> showed that it is possible to obtain an <math>\epsilon</math>
	-'''approximate decomposition''' with <math>O(\log(1/\epsilon^2))</math> permutations.		-'''approximate decomposition''' with <math>O(\log(1/\epsilon^2))</math> permutations.

129.41.46.2: /* Extensions */

2024-03-07T11:30:26Z

Extensions

← Previous revision		Revision as of 11:30, 7 March 2024
Line 72:		Line 72:

	== Extensions ==		== Extensions ==
	The problem of computing the Birkhoff decomposition with the '''minimum number of terms''' has been shown to be [[NP-hard]], but some heuristics for computing it are known.<ref>{{cite journal\|last1=Valls\|first1=Victor\|last2=Iosifidis\|first2=Georgios\|last3=Tassiulas\|first3=Leandros\|date=Dec 2021\|title=Birkhoff's Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches \|url=https://arxiv.org/pdf/2011.02752.pdf\|journal=IEEE/ACM Transactions on Networking\|volume=29\|pages=2399-2412\|doi=10.1109/TNET.2021.3088327}}</ref><ref>{{cite journal\|last1=Dufossé\|first1=Fanny\|last2=Uçar\|first2=Bora\|date=May 2016\|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf\|journal=Linear Algebra and Its Applications\|volume=497\|pages=108–115\|doi=10.1016/j.laa.2016.02.023\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Dufossé\|first1=Fanny\|last2=Kaya\|first2=Kamer\|last3=Panagiotas\|first3=Ioannis\|last4=Uçar\|first4=Bora\|date=2018\|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01586245/file/bvn-results.pdf\|journal=Linear Algebra and Its Applications\|volume=554\|pages=68–78\|doi=10.1016/j.laa.2018.05.017\|s2cid=240083300 \|issn=0024-3795}}</ref> This theorem can be extended for the general stochastic matrix with deterministic transition matrices.<ref>{{Cite journal\|last1=Ye\|first1=Felix X.-F.\|last2=Wang\|first2=Yue\|last3=Qian\|first3=Hong\|year=2016\|title=Stochastic dynamics: Markov chains and random transformations\|journal=Discrete and Continuous Dynamical Systems - Series B\|volume=21\|issue=7\|pages=2337–2361\|doi=10.3934/dcdsb.2016050\|doi-access=free}}</ref>		The problem of computing the Birkhoff decomposition with the '''minimum number of terms''' has been shown to be [[NP-hard]], but some heuristics for computing it are known.<ref>{{cite journal\|last1=Dufossé\|first1=Fanny\|last2=Uçar\|first2=Bora\|date=May 2016\|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf\|journal=Linear Algebra and Its Applications\|volume=497\|pages=108–115\|doi=10.1016/j.laa.2016.02.023\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Dufossé\|first1=Fanny\|last2=Kaya\|first2=Kamer\|last3=Panagiotas\|first3=Ioannis\|last4=Uçar\|first4=Bora\|date=2018\|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01586245/file/bvn-results.pdf\|journal=Linear Algebra and Its Applications\|volume=554\|pages=68–78\|doi=10.1016/j.laa.2018.05.017\|s2cid=240083300 \|issn=0024-3795}}</ref> This theorem can be extended for the general stochastic matrix with deterministic transition matrices.<ref>{{Cite journal\|last1=Ye\|first1=Felix X.-F.\|last2=Wang\|first2=Yue\|last3=Qian\|first3=Hong\|year=2016\|title=Stochastic dynamics: Markov chains and random transformations\|journal=Discrete and Continuous Dynamical Systems - Series B\|volume=21\|issue=7\|pages=2337–2361\|doi=10.3934/dcdsb.2016050\|doi-access=free}}</ref>

	Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282\|citeseerx=10.1.1.649.5582}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.		Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282\|citeseerx=10.1.1.649.5582}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.

	[[Vijay Vazirani\|Vazirani]]<ref>{{cite arXiv \|last=Vazirani \|first=Vijay V. \|date=2020-10-14 \|title=An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs \|class=cs.DS \|eprint=2010.05984 }}</ref> generalizes Birkhoff's algorithm to '''non-bipartite graphs'''.		[[Vijay Vazirani\|Vazirani]]<ref>{{cite arXiv \|last=Vazirani \|first=Vijay V. \|date=2020-10-14 \|title=An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs \|class=cs.DS \|eprint=2010.05984 }}</ref> generalizes Birkhoff's algorithm to '''non-bipartite graphs'''.

			Valls et al.<ref>{{cite journal\|last1=Valls\|first1=Victor\|last2=Iosifidis\|first2=Georgios\|last3=Tassiulas\|first3=Leandros\|date=Dec 2021\|title=Birkhoff's Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches \|url=https://arxiv.org/pdf/2011.02752.pdf\|journal=IEEE/ACM Transactions on Networking\|volume=29\|pages=2399-2412\|doi=10.1109/TNET.2021.3088327}}</ref> showed that it is possible to obtain an <math>\epsilon</math>
			-'''approximate decomposition''' with <math>O(\log(1/\epsilon^2))</math> permutations.

	== See also ==		== See also ==

129.41.46.2: /* Extensions */

2024-03-07T11:17:57Z

Extensions

← Previous revision		Revision as of 11:17, 7 March 2024
Line 72:		Line 72:

	== Extensions ==		== Extensions ==
		⚫	The problem of computing the Birkhoff decomposition with the '''minimum number of terms''' has been shown to be [[NP-hard]], but some heuristics for computing it are known.<ref>{{cite journal\|last1=Valls\|first1=Victor\|last2=Iosifidis\|first2=Georgios\|last3=Tassiulas\|first3=Leandros\|date=Dec 2021\|title=Birkhoff's Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches \|url=https://arxiv.org/pdf/2011.02752.pdf\|journal=IEEE/ACM Transactions on Networking\|volume=29\|pages=2399-2412\|doi=10.1109/TNET.2021.3088327}}</ref><ref>{{cite journal\|last1=Dufossé\|first1=Fanny\|last2=Uçar\|first2=Bora\|date=May 2016\|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf\|journal=Linear Algebra and Its Applications\|volume=497\|pages=108–115\|doi=10.1016/j.laa.2016.02.023\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Dufossé\|first1=Fanny\|last2=Kaya\|first2=Kamer\|last3=Panagiotas\|first3=Ioannis\|last4=Uçar\|first4=Bora\|date=2018\|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01586245/file/bvn-results.pdf\|journal=Linear Algebra and Its Applications\|volume=554\|pages=68–78\|doi=10.1016/j.laa.2018.05.017\|s2cid=240083300 \|issn=0024-3795}}</ref> This theorem can be extended for the general stochastic matrix with deterministic transition matrices.<ref>{{Cite journal\|last1=Ye\|first1=Felix X.-F.\|last2=Wang\|first2=Yue\|last3=Qian\|first3=Hong\|year=2016\|title=Stochastic dynamics: Markov chains and random transformations\|journal=Discrete and Continuous Dynamical Systems - Series B\|volume=21\|issue=7\|pages=2337–2361\|doi=10.3934/dcdsb.2016050\|doi-access=free}}</ref>
	The problem of computing the Birkhoff decomposition with the '''minimum number of terms''' has been shown to be [[NP-hard]], but some heuristics for computing it are known.
⚫	<ref>{{cite journal\|last1=Valls\|first1=Victor\|last2=Iosifidis\|first2=Georgios\|last3=Tassiulas\|first3=Leandros\|date=Dec 2021\|title=Birkhoff's Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches \|url=https://arxiv.org/pdf/2011.02752.pdf\|journal=IEEE/ACM Transactions on Networking\|volume=29\|pages=2399-2412\|doi=10.1109/TNET.2021.3088327}}</ref><ref>{{cite journal\|last1=Dufossé\|first1=Fanny\|last2=Uçar\|first2=Bora\|date=May 2016\|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf\|journal=Linear Algebra and Its Applications\|volume=497\|pages=108–115\|doi=10.1016/j.laa.2016.02.023\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Dufossé\|first1=Fanny\|last2=Kaya\|first2=Kamer\|last3=Panagiotas\|first3=Ioannis\|last4=Uçar\|first4=Bora\|date=2018\|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01586245/file/bvn-results.pdf\|journal=Linear Algebra and Its Applications\|volume=554\|pages=68–78\|doi=10.1016/j.laa.2018.05.017\|s2cid=240083300 \|issn=0024-3795}}</ref> This theorem can be extended for the general stochastic matrix with deterministic transition matrices.<ref>{{Cite journal\|last1=Ye\|first1=Felix X.-F.\|last2=Wang\|first2=Yue\|last3=Qian\|first3=Hong\|year=2016\|title=Stochastic dynamics: Markov chains and random transformations\|journal=Discrete and Continuous Dynamical Systems - Series B\|volume=21\|issue=7\|pages=2337–2361\|doi=10.3934/dcdsb.2016050\|doi-access=free}}</ref>

	Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282\|citeseerx=10.1.1.649.5582}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.		Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282\|citeseerx=10.1.1.649.5582}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.

129.41.46.2: /* Extensions */

2024-03-07T11:15:41Z

Extensions

← Previous revision		Revision as of 11:15, 7 March 2024
Line 72:		Line 72:

	== Extensions ==		== Extensions ==
	The problem of computing the Birkhoff decomposition with the '''minimum number of terms''' has been shown to be [[NP-hard]], but some heuristics for computing it are known.<ref>{{cite journal\|last1=Dufossé\|first1=Fanny\|last2=Uçar\|first2=Bora\|date=May 2016\|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf\|journal=Linear Algebra and Its Applications\|volume=497\|pages=108–115\|doi=10.1016/j.laa.2016.02.023\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Dufossé\|first1=Fanny\|last2=Kaya\|first2=Kamer\|last3=Panagiotas\|first3=Ioannis\|last4=Uçar\|first4=Bora\|date=2018\|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01586245/file/bvn-results.pdf\|journal=Linear Algebra and Its Applications\|volume=554\|pages=68–78\|doi=10.1016/j.laa.2018.05.017\|s2cid=240083300 \|issn=0024-3795}}</ref> This theorem can be extended for the general stochastic matrix with deterministic transition matrices.<ref>{{Cite journal\|last1=Ye\|first1=Felix X.-F.\|last2=Wang\|first2=Yue\|last3=Qian\|first3=Hong\|year=2016\|title=Stochastic dynamics: Markov chains and random transformations\|journal=Discrete and Continuous Dynamical Systems - Series B\|volume=21\|issue=7\|pages=2337–2361\|doi=10.3934/dcdsb.2016050\|doi-access=free}}</ref>		The problem of computing the Birkhoff decomposition with the '''minimum number of terms''' has been shown to be [[NP-hard]], but some heuristics for computing it are known.
			<ref>{{cite journal\|last1=Valls\|first1=Victor\|last2=Iosifidis\|first2=Georgios\|last3=Tassiulas\|first3=Leandros\|date=Dec 2021\|title=Birkhoff's Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches \|url=https://arxiv.org/pdf/2011.02752.pdf\|journal=IEEE/ACM Transactions on Networking\|volume=29\|pages=2399-2412\|doi=10.1109/TNET.2021.3088327}}</ref><ref>{{cite journal\|last1=Dufossé\|first1=Fanny\|last2=Uçar\|first2=Bora\|date=May 2016\|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf\|journal=Linear Algebra and Its Applications\|volume=497\|pages=108–115\|doi=10.1016/j.laa.2016.02.023\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Dufossé\|first1=Fanny\|last2=Kaya\|first2=Kamer\|last3=Panagiotas\|first3=Ioannis\|last4=Uçar\|first4=Bora\|date=2018\|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01586245/file/bvn-results.pdf\|journal=Linear Algebra and Its Applications\|volume=554\|pages=68–78\|doi=10.1016/j.laa.2018.05.017\|s2cid=240083300 \|issn=0024-3795}}</ref> This theorem can be extended for the general stochastic matrix with deterministic transition matrices.<ref>{{Cite journal\|last1=Ye\|first1=Felix X.-F.\|last2=Wang\|first2=Yue\|last3=Qian\|first3=Hong\|year=2016\|title=Stochastic dynamics: Markov chains and random transformations\|journal=Discrete and Continuous Dynamical Systems - Series B\|volume=21\|issue=7\|pages=2337–2361\|doi=10.3934/dcdsb.2016050\|doi-access=free}}</ref>

	Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282\|citeseerx=10.1.1.649.5582}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.		Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282\|citeseerx=10.1.1.649.5582}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.

Sir Ibee: Open access status updates in citations with OAbot #oabot

2024-01-11T06:37:40Z

Open access status updates in citations with OAbot #oabot

← Previous revision		Revision as of 06:37, 11 January 2024
Line 74:		Line 74:
	The problem of computing the Birkhoff decomposition with the '''minimum number of terms''' has been shown to be [[NP-hard]], but some heuristics for computing it are known.<ref>{{cite journal\|last1=Dufossé\|first1=Fanny\|last2=Uçar\|first2=Bora\|date=May 2016\|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf\|journal=Linear Algebra and Its Applications\|volume=497\|pages=108–115\|doi=10.1016/j.laa.2016.02.023\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Dufossé\|first1=Fanny\|last2=Kaya\|first2=Kamer\|last3=Panagiotas\|first3=Ioannis\|last4=Uçar\|first4=Bora\|date=2018\|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01586245/file/bvn-results.pdf\|journal=Linear Algebra and Its Applications\|volume=554\|pages=68–78\|doi=10.1016/j.laa.2018.05.017\|s2cid=240083300 \|issn=0024-3795}}</ref> This theorem can be extended for the general stochastic matrix with deterministic transition matrices.<ref>{{Cite journal\|last1=Ye\|first1=Felix X.-F.\|last2=Wang\|first2=Yue\|last3=Qian\|first3=Hong\|year=2016\|title=Stochastic dynamics: Markov chains and random transformations\|journal=Discrete and Continuous Dynamical Systems - Series B\|volume=21\|issue=7\|pages=2337–2361\|doi=10.3934/dcdsb.2016050\|doi-access=free}}</ref>		The problem of computing the Birkhoff decomposition with the '''minimum number of terms''' has been shown to be [[NP-hard]], but some heuristics for computing it are known.<ref>{{cite journal\|last1=Dufossé\|first1=Fanny\|last2=Uçar\|first2=Bora\|date=May 2016\|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf\|journal=Linear Algebra and Its Applications\|volume=497\|pages=108–115\|doi=10.1016/j.laa.2016.02.023\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Dufossé\|first1=Fanny\|last2=Kaya\|first2=Kamer\|last3=Panagiotas\|first3=Ioannis\|last4=Uçar\|first4=Bora\|date=2018\|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01586245/file/bvn-results.pdf\|journal=Linear Algebra and Its Applications\|volume=554\|pages=68–78\|doi=10.1016/j.laa.2018.05.017\|s2cid=240083300 \|issn=0024-3795}}</ref> This theorem can be extended for the general stochastic matrix with deterministic transition matrices.<ref>{{Cite journal\|last1=Ye\|first1=Felix X.-F.\|last2=Wang\|first2=Yue\|last3=Qian\|first3=Hong\|year=2016\|title=Stochastic dynamics: Markov chains and random transformations\|journal=Discrete and Continuous Dynamical Systems - Series B\|volume=21\|issue=7\|pages=2337–2361\|doi=10.3934/dcdsb.2016050\|doi-access=free}}</ref>

	Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.		Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282\|citeseerx=10.1.1.649.5582}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.

	[[Vijay Vazirani\|Vazirani]]<ref>{{cite arXiv \|last=Vazirani \|first=Vijay V. \|date=2020-10-14 \|title=An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs \|class=cs.DS \|eprint=2010.05984 }}</ref> generalizes Birkhoff's algorithm to '''non-bipartite graphs'''.		[[Vijay Vazirani\|Vazirani]]<ref>{{cite arXiv \|last=Vazirani \|first=Vijay V. \|date=2020-10-14 \|title=An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs \|class=cs.DS \|eprint=2010.05984 }}</ref> generalizes Birkhoff's algorithm to '''non-bipartite graphs'''.

2603:6011:2DF0:2340:5015:571E:848F:5DC9: /* Tools */

2023-10-10T18:09:18Z

Tools

← Previous revision		Revision as of 18:09, 10 October 2023
Line 45:		Line 45:

	== Tools ==		== Tools ==
	A '''permutation set''' of an ''n''-by-''n'' matrix ''X'' is a set of ''n'' entries of ''X'' containing exactly one entry from each row and from each column. A theorem by [[Dénes Kőnig]] says that:<ref>{{citation\|last=Kőnig\|first=Dénes\|title=Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére\|journal=Matematikai és Természettudományi Értesítő\|volume=34\|pages=104–119\|year=1916\|authorlink=Dénes Kőnig}}.</ref><ref name="lp" />{{rp\|35}} <blockquote>''Every bistochastic matrix has a permutation-set in which all entries are positive.''</blockquote>The '''positivity graph''' of an ''n''-by-''n'' matrix ''X'' is a [[bipartite graph]] with 2''n'' vertices, in which the vertices on one side are ''n'' rows and the vertices on the other side are the ''n'' columns, and there is an edge between a row and a column iff the entry at that row and column is positive. A permutation set with positive entries is equivalent to a [[perfect matching]] in the positivity graph. A perfect matching in a bipartite graph can be found in polynomial time, e.g. using any algorithm for [[maximum cardinality matching]]. [[Dénes Kőnig\|Kőnig]]'s theorem is equivalent to the following:<blockquote>''The positivity graph of any bistochastic matrix admits a perfect matching.''</blockquote>A matrix is called '''scaled-bistochastic''' if all elements are ~~weakly~~-~~positive~~, and the sum of each row and column equals ''c'', where ''c'' is some positive constant. In other words, it is ''c'' times a bistochastic matrix. Since the positivity graph is not affected by scaling:<blockquote>''The positivity graph of any scaled-bistochastic matrix admits a perfect matching.''</blockquote>		A '''permutation set''' of an ''n''-by-''n'' matrix ''X'' is a set of ''n'' entries of ''X'' containing exactly one entry from each row and from each column. A theorem by [[Dénes Kőnig]] says that:<ref>{{citation\|last=Kőnig\|first=Dénes\|title=Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére\|journal=Matematikai és Természettudományi Értesítő\|volume=34\|pages=104–119\|year=1916\|authorlink=Dénes Kőnig}}.</ref><ref name="lp" />{{rp\|35}} <blockquote>''Every bistochastic matrix has a permutation-set in which all entries are positive.''</blockquote>The '''positivity graph''' of an ''n''-by-''n'' matrix ''X'' is a [[bipartite graph]] with 2''n'' vertices, in which the vertices on one side are ''n'' rows and the vertices on the other side are the ''n'' columns, and there is an edge between a row and a column iff the entry at that row and column is positive. A permutation set with positive entries is equivalent to a [[perfect matching]] in the positivity graph. A perfect matching in a bipartite graph can be found in polynomial time, e.g. using any algorithm for [[maximum cardinality matching]]. [[Dénes Kőnig\|Kőnig]]'s theorem is equivalent to the following:<blockquote>''The positivity graph of any bistochastic matrix admits a perfect matching.''</blockquote>A matrix is called '''scaled-bistochastic''' if all elements are non-negative, and the sum of each row and column equals ''c'', where ''c'' is some positive constant. In other words, it is ''c'' times a bistochastic matrix. Since the positivity graph is not affected by scaling:<blockquote>''The positivity graph of any scaled-bistochastic matrix admits a perfect matching.''</blockquote>

	== Algorithm ==		== Algorithm ==

Graeme Bartlett: space ; coefficienct fix

2023-01-20T05:03:14Z

space ; coefficienct fix

← Previous revision		Revision as of 05:03, 20 January 2023
Line 67:		Line 67:

	== Application in fair division ==		== Application in fair division ==
	In the [[fair random assignment]] problem, there are ''n'' objects and ''n'' people with different preferences over the objects. It is required to give an object to each person. To attain fairness, the allocation is randomized: for each (person,object) pair, a probability is calculated, such that the sum of probabilities for each person and for each object is 1. The [[probabilistic-serial procedure]] can compute the probabilities such that each agent, looking at the matrix of probabilities, prefers his row of probabilities over the rows of all other people (this property is called [[envy-freeness]]). This raises the question of how to implement this randomized allocation in practice? One cannot just randomize for each object separately, since this may result in allocations in which some people get many objects while other people get no objects.		In the [[fair random assignment]] problem, there are ''n'' objects and ''n'' people with different preferences over the objects. It is required to give an object to each person. To attain fairness, the allocation is randomized: for each (person, object) pair, a probability is calculated, such that the sum of probabilities for each person and for each object is 1. The [[probabilistic-serial procedure]] can compute the probabilities such that each agent, looking at the matrix of probabilities, prefers his row of probabilities over the rows of all other people (this property is called [[envy-freeness]]). This raises the question of how to implement this randomized allocation in practice? One cannot just randomize for each object separately, since this may result in allocations in which some people get many objects while other people get no objects.

	Here, Birkhoff's algorithm is useful. The matrix of probabilities, calculated by the probabilistic-serial algorithm, is bistochastic. Birkhoff's algorithm can decompose it into a convex combination of permutation matrices. Each permutation matrix represents a deterministic assignment, in which every agent receives exactly one object. The ~~coefficienct~~ of each such matrix is interpreted as a probability; based on the calculated probabilities, it is possible to pick one assignment at random and implement it.		Here, Birkhoff's algorithm is useful. The matrix of probabilities, calculated by the probabilistic-serial algorithm, is bistochastic. Birkhoff's algorithm can decompose it into a convex combination of permutation matrices. Each permutation matrix represents a deterministic assignment, in which every agent receives exactly one object. The coefficient of each such matrix is interpreted as a probability; based on the calculated probabilities, it is possible to pick one assignment at random and implement it.

	== Extensions ==		== Extensions ==

Citation bot: Alter: template type. Add: eprint, class, s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 4/24

2022-09-26T04:20:19Z

Alter: template type. Add: eprint, class, s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 4/24

← Previous revision		Revision as of 04:20, 26 September 2022
Line 72:		Line 72:

	== Extensions ==		== Extensions ==
	The problem of computing the Birkhoff decomposition with the '''minimum number of terms''' has been shown to be [[NP-hard]], but some heuristics for computing it are known.<ref>{{cite journal\|last1=Dufossé\|first1=Fanny\|last2=Uçar\|first2=Bora\|date=May 2016\|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf\|journal=Linear Algebra and Its Applications\|volume=497\|pages=108–115\|doi=10.1016/j.laa.2016.02.023\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Dufossé\|first1=Fanny\|last2=Kaya\|first2=Kamer\|last3=Panagiotas\|first3=Ioannis\|last4=Uçar\|first4=Bora\|date=2018\|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01586245/file/bvn-results.pdf\|journal=Linear Algebra and Its Applications\|volume=554\|pages=68–78\|doi=10.1016/j.laa.2018.05.017\|issn=0024-3795}}</ref> This theorem can be extended for the general stochastic matrix with deterministic transition matrices.<ref>{{Cite journal\|last1=Ye\|first1=Felix X.-F.\|last2=Wang\|first2=Yue\|last3=Qian\|first3=Hong\|year=2016\|title=Stochastic dynamics: Markov chains and random transformations\|journal=Discrete and Continuous Dynamical Systems - Series B\|volume=21\|issue=7\|pages=2337–2361\|doi=10.3934/dcdsb.2016050\|doi-access=free}}</ref>		The problem of computing the Birkhoff decomposition with the '''minimum number of terms''' has been shown to be [[NP-hard]], but some heuristics for computing it are known.<ref>{{cite journal\|last1=Dufossé\|first1=Fanny\|last2=Uçar\|first2=Bora\|date=May 2016\|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf\|journal=Linear Algebra and Its Applications\|volume=497\|pages=108–115\|doi=10.1016/j.laa.2016.02.023\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Dufossé\|first1=Fanny\|last2=Kaya\|first2=Kamer\|last3=Panagiotas\|first3=Ioannis\|last4=Uçar\|first4=Bora\|date=2018\|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01586245/file/bvn-results.pdf\|journal=Linear Algebra and Its Applications\|volume=554\|pages=68–78\|doi=10.1016/j.laa.2018.05.017\|s2cid=240083300 \|issn=0024-3795}}</ref> This theorem can be extended for the general stochastic matrix with deterministic transition matrices.<ref>{{Cite journal\|last1=Ye\|first1=Felix X.-F.\|last2=Wang\|first2=Yue\|last3=Qian\|first3=Hong\|year=2016\|title=Stochastic dynamics: Markov chains and random transformations\|journal=Discrete and Continuous Dynamical Systems - Series B\|volume=21\|issue=7\|pages=2337–2361\|doi=10.3934/dcdsb.2016050\|doi-access=free}}</ref>

	Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|~~last~~=Budish\|~~first~~=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.		Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.

	[[Vijay Vazirani\|Vazirani]]<ref>{{cite ~~arxiv~~ \|last=Vazirani \|first=Vijay V. \|date=2020-10-14 \|title=An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs \|~~arxiv~~=2010.05984 }}</ref> generalizes Birkhoff's algorithm to '''non-bipartite graphs'''.		[[Vijay Vazirani\|Vazirani]]<ref>{{cite arXiv \|last=Vazirani \|first=Vijay V. \|date=2020-10-14 \|title=An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs \|class=cs.DS \|eprint=2010.05984 }}</ref> generalizes Birkhoff's algorithm to '''non-bipartite graphs'''.

	== See also ==		== See also ==

Headbomb: /* Extensions */Various citation & identifier cleanup, plus AWB genfixes (arxiv version pointless when published)

2022-09-26T04:02:15Z

Extensions: Various citation & identifier cleanup, plus AWB genfixes (arxiv version pointless when published)

← Previous revision		Revision as of 04:02, 26 September 2022
Line 76:		Line 76:
	Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last=Budish\|first=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.		Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last=Budish\|first=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.

	[[Vijay Vazirani\|Vazirani]]<ref>{{~~Cite~~ ~~journal~~ \|last=Vazirani \|first=Vijay V. \|date=2020-10-14 \|title=An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs \|~~url=http://~~arxiv~~.org/abs/2010.05984 \|journal~~=~~arXiv:~~2010.05984 ~~[cs, econ]~~}}</ref> generalizes Birkhoff's algorithm to '''non-bipartite graphs'''.		[[Vijay Vazirani\|Vazirani]]<ref>{{cite arxiv \|last=Vazirani \|first=Vijay V. \|date=2020-10-14 \|title=An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs \|arxiv=2010.05984 }}</ref> generalizes Birkhoff's algorithm to '''non-bipartite graphs'''.

	== See also ==		== See also ==

← Previous revision		Revision as of 06:37, 11 January 2024
Line 74:		Line 74:
	The problem of computing the Birkhoff decomposition with the '''minimum number of terms''' has been shown to be [[NP-hard]], but some heuristics for computing it are known.<ref>{{cite journal\|last1=Dufossé\|first1=Fanny\|last2=Uçar\|first2=Bora\|date=May 2016\|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf\|journal=Linear Algebra and Its Applications\|volume=497\|pages=108–115\|doi=10.1016/j.laa.2016.02.023\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Dufossé\|first1=Fanny\|last2=Kaya\|first2=Kamer\|last3=Panagiotas\|first3=Ioannis\|last4=Uçar\|first4=Bora\|date=2018\|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01586245/file/bvn-results.pdf\|journal=Linear Algebra and Its Applications\|volume=554\|pages=68–78\|doi=10.1016/j.laa.2018.05.017\|s2cid=240083300 \|issn=0024-3795}}</ref> This theorem can be extended for the general stochastic matrix with deterministic transition matrices.<ref>{{Cite journal\|last1=Ye\|first1=Felix X.-F.\|last2=Wang\|first2=Yue\|last3=Qian\|first3=Hong\|year=2016\|title=Stochastic dynamics: Markov chains and random transformations\|journal=Discrete and Continuous Dynamical Systems - Series B\|volume=21\|issue=7\|pages=2337–2361\|doi=10.3934/dcdsb.2016050\|doi-access=free}}</ref>		The problem of computing the Birkhoff decomposition with the '''minimum number of terms''' has been shown to be [[NP-hard]], but some heuristics for computing it are known.<ref>{{cite journal\|last1=Dufossé\|first1=Fanny\|last2=Uçar\|first2=Bora\|date=May 2016\|title=Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf\|journal=Linear Algebra and Its Applications\|volume=497\|pages=108–115\|doi=10.1016/j.laa.2016.02.023\|doi-access=free}}</ref><ref>{{Cite journal\|last1=Dufossé\|first1=Fanny\|last2=Kaya\|first2=Kamer\|last3=Panagiotas\|first3=Ioannis\|last4=Uçar\|first4=Bora\|date=2018\|title=Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices\|url=https://hal.inria.fr/hal-01586245/file/bvn-results.pdf\|journal=Linear Algebra and Its Applications\|volume=554\|pages=68–78\|doi=10.1016/j.laa.2018.05.017\|s2cid=240083300 \|issn=0024-3795}}</ref> This theorem can be extended for the general stochastic matrix with deterministic transition matrices.<ref>{{Cite journal\|last1=Ye\|first1=Felix X.-F.\|last2=Wang\|first2=Yue\|last3=Qian\|first3=Hong\|year=2016\|title=Stochastic dynamics: Markov chains and random transformations\|journal=Discrete and Continuous Dynamical Systems - Series B\|volume=21\|issue=7\|pages=2337–2361\|doi=10.3934/dcdsb.2016050\|doi-access=free}}</ref>

	Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.		Budish, Che, Kojima and Milgrom<ref name=":12">{{Cite journal\|last1=Budish\|first1=Eric\|last2=Che\|first2=Yeon-Koo\|last3=Kojima\|first3=Fuhito\|last4=Milgrom\|first4=Paul\|date=2013-04-01\|title=Designing Random Allocation Mechanisms: Theory and Applications\|url=https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585\|journal=American Economic Review\|language=en\|volume=103\|issue=2\|pages=585–623\|doi=10.1257/aer.103.2.585\|issn=0002-8282\|citeseerx=10.1.1.649.5582}}</ref> generalize Birkhoff's algorithm to '''non-square matrices''', with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values.

	[[Vijay Vazirani\|Vazirani]]<ref>{{cite arXiv \|last=Vazirani \|first=Vijay V. \|date=2020-10-14 \|title=An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs \|class=cs.DS \|eprint=2010.05984 }}</ref> generalizes Birkhoff's algorithm to '''non-bipartite graphs'''.		[[Vijay Vazirani\|Vazirani]]<ref>{{cite arXiv \|last=Vazirani \|first=Vijay V. \|date=2020-10-14 \|title=An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs \|class=cs.DS \|eprint=2010.05984 }}</ref> generalizes Birkhoff's algorithm to '''non-bipartite graphs'''.