M.Sc Thesis
M.Sc Student Finkelstein Liri Two Algorithms for the Matroid Secretary Problem Department of Industrial Engineering and Management Professor Aharon Ron Lavi

Abstract

In the classic secretary problem a known number of candidates are interviewed for a secretary position. They arrive in a randomly-ordered sequence. Whenever a candidate is interviewed, the manager learns her true "value", and then he must make an irrevocable decision as to whether or not to accept her for the position. An algorithm needs to choose the most valuable candidate with high constant probability (not dependent on the number of secretaries). One variation of the classic secretary problem is where the goal is to maximize the expected value of the chosen secretary. Thus, for example, selecting other candidates with values close to the best might also be beneficial.

The matroid secretary problem is a setting in which elements arrive at a random order, and the algorithm must make an irrevocable decision whether or not to select each element. Not all subsets of elements can be selected, only those subsets that are independent sets of a pre-specified matroid. Each element has a weight, which is revealed when the element arrives. The goal is to select a subset of elements, which is an independent set, and has maximal weight. When the matroid independent sets are all the singletons, this is exactly the variation of the secretary problem specified above. The offline version of the matroid secretary problem is optimally solved by a greedy algorithm for any matroid and any weight function. An open question is whether constant competitiveness is achievable for all matroids. Several attempts to answer this question during the last decade yielded solutions for some important classes of matroids: uniform, partition, transversal, graphic, and laminar.

I studied laminar matroids - a class that was not solved during the time I worked. I defined cells algorithm and showed it is 4-competitive for uniform matroid and 9.5-competitive for laminar matroids of height 2, but the analysis I use is not extendable for laminar matroid of general height. I used ideas from the cells algorithm for a new algorithm for general matroids - the circuits algorithm, and showed that it has constant competitive ratios for special cases of matroids that were not studied before. An interesting property of the circuits algorithm is that it uses only terms of general matroids, not relying on properties of a certain class of matroids. Finally, I proved that the circuits and the cells algorithms yield exactly the same output for laminar matroid of general height.