License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.478
URN: urn:nbn:de:0030-drops-39586
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3958/
Go to the corresponding LIPIcs Volume Portal

Ma, Tengyu ; Tang, Bo ; Wang, Yajun

The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems

pdf-format:
46.pdf (0.6 MB)

Abstract

We study the matroid secretary problems with submodular valuation functions. In these problems, the elements arrive in random order. When one element arrives, we have to make an immediate and irrevocable decision on whether to accept it or not. The set of accepted elements must form an independent set in a predefined matroid. Our objective is to maximize the value of the accepted elements. In this paper, we focus on the case that the valuation function is a non-negative and monotonically non-decreasing submodular function.

We introduce a general algorithm for such submodular matroid secretary problems. In particular, we obtain constant competitive algorithms for the cases of laminar matroids and transversal
matroids. Our algorithms can be further applied to any independent set system defined by the intersection of a constant number of laminar matroids, while still achieving constant competitive ratios. Notice that laminar matroids generalize uniform matroids and partition matroids.

On the other hand, when the underlying valuation function is linear, our algorithm achieves a competitive ratio of 9.6 for laminar matroids, which significantly improves the previous
result.

BibTeX - Entry

@InProceedings{ma_et_al:LIPIcs:2013:3958,
  author =	{Tengyu Ma and Bo Tang and Yajun Wang},
  title =	{{The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{478--489},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3958},
  URN =		{urn:nbn:de:0030-drops-39586},
  doi =		{10.4230/LIPIcs.STACS.2013.478},
  annote =	{Keywords: secretary problem, submodular function, matroid, online algorithm}
}

Keywords: secretary problem, submodular function, matroid, online algorithm
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI