Torna ai risultati della ricercaBando per assegno di ricerca
| Titolo del progetto di ricerca in italiano | Studio teorico-computazionale di rilassamenti convessi per il problema del massimo insieme stabile |
|---|---|
| Titolo del progetto di ricerca in inglese | Theoretical and computational study of convex relaxations for the maximum stable set problem |
| Settore Concorsuale | 01 - Scienze matematiche e informatiche |
| S.S.D | MAT/09 - RICERCA OPERATIVA |
| Settore Concorsuale | 01 - Scienze matematiche e informatiche |
| S.S.D | INF/01 - INFORMATICA |
| Descrizione sintetica in italiano | Il problema del Massimo Insieme Stabile rappresenta uno dei problemi di base dell’Ottimizzazione Combinatoria e della teoria dei grafi. Esso appartiene alla classe dei problemi NP-hard persino difficili da approssimare. Tale complessità si manifesta anche in pratica: calcolare il massimo insieme stabile su grafi con poche centinaia di vertici può essere molto difficile se si richiede un certificato di ottimalità della soluzione. La principale motivazione di questa difficoltà è la mancanza di tecniche efficaci per il calcolo di buone limitazioni superiori del valore ottimo (upper bound). Le tecniche note, basate sulla programmazione matematica, utilizzano rilassamenti lineari o semidefiniti. I rilassamenti lineari noti sono risolvibili efficientemente ma producono spesso upper bound di scarsa qualità. D'altro canto, i rilassamenti semidefiniti forniscono upper bound di qualità eccellente, ma richiedono tempi di calcolo eccessivi. |
| Descrizione sintetica in inglese | The Maximum Stable Set problem is a fundamental problem in Combinatorial Optimization and Graph Theory. It belongs to the class of NP-hard problems and is even difficult to approximate (Hastad 1999). This complexity also borns out in practice. In fact, computing exactly the stability number of graphs with 300 vertices or so can be too time consuming. One major motivation for such a difficulty is the lack of effective techniques to compute good upper bounds of the optimal value. In the literature many papers appeared investigating linear or semidefinite relaxations to compute upper bounds to the stability number of a graph. Linear relaxations are computationally tractable but often provide weak upper bounds. On the contrary, semidefinite relaxations provide excellent upper bounds but too expensive to compute. |
| Data del bando | 16/12/2011 |
| E' richiesta mobilità internazionale? | yes |
| Paesi in cui può essere condotta la ricerca |
Turkey |
| Paesi di residenza dei candidati |
All |
| Nazionalità dei candidati |
All |
| Sito web del bando | http://www.univaq.it/section.php?id=766 |
| Destinatari dell'assegno di ricerca (of target group) |
Experienced researcher or 4-10 yrs (Post-Doc) |
|---|
| Nome dell'Ente finanziatore | Università degli Studi dell'Aquila |
|---|---|
| Tipologia dell'Ente | Public research |
| Paese dell'Ente | Italy |
| Città | L'Aquila |
| Sito web | http://www.univaq.it |
| assegni.ricerca@univaq.it |
| L'assegno finanziato/cofinanziato attraverso un EU Research Framework Programme? | No |
|---|
| Data di scadenza del bando | 19/01/2012 - alle ore 00:00 |
|---|---|
| Come candidarsi | Other |