Torna ai risultati della ricercaBando per assegno di ricerca
| Titolo del progetto di ricerca in italiano | Algoritmi esatti e di approssimazione per problemi di ottimizzazione combinatoria - “Rif. 366/2011” |
|---|---|
| Titolo del progetto di ricerca in inglese | Exact and approximation algorithms for combinatorial optimization problems - “Ref. 366/2011” |
| Settore Concorsuale | 01 - Scienze matematiche e informatiche |
| S.S.D | MAT/09 - RICERCA OPERATIVA |
| Descrizione sintetica in italiano | Il programma di ricerca prevede lo svolgimento di attività di ricerca e sviluppo nell’ambito degli algoritmi esatti e di approssimazione per problemi di difficili di ottimizzazione combinatoria. Gran parte dei problemi di ottimizzazione combinatoria di rilevanza pratica sono per l’appunto NP-hard e per molti di questi problemi non sono noti o addirittura è fortemente improbabile che esistano algoritmi euristici per i quali sia possibile anche solo identificare un rapporto di approssimazione costante. In quest’ambito, verranno affrontati vari problemi per i quali verranno proposti algoritmi esatti ed approssimati che saranno analizzati in termini di complessità di caso peggiore (worst-case complexity analysis). Particolare attenzione verrà data all’analisi di complessità di caso peggiore di algoritmi approssimati di bassa complessità esponenziale per problemi non approssimabili in tempo polinomiale. |
| Descrizione sintetica in inglese | The research focuses on the design of exact and approximation algorithms for hard combinatorial optimization problems (COPs). Most COPs of practical relevance are classified in formal terms as NP-hard. Even if until now no proof is known that NP-hard problems cannot be solved by means of polynomial time algorithms, there is a strong evidence that such algorithms may not exist and we have to make use of approximation approaches. For many of these problems, it is also highly unlikely to find heuristic polynomial time algorithms reaching a constant approximation ratio w.r.t. the optimal solution. In this context, several problems will considered and both exact and heuristic algorithms will be designed and analyzed w.r.t. worst-case complexity. Special emphasis will be devoted to approximation algorithms presenting low exponential complexity for problems that cannot reach a constant approximation ratio by means of polynomial time algorithms. |
| Data del bando | 28/11/2011 |
| Paesi in cui può essere condotta la ricerca |
All |
| Paesi di residenza dei candidati |
All |
| Nazionalità dei candidati |
All |
| Sito web del bando | http://www.swas.polito.it/services/concorsi/assric.asp |
| Destinatari dell'assegno di ricerca (of target group) |
Experienced researcher or 4-10 yrs (Post-Doc) |
|---|---|
| Criteri di selezione in italiano (breve descrizione) | Il bando e la modulistica per partecipare alla valutazione comparativa sono disponibili all'indirizzo: http://www.swas.polito.it/services/concorsi/assric.asp |
| Criteri di selezione in inglese (breve descrizione) | To apply for research grants fill out the form available at the following address: http://www.swas.polito.it/services/concorsi/assric.asp |
| Nome dell'Ente finanziatore | Politecnico di Torino |
|---|---|
| Tipologia dell'Ente | Public research |
| Paese dell'Ente | Italy |
| Città | Torino |
| Sito web | http://www.polito.it/ |
| ruo.persns@polito.it | |
| Telefono | +39 011 090 6229 |
| L'assegno finanziato/cofinanziato attraverso un EU Research Framework Programme? | No |
|---|
| Data di scadenza del bando | 07/12/2011 - alle ore 00:00 |
|---|---|
| Come candidarsi | Other |