Paper Info
Title
Improved competitive ratio for the matroid secretary problem
Abstract
The Matroid Secretary Problem, introduced by Babaioff et al. (2007), is a generalization of the Classical Secretary Problem. In this problem, elements from a matroid are presented to an on-line algorithm in a random order. Each element has a weight associated with it, which is revealed to the algorithm along with the element. After each element is revealed the algorithm must make an irrevocable decision on whether or not to select it. The goal is to pick an independent set with the sum of the weights of the selected elements as large as possible. Babaioff et al gave an algorithm for the Matroid Secretary Problem with a competitive ratio of O(logρ), where ρ is the rank of the matroid. It has been conjectured that a constant competitive-ratio is achievable for this problem. In this paper we give an algorithm that has a competitive-ratio of O(√logρ).
Year
DOI
Venue
2012
10.5555/2095116.2095251
SODA
Keywords
Field
DocType
competitive ratio,on-line algorithm,irrevocable decision,matroid secretary problem,constant competitive-ratio,random order,classical secretary problem,selected element,independent set,improved competitive ratio
Matroid,Discrete mathematics,Combinatorics,Oriented matroid,Secretary problem,Matroid partitioning,Independent set,Graphic matroid,Weighted matroid,Mathematics,Competitive analysis
Conference
ISBN
Citations 
PageRank 
978-1-61197-251-1
19
1.05
References 
Authors
9
2
Name
Order
Citations
PageRank
Sourav Chakraborty138149.27
Oded Lachish220418.19