In 2007 Babaioff, Immorlica, and Kleinberg formulated the matroid secretary problem, elegantly tying together the field of matroid theory with generalizations of the secretary problem. In this thesis, we introduce the reader to matroids and the secretary problem, before diving into Babaioff et al's definition and a survey of recent results. We then focus on the important special case of the transversal matroid secretary problem. We formulate a previously undefined class of transversal matroids and give a constant competitive algorithm for them. We also provide the tightest known analysis of Plaxton and Dimitrov's recent 2008 algorithm for the transversal matroid secretary problem and thereby give the tightest known competitive ratio for this problem. / En 2007, Babaioff, Immorlica, et Kleinberg formulèrent la version matroïdale du problème du secrétaire (matroid secretary problem), liant de façon élégante la théorie des matroïdes à des généralisations du problème du secrétaire. Dans cette thèse, nous introduisons le lecteur aux matroïdes et au problème du secrétaire, avant de nous lancer dans la définition de Babaioff et al. et dans une étude de résultats récents. En suite nous nous concentrons sur l'important cas spécial du transversal matroid secretary problem. Nous formulons une classe de matroïdes transversales qui n'a pas été defini auparavant, et présentons un algorithme c-compétitif (c une constante) pour cette classe. Nous fournissons aussi l'analyse la plus rigoureuse que l'on connaisse de l'algorithme récent (2008) de Plaxton et Dimitrov pour le transversal matroid secretary problem, ainsi donnant le meilleur rapport de compétitivité que l'on connaisse pour ce problème.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.32403 |
| Date | January 2009 |
| Creators | Thain, Nithum |
| Contributors | Adrian Roshan Vetta (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (Department of Mathematics and Statistics) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0017 seconds