Online Selection Problems against Constrained Adversary

Zhihao Jiang, Pinyan Lu, Zhihao Gavin Tang, Yuhao Zhang
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:5002-5012, 2021.

Abstract

Inspired by a recent line of work in online algorithms with predictions, we study the constrained adversary model that utilizes predictions from a different perspective. Prior works mostly focused on designing simultaneously robust and consistent algorithms, without making assumptions on the quality of the predictions. In contrary, our model assumes the adversarial instance is consistent with the predictions and aim to design algorithms that have best worst-case performance against all such instances. We revisit classical online selection problems under the constrained adversary model. For the single item selection problem, we design an optimal algorithm in the adversarial arrival model and an improved algorithm in the random arrival model (a.k.a., the secretary problem). For the online edge-weighted bipartite matching problem, we extend the classical Water-filling and Ranking algorithms and achieve improved competitive ratios.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-jiang21h, title = {Online Selection Problems against Constrained Adversary}, author = {Jiang, Zhihao and Lu, Pinyan and Tang, Zhihao Gavin and Zhang, Yuhao}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {5002--5012}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/jiang21h/jiang21h.pdf}, url = {https://proceedings.mlr.press/v139/jiang21h.html}, abstract = {Inspired by a recent line of work in online algorithms with predictions, we study the constrained adversary model that utilizes predictions from a different perspective. Prior works mostly focused on designing simultaneously robust and consistent algorithms, without making assumptions on the quality of the predictions. In contrary, our model assumes the adversarial instance is consistent with the predictions and aim to design algorithms that have best worst-case performance against all such instances. We revisit classical online selection problems under the constrained adversary model. For the single item selection problem, we design an optimal algorithm in the adversarial arrival model and an improved algorithm in the random arrival model (a.k.a., the secretary problem). For the online edge-weighted bipartite matching problem, we extend the classical Water-filling and Ranking algorithms and achieve improved competitive ratios.} }
Endnote
%0 Conference Paper %T Online Selection Problems against Constrained Adversary %A Zhihao Jiang %A Pinyan Lu %A Zhihao Gavin Tang %A Yuhao Zhang %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-jiang21h %I PMLR %P 5002--5012 %U https://proceedings.mlr.press/v139/jiang21h.html %V 139 %X Inspired by a recent line of work in online algorithms with predictions, we study the constrained adversary model that utilizes predictions from a different perspective. Prior works mostly focused on designing simultaneously robust and consistent algorithms, without making assumptions on the quality of the predictions. In contrary, our model assumes the adversarial instance is consistent with the predictions and aim to design algorithms that have best worst-case performance against all such instances. We revisit classical online selection problems under the constrained adversary model. For the single item selection problem, we design an optimal algorithm in the adversarial arrival model and an improved algorithm in the random arrival model (a.k.a., the secretary problem). For the online edge-weighted bipartite matching problem, we extend the classical Water-filling and Ranking algorithms and achieve improved competitive ratios.
APA
Jiang, Z., Lu, P., Tang, Z.G. & Zhang, Y.. (2021). Online Selection Problems against Constrained Adversary. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:5002-5012 Available from https://proceedings.mlr.press/v139/jiang21h.html.

Related Material