Lo scopo di questo elaborato è quello mostrare strategie di rilassamento della stabilità per diverse tipologie di problemi di grafi bipartiti. In primo luogo affronteremo il problema MAX HRSS, presentando un algoritmo di approssimazione per combattere la NP-difficoltà del problema. Successivamente, tratteremo casi speciali dello stesso problema MAX HRSS interessanti per la loro risolvibilità in tempo polinomiale. Per poi concludere studiando problemi in matching bipartiti con pesi sugli archi, dove i pesi rappresentano l'importanza di includere o meno tale arco nel matching. Presenteremo una strategia di rilassatezza della stabilità basata sul pagare un prezzo per gli archi bloccanti del matching, massimizzando il valore dato dal peso degli archi del matching meno il costo degli archi bloccanti. Infine, mostreremo che ci sono casi in cui questa strategia porta ad algoritmi risolutivi polinomiali.
Stabilità rilassata in problemi di matching bipartiti
CALDANA, JACOPO
2022/2023
Abstract
Lo scopo di questo elaborato è quello mostrare strategie di rilassamento della stabilità per diverse tipologie di problemi di grafi bipartiti. In primo luogo affronteremo il problema MAX HRSS, presentando un algoritmo di approssimazione per combattere la NP-difficoltà del problema. Successivamente, tratteremo casi speciali dello stesso problema MAX HRSS interessanti per la loro risolvibilità in tempo polinomiale. Per poi concludere studiando problemi in matching bipartiti con pesi sugli archi, dove i pesi rappresentano l'importanza di includere o meno tale arco nel matching. Presenteremo una strategia di rilassatezza della stabilità basata sul pagare un prezzo per gli archi bloccanti del matching, massimizzando il valore dato dal peso degli archi del matching meno il costo degli archi bloccanti. Infine, mostreremo che ci sono casi in cui questa strategia porta ad algoritmi risolutivi polinomiali.File | Dimensione | Formato | |
---|---|---|---|
Tesi Caldana.pdf
accesso aperto
Dimensione
1.37 MB
Formato
Adobe PDF
|
1.37 MB | Adobe PDF | Visualizza/Apri |
The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/61296