## Abstract

The classical secretary problem studies the problem of selecting online an element (a "secretary") with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and this decision is irrevocable. Constant-competitive algorithms are known for the classical secretary problems (see, e.g., the survey of Freeman [7]) and several variants. We study the following two extensions of the secretary problem: • In the discounted secretary problem, there is a time-dependent "discount" factor d(t). and the benefit derived from selecting an element/secretary e at time t is d(t)·v(e). For this problem with arbitrary (not necessarily decreasing) functions d(t), we show a constant-competitive algorithm when the expected optimum is known in advance. With no prior knowledge, we exhibit a lower bound of Ω(log n/log log n), and give a nearly-matching O(logn)-competitive algorithm. • In the weighted secretary problem, up to K secretaries can be selected; when a secretary is selected (s)he must be irrevocably assigned to one of K positions, with position k having weight w(k), and assigning object/secretary e to position k has benefit w(k)·v(e). The goal is to select secretaries and assign them to positions to maximize ∑_{e,k} w(k)·v(e)·x_{ek} where x_{ek} is an indicator variable that secretary e is assigned position k. We give constant-competitive algorithms for this problem. Most of these results can also be extended to the matroid secretary case (Babaioff et al. [2]) for a large family of matroids with a constant-factor loss, and an O(log rank) loss for general matroids. These results are based on a reduction from various matroids to partition matroids which present a unified approach to many of the upper bounds of Babaioff et al. These problems have connections to online mechanism design (see, e.g., Hajiaghayi et al. [9]). All our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problems.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms |

Publisher | Association for Computing Machinery |

Pages | 1245-1254 |

Number of pages | 10 |

ISBN (Print) | 9780898716801 |

DOIs | |

State | Published - 2009 |

Event | 20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States Duration: Jan 4 2009 → Jan 6 2009 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 20th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | New York, NY |

Period | 1/4/09 → 1/6/09 |

## ASJC Scopus subject areas

- Software
- General Mathematics