Ítem


Computing small Rainbow Cycle Numbers with SAT modulo Symmetries

Markus Kirchweger from the Vienna University of Technology, tells that envy-freeness up to any good (EFX) is a key concept in Computational Social Choice for the fair division of indivisible goods, where no agent envies another’s allocation after removing any single item. A deeper understanding of EFX allocations is facilitated by exploring the rainbow cycle number ($R_f(d)$), the largest number of independent sets in a certain class of directed graphs. Upper bounds on $R_f(d)$ provide guarantees the feasibility of EFX allocations (Chaudhury et al., EC 2021). In this work, we precisely compute the numbers $R_f(d)$ for small values of d, employing the SAT modulo Symmetries framework. SAT modulo Symmetries is specifically tailored for the constraint-based isomorph-free generation of combinatorial structures. We provide an efficient encoding for the rainbow cycle number, comparing eager and lazy approaches. To cope with the huge search space, we extend the encoding with invariant pruning, a new method that significantly speeds up computation

7780.mp4 7780.mp3

Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística

Altres contribucions: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Autor: Kirchweger, Markus
Szeider, Stefan
Data: 3 setembre 2024
Resum: Markus Kirchweger from the Vienna University of Technology, tells that envy-freeness up to any good (EFX) is a key concept in Computational Social Choice for the fair division of indivisible goods, where no agent envies another’s allocation after removing any single item. A deeper understanding of EFX allocations is facilitated by exploring the rainbow cycle number ($R_f(d)$), the largest number of independent sets in a certain class of directed graphs. Upper bounds on $R_f(d)$ provide guarantees the feasibility of EFX allocations (Chaudhury et al., EC 2021). In this work, we precisely compute the numbers $R_f(d)$ for small values of d, employing the SAT modulo Symmetries framework. SAT modulo Symmetries is specifically tailored for the constraint-based isomorph-free generation of combinatorial structures. We provide an efficient encoding for the rainbow cycle number, comparing eager and lazy approaches. To cope with the huge search space, we extend the encoding with invariant pruning, a new method that significantly speeds up computation
7780.mp4 7780.mp3
Format: audio/mpeg
video/mp4
Accés al document: http://hdl.handle.net/10256.1/7780
Llenguatge: eng
Editor: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Col·lecció: 30th International Conference on Principles and Practice of Constraint Programming
Drets: Attribution-NonCommercial-ShareAlike 4.0 International
URI Drets: http://creativecommons.org/licenses/by-nc-sa/4.0/
Matèria: Programació per restriccions (Informàtica) -- Congressos
Constraint programming (Computer science) -- Congresses
Títol: Computing small Rainbow Cycle Numbers with SAT modulo Symmetries
Tipus: info:eu-repo/semantics/lecture
Repositori: DUGiMedia

Matèries

Autors