Nonnecessary conditions or useful procedures in desensitization

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. Shanghai Jiao Tong University. This work was done when the author was visiting Microsoft Research Asia. Microsoft Research Asia, [email protected]

Bipartite graph · Combinatorics · Competitive analysis · Discrete mathematics · Economics · Graph · Graphic matroid · Independent set · Mathematical optimization · Matroid · Matroid partitioning · Oriented matroid · Secretary problem · Set function · Submodular set function · Weighted matroid · Auction Theory and Applications · Complexity and Algorithms in Graphs · Computer Science · Mathematics · Optimization and Search Problems · Finance

• The Application of Cognitive Behaviour Modification Techniques to Social Work Practice

  Open Access•John S Wodarski•International Social Work•1975

  Add to list