The Wrong Direction of Jensen’s Inequality Is Algorithmically Right

Autor:	Zamir, Or
Jazyk:	angličtina
Rok vydání:	2023
Předmět:	Theory of computation → Parameterized complexity and exact algorithms Theory of computation → Algorithm design techniques algorithms complexity Theory of computation → Computational complexity and cryptography Jensen’s inequality
DOI:	10.4230/lipics.icalp.2023.107
Popis:	Let 𝒜 be an algorithm with expected running time e^X, conditioned on the value of some random variable X. We construct an algorithm A' with expected running time O (e^𝖤[X]), that fully executes 𝒜. In particular, an algorithm whose running time is a random variable T can be converted to one with expected running time O (e^𝖤[ln T]), which is never worse than O(𝖤[T]). No information about the distribution of X is required for the construction of 𝒜'. LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 107:1-107:10
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::32f2487e6e8d615087dc5493844640be Zobrazit plný text záznamu