A Framework for the Secretary Problem on the Intersection of Matroids
METADATA ONLY
Author / Producer
Date
2018
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)
Journal / series
Volume
Pages / Article No.
735 - 752
Publisher
SIAM
Event
29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
matroid secretary problem; matroid intersection; online algorithms
Organisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
Notes
Funding
165866 - New Approaches to Constrained Submodular Maximization (SNF)