Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. A Framework for the Secretary Problem on the Intersection of Matroids
 
conference paper

A Framework for the Secretary Problem on the Intersection of Matroids

Feldman, Moran  
•
Svensson, Ola  
•
Zenklusen, Rico
January 1, 2018
Soda'18: Proceedings Of The Twenty-Ninth Annual Acm-Siam Symposium On Discrete Algorithms
29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

The secretary problem became one of the most prominent online selection problems due to its numerous applications in online mechanism design. The task is to select a maximum weight subset of elements subject to given constraints, where elements arrive one-by-one in random order, revealing a weight upon arrival. The decision whether to select an element has to be taken immediately after its arrival. The different applications that map to the secretary problem ask for different constraint families to be handled. The most prominent ones are matroid constraints, which both capture many relevant settings and admit strongly competitive secretary algorithms. However, dealing with more involved constraints proved to be much more difficult, and strong algorithms are known only for a few specific settings. In this paper, we present a general framework for dealing with the secretary problem over the intersection of several matroids. This framework allows us to combine and exploit the large set of matroid secretary algorithms known in the literature. As one consequence, we get constant-competitive secretary algorithms over the intersection of any constant number of matroids whose corresponding (single-)matroid secretary problems are currently known to have a constant-competitive algorithm. Moreover, we show that our results extend to submodular objectives.

  • Details
  • Metrics
Type
conference paper
DOI
10.1137/1.9781611975031.48
Web of Science ID

WOS:000483921200049

Author(s)
Feldman, Moran  
Svensson, Ola  
Zenklusen, Rico
Date Issued

2018-01-01

Publisher

ASSOC COMPUTING MACHINERY

Publisher place

New York

Published in
Soda'18: Proceedings Of The Twenty-Ninth Annual Acm-Siam Symposium On Discrete Algorithms
ISBN of the book

978-1-6119-7503-1

Start page

735

End page

752

Subjects

matroid secretary problem

•

matroid intersection

•

online algorithms

•

maximization

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL2  
Event nameEvent placeEvent date
29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

New Orleans, LA

Jan 07-10, 2018

Available on Infoscience
September 20, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/161301
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés