Computer Science – Data Structures and Algorithms
Scientific paper
2011-07-12
Computer Science
Data Structures and Algorithms
Scientific paper
We study the matroid secretary problem when the valuation is defined by a submodular function. In this problem, the elements of the ground set of a matroid are arriving in random order. When one element arrives, we have to make an immediate and irrevocable decision regarding whether or not to accept it. Our objective is to select an independent set under the given matroid, so that the valuation of the set is maximized with a submodular function. Our major result is a constant-competitive algorithm for the submodular matroid secretary problem under transversal matroids with monotonically increasing submodular valuation functions. In addressing it, we instead develop a constant competitive algorithm for a more general online bipartite graph matching problem. As a natural special case, we also consider the secretary problem under partition matroids and provide an extremely simple algorithm which can handle non-monotone submodular functions. This algorithm significantly improves the competitive ratio over the previous work.
Tang Bo
Wang Yajun
No associations
LandOfFree
Algorithms for Submodular Matroid Secretary Problems Under Transversal Matroids and Partition Matroids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Algorithms for Submodular Matroid Secretary Problems Under Transversal Matroids and Partition Matroids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Submodular Matroid Secretary Problems Under Transversal Matroids and Partition Matroids will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-564798