Submodular Secretary Problems (Masters project):

Given a ground set S, a set function f is a function assigning a real number for each subsets of S. Submodular functions form a natural class of sets functions appearing in many fields such as graph theory, economics and game theory. In a submodular secretary problem, the elements of S are revealed in a random order. Whenever an element is revealed, the algorithm must immediately either accept it or reject it. In both cases, the decision of the algorithm is irrevocable, and cannot be changed after additional elements are revealed. The objective of the algorithm is to maximize f over the set of accepted secretaries, subject to a problem specific constraint that the set of accepted elements must obey. This project involves two submodular secretary problems:

1. The algorithm is allowed to pick any subset of elements. A trivial algorithm that picks every element with probability 1/2 is 1/4 competitive. On the other hand, the best known hardness result known is 1/2. We want to reduce this gap by either finding an algorithm with a non-trivial competitive ratio, or improving the hardness.


2. The algorithm is allowed to pick up to k elements. The state of the art competitive ratio for this problem is (1-1/e)/(e + 1) (about 0.170) when the objective function f has an additional property called monotonicity. For general submodular functions only a much worse competitive ratio is known. We want to find better algorithms for both cases. Specifically, the 0.170 competitive algorithm for the monotone case seems non-optimized, and it should be possible to carry its ideas further.

Further questions about the project: moran.feldman "at" epfl.ch

Responsible professor: Ola Svensson

Back to Theory@EPFL.