Benvenuti nell'Anagrafe della Ricerca d'Ateneo
La valutazione delle attività di ricerca che si svolgono nelle università ha assunto un'importanza rilevante sia per l'intero sistema universitario sia all'interno di ogni singolo ateneo. Roma Tre si è quindi dotata di idonei strumenti informativi in grado di supportare al meglio le azioni di monitoraggio e di valutazione delle attività di ricerca svolte nei propri dipartimentied ha realizzato una Anagrafe della Ricerca di Ateneo.
EnglishMany polynomial-time solvable combinatorial optimization problems become NP-hard if an additional complicating constraint is added to restrict the set of feasible solutions. In this paper, we consider two such problems, namely maximum-weight matching and maximum-weight matroid intersection with one additional budget constraint. We present the first polynomial-time approximation schemes for these problems. Similarly to other approaches for related problems, our schemes compute two solutions to the Lagrangian relaxation of the problem and patch them together to obtain a near-optimal solution. However, due to the richer combinatorial structure of the problems considered here, standard patching techniques do not apply. To circumvent this problem, we crucially exploit the adjacency relations on the solution polytope and, surprisingly, the solution to an old combinatorial puzzle. © 2009 Springer and Mathematical Programming Society.
Berger, A., Bonifaci, V., Grandoni, F., & Schafer, G. (2011). Budgeted matching and budgeted matroid intersection via the gasoline puzzle. MATHEMATICAL PROGRAMMING, 128(1-2), 355-372.
| Titolo: | Budgeted matching and budgeted matroid intersection via the gasoline puzzle |
| Autori: | |
| Data di pubblicazione: | 2011 |
| Rivista: | |
| Citazione: | Berger, A., Bonifaci, V., Grandoni, F., & Schafer, G. (2011). Budgeted matching and budgeted matroid intersection via the gasoline puzzle. MATHEMATICAL PROGRAMMING, 128(1-2), 355-372. |
| Handle: | http://hdl.handle.net/11590/381271 |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11590/381271
Copyright © 2021