- Conference Paper
The secretary problem became one of the most prominentonline selection problems due to its numerous applications inonline mechanism design. The task is to select a maximumweight subset of elements subject to given constraints, whereelements arrive one-by-one in random order, revealing aweight upon arrival. The decision whether to select anelement has to be taken immediately after its arrival. Thedifferent applications that map to the secretary problem askfor different constraint families to be handled. The mostprominent ones are matroid constraints, which both capturemany relevant settings and admit strongly competitivesecretary algorithms. However, dealing with more involvedconstraints proved to be much more difficult, and strongalgorithms are known only for a few specific settings. In thispaper, we present a general framework for dealing with thesecretary problem over the intersection of several matroids.This framework allows us to combine and exploit the largeset of matroid secretary algorithms known in the literature.As one consequence, we get constant-competitive secretaryalgorithms over the intersection of any constant numberof matroids whose corresponding (single-)matroid secretaryproblems are currently known to have a constant-competitivealgorithm. Moreover, we show that our results extend tosubmodular objectives. Show more
Book titleProceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)
Pages / Article No.
Subjectmatroid secretary problem; matroid intersection; online algorithms
Organisational unit09487 - Zenklusen, Rico / Zenklusen, Rico
165866 - New Approaches to Constrained Submodular Maximization (SNF)
MoreShow all metadata