## תקציר

During the last decade, the matroid secretary problem (MSP) became one of the most prominent classes of online selection problems. The interest in MSP is twofold: on the one hand, there are many interesting applications of MSP, and on the other hand, there is strong hope that MSP admits O(1)-competitive algorithms, which is the claim of the well-known matroid secretary conjecture. Partially linked to its numerous applications in mechanism design, substantial interest arose also in the study of nonlinear versions of MSP, with a focus on the sub modular matroid secretary problem (SMSP). The fact that sub modularity captures the property of diminishing returns, a very natural property for valuation functions, is a key reason for the interest in SMSP. So far, O(1)-competitive algorithms have been obtained for SMSP over some basic matroid classes. This created some hope that, analogously to the matroid secretary conjecture, one may even obtain O(1)-competitive algorithms for SMSP over any matroid. However, up to now, most questions related to SMSP remained open, including whether SMSP may be substantially more difficult than MSP, and more generally, to what extend MSP and SMSP are related. Our goal is to address these points by presenting general black-box reductions from SMSP to MSP. In particular, we show that any O(1)-competitive algorithm for MSP, even restricted to a particular matroid class, can be transformed in a black-box way to an O(1)-competitive algorithm for SMSP over the same matroid class. This implies that the matroid secretary conjecture is equivalent to the same conjecture for SMSP. Hence, in this sense SMSP is not harder than MSP. Also, to find O(1)-competitive algorithms for SMSP over a particular matroid class, it suffices to consider MSP over the same matroid class. Using our reductions we obtain many first and improved O(1)-competitive algorithms for SMSP over various matroid classes by leveraging known algorithms for MSP. Moreover, our reductions imply an O(log log(rank))-competitive algorithm for SMSP, thus, matching the currently best asymptotic algorithm for MSP, and substantially improving on the previously best O(log(rank))-competitive algorithm for SMSP.

שפה מקורית | אנגלית |
---|---|

כותר פרסום המארח | Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 |

מוציא לאור | IEEE Computer Society |

עמודים | 486-505 |

מספר עמודים | 20 |

מסת"ב (אלקטרוני) | 9781467381918 |

מזהי עצם דיגיטלי (DOIs) | |

סטטוס פרסום | פורסם - 11 דצמ׳ 2015 |

פורסם באופן חיצוני | כן |

אירוע | 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, ארצות הברית משך הזמן: 17 אוק׳ 2015 → 20 אוק׳ 2015 |

### סדרות פרסומים

שם | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

כרך | 2015-December |

ISSN (מודפס) | 0272-5428 |

### כנס

כנס | 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 |
---|---|

מדינה/אזור | ארצות הברית |

עיר | Berkeley |

תקופה | 17/10/15 → 20/10/15 |

### הערה ביבליוגרפית

Publisher Copyright:© 2015 IEEE.