7_CP24-29-exponential steepest.mp3
Exponential steepest ascent from valued constraint graphs of pathwidth four
dc.contributor.author
dc.date.issued
2024-09-03
dc.identifier.uri
dc.description.abstract
Melle van Marle from the University of Utrecht, Holland, tells us about the complexity of maximising fitness via local search on valued constraint satisfaction problems (VCSPs). We consider two kinds of local ascents: (1) steepest ascents, where each step changes the domain that produces a maximal increase in fitness; and(2) $\prec$-ordered ascents, where -- of the domains with available fitness increasing changes -- each step changes the $\prec$-minimal domain. We provide a general padding argument to simulate any ordered ascent by a steepest ascent. We construct a VCSP that is a path of binary constraints between alternating 2-state and 3-state domains with exponentially long ordered ascents. We apply our padding argument to this VCSP to obtain a Boolean VCSP that has a constraint (hyper)graph of arity 5 and pathwidth 4 with exponential steepest ascents. This is an improvement on the previous best known construction for long steepest ascents, which had arity 8 and pathwidth 7
dc.format.mimetype
audio/mpeg
video/mp4
dc.language.iso
Anglès
dc.publisher
Universitat de Girona. Departament d'Informàtica, Matemàtica Aplicada i Estadística
dc.relation.ispartofseries
30th International Conference on Principles and Practice of Constraint Programming
dc.rights
Attribution-NonCommercial-ShareAlike 4.0 International
dc.rights.uri
dc.subject
dc.title
Exponential steepest ascent from valued constraint graphs of pathwidth four
dc.type
Conferència/Classe
dc.rights.accessrights
Accés obert