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

Gupta, Anupam

doi:10.4230/LIPIcs.FSTTCS.2022.1

Document

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

Author Anupam Gupta

Part of: Volume: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
License: Creative Commons Attribution 4.0 International license
Publication Date: 2022-12-14

PDF

File

PDF

LIPIcs.FSTTCS.2022.1.pdf

Filesize: 253 kB
1 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2022.1
URN: urn:nbn:de:0030-drops-173933

Subject Classification

ACM Subject Classification

Theory of computation → Online algorithms

Keywords

Optimization under Uncertainty
Online Algorithms
Beyond Worst Case Analysis

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get BibTex

Anupam Gupta. Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.FSTTCS.2022.1

Author Details

Anupam Gupta

Carnegie Mellon University, Pittsburgh, PA, USA

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail

	
		OSZAR »