CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

The Blind Passenger and the Assignment Problem

Johan Wästlund (Institutionen för matematiska vetenskaper, matematik)
Combinatorics Probability & Computing (0963-5483). Vol. 20 (2011), 3, p. 467-480.
[Artikel, refereegranskad vetenskaplig]

We introduce a discrete random process which we call the passenger model, and show that it is connected to a certain random model of the assignment problem and in particular to the so-called Buck-Chan-Robbins urn process. We propose a conjecture on the distribution of the location of the minimum cost assignment in a cost matrix with zeros at specified positions and remaining entries of exponential distribution. The conjecture is consistent with earlier results on the participation probability of an individual matrix entry. We also use the passenger model to verify a conjecture by V. Dotsenko on the assignment problem.

Nyckelord: traveling salesman, minimum assignment, expected value, zeta(2) limit, proof, conjecture

Denna post skapades 2011-04-21. Senast ändrad 2013-04-03.
CPL Pubid: 139685


Läs direkt!

Lokal fulltext (fritt tillgänglig)

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)


Tillämpad matematik

Chalmers infrastruktur