Reasoning with incomplete and imprecise preferences

Gelain, Mirco (2011) Reasoning with incomplete and imprecise preferences, [Dissertation thesis], Alma Mater Studiorum Università di Bologna. Dottorato di ricerca in Informatica, 23 Ciclo. DOI 10.6092/unibo/amsdottorato/3657.
Documenti full-text disponibili:
[img]
Anteprima
Documento PDF (English) - Richiede un lettore di PDF come Xpdf o Adobe Acrobat Reader
Download (3MB) | Anteprima

Abstract

Preferences are present in many real life situations but it is often difficult to quantify them giving a precise value. Sometimes preference values may be missing because of privacy reasons or because they are expensive to obtain or to produce. In some other situations the user of an automated system may have a vague idea of whats he wants. In this thesis we considered the general formalism of soft constraints, where preferences play a crucial role and we extended such a framework to handle both incomplete and imprecise preferences. In particular we provided new theoretical frameworks to handle such kinds of preferences. By admitting missing or imprecise preferences, solving a soft constraint problem becomes a different task. In fact, the new goal is to find solutions which are the best ones independently of the precise value the each preference may have. With this in mind we defined two notions of optimality: the possibly optimal solutions and the necessary optimal solutions, which are optimal no matter we assign a precise value to a missing or imprecise preference. We provided several algorithms, bases on both systematic and local search approaches, to find such kind of solutions. Moreover, we also studied the impact of our techniques also in a specific class of problems (the stable marriage problems) where imprecision and incompleteness have a specific meaning and up to now have been tackled with different techniques. In the context of the classical stable marriage problem we developed a fair method to randomly generate stable marriages of a given problem instance. Furthermore, we adapted our techniques to solve stable marriage problems with ties and incomplete lists, which are known to be NP-hard, obtaining good results both in terms of size of the returned marriage and in terms of steps need to find a solution.

Abstract
Tipologia del documento
Tesi di dottorato
Autore
Gelain, Mirco
Supervisore
Co-supervisore
Dottorato di ricerca
Scuola di dottorato
Scienze e ingegneria dell'informazione
Ciclo
23
Coordinatore
Settore disciplinare
Settore concorsuale
Parole chiave
preferences incompleteness imprecision local search stable marriages soft constraints
URN:NBN
DOI
10.6092/unibo/amsdottorato/3657
Data di discussione
6 Maggio 2011
URI

Altri metadati

Statistica sui download

Gestione del documento: Visualizza la tesi

^