Can I read A General Framework for Enumerating Equivalence Classes of Solutions on EtoBox?

A General Framework for Enumerating Equivalence Classes of Solutions by Yishu Wang; Arnaud Mary; Marie-France Sagot; Blerina Sinaimeri is a Computer Science article available to read on EtoBox.

What is A General Framework for Enumerating Equivalence Classes of Solutions about?

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 optimization problems solvable by dynamic programming algorithms, and for certain types of equivalence relations between solutions.

Who reads A General Framework for Enumerating Equivalence Classes of Solutions?

Author

Yishu Wang; Arnaud Mary; Marie-France Sagot; Blerina Sinaimeri

Publisher

Springer Science and Business Media LLC

Published

2023

Language

EN

Field

Computer Science (Physical Sciences)