Αλγόριθμος του Μπίρκοφ

Ο αλγόριθμος του Μπίρκοφ (επίσης γνωστός ως αλγόριθμος Μπίρκοφ-φον Νόιμαν) είναι ένας αλγόριθμος για τη διάσπαση ενός διστοχαστικού πίνακα σε έναν κυρτό συνδυασμό πινάκων μετατροπής. Δημοσιεύθηκε από τον Γκάρετ Μπίρκοφ το 1946^[1]^[2]^:36 Έχει πολλές εφαρμογές. Μια τέτοια εφαρμογή είναι για το πρόβλημα της δίκαιης τυχαίας κατανομής: δεδομένης μιας τυχαίας κατανομής αντικειμένων, ο αλγόριθμος του Μπίρκοφ μπορεί να την αποσυνθέσει σε μια κλήρωση σε προσδιοριστικές αναθέσεις.

Ορολογία

Ένας διστοχαστικός πίνακας (που ονομάζεται επίσης: διπλά-στοχαστικός) είναι ένας πίνακας στον οποίο όλα τα στοιχεία είναι μεγαλύτερα ή ίσα του 0 και το άθροισμα των στοιχείων σε κάθε γραμμή και στήλη ισούται με 1. Ένα παράδειγμα είναι ο ακόλουθος πίνακας 3 επί 3:

${\begin{pmatrix}0.2&0.3&0.5\\0.6&0.2&0.2\\0.2&0.5&0.3\end{pmatrix}}$

Ένας πίνακας μεταθέσεων είναι μια ειδική περίπτωση ενός διστοχαστικού πίνακα, στον οποίο κάθε στοιχείο είναι είτε 0 είτε 1 (έτσι υπάρχει ακριβώς ένα «1» σε κάθε γραμμή και κάθε στήλη). Ένα παράδειγμα είναι ο ακόλουθος πίνακας 3 επί 3:

${\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}$

Μια παραγοντοποιήση Μπίρκοφ (επίσης αποκαλούμενη: παραγοντοποίηση Μπίρκοφ-φον Νόιμαν) ενός διστοχαστικού πίνακα είναι η παρουσίασή του ως άθροισμα πινάκων μετατροπής με μη αρνητικά βάρη. Παραδείγματος χάριν, ο παραπάνω πίνακας μπορεί να παρουσιαστεί ως το ακόλουθο άθροισμα:

$0.2{\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}+0.2{\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}+0.1{\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}+0.5{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}$

Ο αλγόριθμος του Μπίρκοφ λαμβάνει ως είσοδο έναν διστοχαστικό πίνακα και επιστρέφει ως έξοδο μια παραγοντοποιήση Μπίρκοφ.

Εργαλεία

Ένα σύνολο αντιμετάθεσης ενός n-προς-n πίνακα X είναι ένα σύνολο n καταχωρήσεων του X που περιέχει ακριβώς μία καταχώρηση από κάθε γραμμή και από κάθε στήλη. Ένα θεώρημα του Ντένες Κνούνιγκ αναφέρει ότι: ^[3]^[2]^:35

Κάθε διστοχαστικός πίνακας έχει ένα σύνολο μεταθέσεων στο οποίο όλες οι καταχωρήσεις είναι θετικές.

Το γράφημα θετικότητας ενός πίνακα n-προς-n X είναι ένα διμερές γράφημα με 2 n κορυφές, στο οποίο οι κορυφές από τη μία πλευρά είναι οι n γραμμές και οι κορυφές από την άλλη πλευρά είναι οι n στήλες, και υπάρχει ακμή μεταξύ μιας γραμμής και μιας στήλης αν η είσοδος σε αυτή τη γραμμή και τη στήλη είναι θετική. Ένα σύνολο μεταθέσεων με θετικές καταχωρήσεις είναι ισοδύναμο με ένα τέλειο ταίριασμα στο γράφημα θετικότητας. Ένα τέλειο ταίριασμα σε ένα διμερές γράφημα μπορεί να βρεθεί σε πολυωνυμικό χρόνο, π.χ. με τη χρήση οποιουδήποτε αλγορίθμου για ταίριασμα μέγιστης πληθικότητας. Το θεώρημα του Κνούνιγκ είναι ισοδύναμο με το ακόλουθο:

Το γράφημα θετικότητας οποιουδήποτε διστοχαστικού πίνακα επιτρέπει ένα τέλειο ταίριασμα.

Ένας πίνακας ονομάζεται κλιμακωτός-διστοχαστικός αν όλα τα στοιχεία είναι μη αρνητικά και το άθροισμα κάθε γραμμής και στήλης ισούται με c, όπου c είναι κάποια θετική σταθερά. Με άλλα λόγια, είναι c επί ένα διστοχαστικό πίνακα. Δεδομένου ότι το γράφημα θετικότητας δεν επηρεάζεται από την κλιμάκωση:

