Algorithms for Matroid Secretary Problem and Its Multiobjective Variant

Matroids are a mathematical structure that generalize the linear independence in vector spaces and acyclic subgraphs in graphs, and have been applied in combinatorial optimization and discrete math. In the matroid secretary problem, a matroid M is given and an adversary assigns a weight to each element of M. The elements appear one by one in uniformly random order, and when an element e arrives, the weight w(e) is presented and an irrevocable decision to accept or reject the element has to be made at that time. The goal of the problem is to design an online algorithm that selects an independent set whose weight is as large as possible. This problem generalizes the classical secretary problem and has applications in online auction and online mechanism design.

In this presentation, we show a constant competitive algorithm of the matroid secretary problem for the partition matroids without knowledge of the partition and a constant competitive algorithm of the matroid secretary problem for the paving matroids. In some cases, it is appropriate to optimize more than one objective function. For example, the manager intends to employ the secretary with highest quality but lowest salary requirement. Then we introduce the multi-objective secretary problem to model this situation. Moreover, we also review some notions of multi-objective optimization. Finally, constant competitive algorithms of the multi-objective matroid secretary problem for the paving matroids and the uniform matroids are presented.

Event Topic

Discrete Applied Math Seminar