Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.1
URN: urn:nbn:de:0030-drops-173933
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17393/
Gupta, Anupam
Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk)
| pdf-format: |
|
Abstract
Analyzing the performance of algorithms in both the worst case and the average case are cornerstones of computer science: these are two different ways to understand how well algorithms perform. Over the past two decades, there has been a concerted effort to understand the performance of algorithms in models that go beyond these two extremes. In this talk I will discuss some of the proposed models and approaches, particularly for problems related to online algorithms, where decisions must be made sequentially without knowing future portions of the input.
BibTeX - Entry
@InProceedings{gupta:LIPIcs.FSTTCS.2022.1,
author = {Gupta, Anupam},
title = {{Algorithms for Uncertain Environments: Going Beyond the Worst-Case}},
booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
pages = {1:1--1:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-261-7},
ISSN = {1868-8969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17393},
URN = {urn:nbn:de:0030-drops-173933},
doi = {10.4230/LIPIcs.FSTTCS.2022.1},
annote = {Keywords: Optimization under Uncertainty, Online Algorithms, Beyond Worst Case Analysis}
}
| Keywords: | Optimization under Uncertainty, Online Algorithms, Beyond Worst Case Analysis | |
| Seminar: | 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 14.12.2022 |
