License: Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17393/
Go to the corresponding LIPIcs Volume Portal

Gupta, Anupam

Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk)

pdf-format:
LIPIcs-FSTTCS-2022-1.pdf (0.2 MB)

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
Collection: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Issue Date: 2022
Date of publication: 14.12.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI