| Competitive Weighted Matching (2009) | |||||||||||||||
Abstract | |||||||||||||||
| 1 Introduction Motivated by applications related to auctions, mechanism design, and revenuemanagement, Babaioff et al. recently introduced a generalization of the secretary problem called the online matroid problem [1]. In the online matroid problem,the goal is to build a maximum weight independent set, but we are constrained from knowing the full input to the problem. Instead, a uniformly random permu-tation of the matroid elements is revealed, one element at a time, and we must immediately decide whether to include the revealed element in the independentset. In such a setting, an online algorithm is said to be c-competitive if it is ableto produce an independent set with weight within a factor of | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||