When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be huge, including sometimes exponential. Furthermore, depending on the application, many of these solutions can be considered equivalent. The problem of an efficient enumeration of the equivalence classes or of one representative per class (without generating all the solutions), although identified as a need in many areas, has been addressed only for very few specific cases. In this paper, we provide a general framework that solves this problem in polynomial delay for a wide variety of contexts, including optimization ones that can be addressed by dynamic programming algorithms, and for certain types of equivalence relations between solutions.

A general framework for enumerating equivalence classes of solutions / Wang, Y.; Mary, A.; Sagot, M. -F.; Sinaimeri, B.. - 204:(2021), pp. 1-14. [10.4230/LIPIcs.ESA.2021.80]

A general framework for enumerating equivalence classes of solutions

Sinaimeri B.
2021

Abstract

When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be huge, including sometimes exponential. Furthermore, depending on the application, many of these solutions can be considered equivalent. The problem of an efficient enumeration of the equivalence classes or of one representative per class (without generating all the solutions), although identified as a need in many areas, has been addressed only for very few specific cases. In this paper, we provide a general framework that solves this problem in polynomial delay for a wide variety of contexts, including optimization ones that can be addressed by dynamic programming algorithms, and for certain types of equivalence relations between solutions.
978-3-95977-204-4
Dynamic programming, Enumeration algorithms, Equivalence relation
A general framework for enumerating equivalence classes of solutions / Wang, Y.; Mary, A.; Sagot, M. -F.; Sinaimeri, B.. - 204:(2021), pp. 1-14. [10.4230/LIPIcs.ESA.2021.80]
File in questo prodotto:
File Dimensione Formato  
LIPIcs-ESA-2021-80.pdf

Open Access

Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 748.68 kB
Formato Adobe PDF
748.68 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/210655
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact