Solving 'Still life' with soft constraints and bucket elimination

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/97372

dc.contributor	Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors
dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Morancho Llena, Enrique
dc.contributor.author	Larrosa Bondia, Francisco Javier
dc.date	2003-04
dc.identifier.citation	Morancho, E., Larrosa, J. "Solving 'Still life' with soft constraints and bucket elimination". 2003.
dc.identifier.uri	http://hdl.handle.net/2117/97372
dc.language.iso	eng
dc.relation	LSI-03-14-R
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica
dc.subject	Still life
dc.subject	Software contraints
dc.subject	Bucket elimination
dc.title	Solving 'Still life' with soft constraints and bucket elimination
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.abstract	In this paper we study the aplicability of bucket elimination (BE) to the problem of finding stilllife patterns. Very recently, it has been tackled using integer programming and constraint programming, both of them being search-based methods. We show that BE, which is based on dynamic programming, provides an exponentially lower worstcase complexity than search methods. Then, we empirically show that BE is quite competitive with search-based approaches. Finally, we show how BE can be adapted to exploit the problem symmetries, with which in several cases we outperform previous results.