Metadata only
Date
2018Type
- Conference Paper
Abstract
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
Publication status
publishedExternal links
Book title
Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)Pages / Article No.
Publisher
SIAMEvent
Subject
matroid secretary problem; matroid intersection; online algorithmsOrganisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
Funding
165866 - New Approaches to Constrained Submodular Maximization (SNF)
More
Show all metadata