Το γράφημα θετικότητας οποιουδήποτε κλιμακωτού-διστοχωστικού πίνακα επιτρέπει ένα τέλειο ταίριασμα.

Αλγόριθμος

Ο αλγόριθμος του Μπίρκοφ είναι ένας άπληστος αλγόριθμος^[4]: βρίσκει άπληστα τις τέλειες αντιστοιχίες και τις αφαιρεί από την κλασματική αντιστοιχία. Λειτουργεί ως εξής.^[5]^:app.B

Έστω i = 1.
Σχεδιάστε το γράφημα θετικότητας G_X of X.
Βρείτε ένα τέλειο ταίριασμα στο G_X, που αντιστοιχεί σε ένα θετικό σύνολο μεταθέσεων στο X.
Έστω z[i] > 0 η μικρότερη καταχώρηση στο σύνολο μεταθέσεων.
Έστω P[i] ένας πίνακας μεταθέσεων με 1 στο θετικό σύνολο μεταθέσεων.
Έστω X := X − z[i] P[i].
Αν το X περιέχει μη μηδενικά στοιχεία, αφήστε i = i + 1 και επιστρέψτε στο βήμα 2.
Διαφορετικά, επιστρέψτε το άθροισμα: z[1] P[1] + ... + z[2] P[2] + ... + z[i] P[i].

Ο αλγόριθμος είναι σωστός διότι, μετά το βήμα 6, το άθροισμα σε κάθε γραμμή και κάθε στήλη μειώνεται κατά z[i]. Επομένως, ο πίνακας X παραμένει κλιμακωτός-πιστοχαστικός. Επομένως, στο βήμα 3, υπάρχει πάντα μια τέλεια αντιστοίχιση.

Πολυπλοκότητα χρόνου εκτέλεσης

Με την επιλογή του z[i] στο βήμα 4, σε κάθε επανάληψη τουλάχιστον ένα στοιχείο του X γίνεται 0. Επομένως, ο αλγόριθμος πρέπει να τελειώσει μετά από το πολύ n² βήματα. Ωστόσο, το τελευταίο βήμα πρέπει ταυτόχρονα να κάνει n στοιχεία 0, οπότε ο αλγόριθμος τελειώνει μετά από το πολύ n² − n + 1 βήματα, το οποίο συνεπάγεται $O(n^{2})$

Το 1960, οι Τζόσνσον, Ντουλμάζ και Μέντελσον έδειξαν ότι ο αλγόριθμος του Μπίρκοφ τελειώνει στην πραγματικότητα μετά από το πολύ n² − 2n + 2 βήματα, το οποίο είναι σφιχτό σε γενικές γραμμές (δηλαδή, σε ορισμένες περιπτώσεις μπορεί να απαιτούνται n² − 2n + 2 πίνακες μεταθέσεων)^[6].

Εφαρμογή στη δίκαιη κατανομή

Στο πρόβλημα της δίκαιης τυχαίας κατανομής, υπάρχουν n αντικείμενα και n άτομα με διαφορετικές προτιμήσεις για τα αντικείμενα. Απαιτείται να δοθεί ένα αντικείμενο σε κάθε άτομο. Για να επιτευχθεί η δίκαιη κατανομή, η κατανομή είναι τυχαία: για κάθε ζεύγος (άτομο, αντικείμενο) υπολογίζεται μια πιθανότητα, έτσι ώστε το άθροισμα των πιθανοτήτων για κάθε άτομο και για κάθε αντικείμενο να είναι 1. Η πιθανολογική-σειριακή διαδικασία μπορεί να υπολογίσει τις πιθανότητες έτσι ώστε κάθε πράκτορας, κοιτάζοντας τον πίνακα των πιθανοτήτων, να προτιμά τη σειρά των πιθανοτήτων του από τις σειρές όλων των άλλων ατόμων (αυτή η ιδιότητα ονομάζεται ζηλευτή-ευγένεια). Αυτό εγείρει το ερώτημα πώς μπορεί να εφαρμοστεί αυτή η τυχαιοποιημένη κατανομή στην πράξη; Δεν είναι δυνατόν να γίνει τυχαία κατανομή κάθε αντικειμένου ξεχωριστά, καθώς αυτό θα μπορούσε να οδηγήσει σε κατανομές στις οποίες κάποιοι άνθρωποι παίρνουν πολλά αντικείμενα ενώ άλλοι κανένα.

