NeurIPS 2019poster2 citations
Secretary Ranking with Minimal Inversions
Sepehr Assadi, Eric Balkanski, Renato Leme
Abstract
We study a secretary problem which captures the task of ranking in online settings. We term this problem the secretary ranking problem: elements from an ordered set arrive in random order and instead of picking the maximum element, the algorithm is asked to assign a rank, or position, to each of the elements. The rank assigned is irrevocable and is given knowing only the pairwise comparisons with elements previously arrived. The goal is to minimize the distance of the rank produced to the true rank of the elements measured by the Kendall-Tau distance, which corresponds to the number of pairs that are inverted with respect to the true order.
BibTeX
@inproceedings{NEURIPS2019_3871bd64,
author = {Assadi, Sepehr and Balkanski, Eric and Leme, Renato},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Secretary Ranking with Minimal Inversions},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/3871bd64012152bfb53fdf04b401193f-Paper.pdf},
volume = {32},
year = {2019}
}