Geometric Amortization of Enumeration Algorithms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

Geometric Amortization of Enumeration Algorithms

Résumé

In this paper, we introduce a technique we call geometric amortization for enumeration algorithms, which can be used to make the delay of enumeration algorithms more regular with little overhead on the space it uses. More precisely, we consider enumeration algorithms having incremental linear delay, that is, algorithms enumerating, on input x, a set A(x) such that for every t ≤ ♯A(x), it outputs at least t solutions in time O(t • p(|x|)), where p is a polynomial. We call p the incremental delay of the algorithm. While it is folklore that one can transform such an algorithm into an algorithm with maximal delay O(p(|x|)), the naive transformation may use exponential space. We show that, using geometric amortization, such an algorithm can be transformed into an algorithm with delay O(p(|x|) log(♯A(x))) and space O(s log(♯A(x))) where s is the space used by the original algorithm. In terms of complexity, we prove that classes DelayP and IncP1 with polynomial space coincide. We apply geometric amortization to show that one can trade the delay of flashlight search algorithms for their average delay up to a factor of O(log(♯A(x))). We illustrate how this tradeoff is advantageous for the enumeration of solutions of DNF formulas.
Fichier principal
Vignette du fichier
stacs.pdf (916.49 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03955911 , version 1 (25-01-2023)

Licence

Paternité

Identifiants

Citer

Florent Capelli, Yann Strozecki. Geometric Amortization of Enumeration Algorithms. 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), Mar 2023, Hamburg, Germany. ⟨10.4230/LIPIcs.STACS.2023.18⟩. ⟨hal-03955911⟩
63 Consultations
27 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More