Εδώ είναι χρήσιμος ο αλγόριθμος του Μπίρκοφ. Ο πίνακας πιθανοτήτων, που υπολογίζεται από τον αλγόριθμο πιθανοτήτων-σειρών, είναι διστοχαστικός. Ο αλγόριθμος του Μπίρκοφ μπορεί να τον αποσυνθέσει σε έναν κυρτό συνδυασμό πινάκων μεταθέσεων. Κάθε πίνακας μεταθέσεων αντιπροσωπεύει μια προσδιοριστική κατανομή, στην οποία κάθε πράκτορας λαμβάνει ακριβώς ένα αντικείμενο. Ο συντελεστής κάθε τέτοιου πίνακα ερμηνεύεται ως πιθανότητα- με βάση τις υπολογισμένες πιθανότητες, είναι δυνατόν να επιλεγεί μια τυχαία ανάθεση και να υλοποιηθεί.

Επεκτάσεις

Το πρόβλημα του υπολογισμού της παραγοντοποιήσης Μπίρκοφ με τον ελάχιστο αριθμό όρων έχει αποδειχθεί ότι είναι NP-δύσκολο, αλλά είναι γνωστές κάποιες ευρετικές τεχνικές για τον υπολογισμό του^[7]^[8] Το θεώρημα αυτό μπορεί να επεκταθεί για τον γενικό στοχαστικό πίνακα με προσδιοριστικούς πίνακες μετάβασης^[9].

Οι Μπουντίς, Τσε, Κοτζίμα και Μίλγκρομ^[10] γενικεύουν τον αλγόριθμο του Μπίρκοφ σε μη τετραγωνικούς πίνακες, με ορισμένους περιορισμούς στις εφικτές αναθέσεις. Παρουσιάζουν επίσης έναν αλγόριθμο αποσύνθεσης που ελαχιστοποιεί τη διακύμανση των αναμενόμενων τιμών.

Ο Βαζιράνι^[11] γενικεύει τον αλγόριθμο του Μπίρκοφ σε μη διμερή γραφήματα.

Οι Βάλς κ.ά.^[12] έδειξαν ότι είναι δυνατόν να ληφθεί ένα $\epsilon$ -προσεγγιστική παραγοντοποιήση με $O(\log(1/\epsilon ^{2}))$ μεταθέσεις.

Δημοσιεύσεις

Μαυρογιάννης, Ν. Σ. (Μαΐου 2016). «Μία εισαγωγή στους μιγαδικούς αριθμούς». Εκθέτης Φύλλα Μαθηματικής Παιδείας (16): 1-8. http://ekthetis.gr/Ekthetis016.pdf.
Bronshtein, I. N.· Semendyayev, K. A. (29 Ιουνίου 2013). Handbook of Mathematics. Springer Science & Business Media. ISBN 978-3-662-21982-9.
Belevitch V (1950). «Theory of 2n-terminal networks with applications to conference telephony». Electrical Communication 27: 231–244.
Goethals J.M., Seidel J.J. (1967). «Orthogonal matrices with zero diagonal». Canadian Journal of Mathematics 19: 1001–1010. doi:10.4153/cjm-1967-091-8. https://archive.org/details/sim_canadian-journal-of-mathematics_1967_19_5/page/1001.
Wilson, Robin (2018). Euler's Pioneering Equation: The Most Beautiful Theorem in Mathematics. Oxford: Oxford University Press. ISBN 978-0-19-879492-9. MR 3791469.
Damask, Jay N. (2004). Polarization Optics in Telecommunications. Springer. ISBN 0-387-22493-9.
Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. 108. Cambridge: Cambridge University Press. ISBN 0-521-86565-4. Zbl 1106.05001.
Joseph, Najnudel; Ashkan, Nikeghbali (2010), The Distribution of Eigenvalues of Randomized Permutation Matrices
Hardy, G. H.· Wright, E. M. (1979). An Introduction to the Theory of Numbers (Fifth έκδοση). Oxford: Oxford University Press. ISBN 978-0-19-853171-5.
Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd έκδοση). Lexington: D. C. Heath and Company. LCCN 77171950.

Δείτε επίσης

Εξωτερικοί σύνδεσμοι

Παραπομπές

↑ Birkhoff, Garrett (1946), «Tres observaciones sobre el algebra lineal [Three observations on linear algebra]», Univ. Nac. Tucumán. Revista A. 5: 147–151 .
1 2 Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
↑ Kőnig, Dénes (1916), «Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére», Matematikai és Természettudományi Értesítő 34: 104–119 .
↑ «Άπληστοι αλγόριθμοι (Greedy Algorithms) - Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών» (PDF).
↑ Aziz, Haris (2020). «Simultaneously Achieving Ex-ante and Ex-post Fairness».
arXiv:2004.02554
[cs.GT]
.
↑ Johnson, Diane M.; Dulmage, A. L.; Mendelsohn, N. S. (1960-09-01). «On an Algorithm of G. Birkhoff Concerning Doubly Stochastic Matrices». Canadian Mathematical Bulletin 3 (3): 237–242. doi:10.4153/cmb-1960-029-5. ISSN 0008-4395.
↑ Dufossé, Fanny; Uçar, Bora (May 2016). «Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices». Linear Algebra and Its Applications 497: 108–115. doi:10.1016/j.laa.2016.02.023. https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf.
↑ Dufossé, Fanny; Kaya, Kamer; Panagiotas, Ioannis; Uçar, Bora (2018). «Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices». Linear Algebra and Its Applications 554: 68–78. doi:10.1016/j.laa.2018.05.017. ISSN 0024-3795. https://hal.inria.fr/hal-01586245/file/bvn-results.pdf.
↑ Ye, Felix X.-F.; Wang, Yue; Qian, Hong (2016). «Stochastic dynamics: Markov chains and random transformations». Discrete and Continuous Dynamical Systems - Series B 21 (7): 2337–2361. doi:10.3934/dcdsb.2016050.
↑ Budish, Eric; Che, Yeon-Koo; Kojima, Fuhito; Milgrom, Paul (2013-04-01). «Designing Random Allocation Mechanisms: Theory and Applications» (στα αγγλικά). American Economic Review 103 (2): 585–623. doi:10.1257/aer.103.2.585. ISSN 0002-8282. https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585.
↑ Vazirani, Vijay V. (2020-10-14). «An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs».
arXiv:2010.05984
[cs.DS]
.
↑ Valls, Victor; Iosifidis, Georgios; Tassiulas, Leandros (Dec 2021). «Birkhoff's Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches». IEEE/ACM Transactions on Networking 29: 2399–2412. doi:10.1109/TNET.2021.3088327. https://arxiv.org/pdf/2011.02752.pdf.

[1] Birkhoff, Garrett (1946), «Tres observaciones sobre el algebra lineal [Three observations on linear algebra]», Univ. Nac. Tucumán. Revista A. 5: 147–151 .

[lp-2] 1 2 Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549

[3] Kőnig, Dénes (1916), «Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére», Matematikai és Természettudományi Értesítő 34: 104–119 .

[4] «Άπληστοι αλγόριθμοι (Greedy Algorithms) - Εθνικόν και Καποδιστριακόν Πανεπιστήμιον Αθηνών» (PDF).

[aziz20-5] Aziz, Haris (2020). «Simultaneously Achieving Ex-ante and Ex-post Fairness».
arXiv:2004.02554
[cs.GT]
.

[6] Johnson, Diane M.; Dulmage, A. L.; Mendelsohn, N. S. (1960-09-01). «On an Algorithm of G. Birkhoff Concerning Doubly Stochastic Matrices». Canadian Mathematical Bulletin 3 (3): 237–242. doi:10.4153/cmb-1960-029-5. ISSN 0008-4395.

[7] Dufossé, Fanny; Uçar, Bora (May 2016). «Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices». Linear Algebra and Its Applications 497: 108–115. doi:10.1016/j.laa.2016.02.023. https://hal.inria.fr/hal-01270331/file/bvn-laa.pdf.

[8] Dufossé, Fanny; Kaya, Kamer; Panagiotas, Ioannis; Uçar, Bora (2018). «Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices». Linear Algebra and Its Applications 554: 68–78. doi:10.1016/j.laa.2018.05.017. ISSN 0024-3795. https://hal.inria.fr/hal-01586245/file/bvn-results.pdf.

[9] Ye, Felix X.-F.; Wang, Yue; Qian, Hong (2016). «Stochastic dynamics: Markov chains and random transformations». Discrete and Continuous Dynamical Systems - Series B 21 (7): 2337–2361. doi:10.3934/dcdsb.2016050.

[:12-10] Budish, Eric; Che, Yeon-Koo; Kojima, Fuhito; Milgrom, Paul (2013-04-01). «Designing Random Allocation Mechanisms: Theory and Applications» (στα αγγλικά). American Economic Review 103 (2): 585–623. doi:10.1257/aer.103.2.585. ISSN 0002-8282. https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585.

[11] Vazirani, Vijay V. (2020-10-14). «An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs».
arXiv:2010.05984
[cs.DS]
.

[12] Valls, Victor; Iosifidis, Georgios; Tassiulas, Leandros (Dec 2021). «Birkhoff's Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches». IEEE/ACM Transactions on Networking 29: 2399–2412. doi:10.1109/TNET.2021.3088327. https://arxiv.org/pdf/2011.02752.pdf.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]