Abstract
The main theme of this project is the investigation of several problems on objects of discrete nature, with focus on their algorithmic, structural and theoretical aspects. We will give emphasis to the treatment of "hard problems" (formally known as NP-hard problems), but we will not restrict to this class of problems. We will also consider problems belonging to other complexity classes, as well as problems whose difficulty lies on the lack of information or on the decentralization of the decisions of different users, in contexts where the decision of an user affects the decision of the others. The algorithmic issues that will be investigated includes the design of efficient and practical algorithms (with performance guarantees, when possible), the development of new techniques, and the classification of several problems regarding their computational complexity. The structural and theoretical studies concerning the combinatorial objects that we will be carried out include their characterization, properties, conditions for their existence, counting and construction of these objects. The topics that we will investigate are interconnected and occur in several areas such as computational biology, discrete optimization, graph theory, logistics and economy. We expect that the research that will be conducted in this project will lead to relevant results, which will contribute to push forward the state of the art of the subject area. We also expect that this project will promote the academic formation of young researchers. Towards the end of the project, we envision an increase on the research activities in areas that are still little investigated in Brazil, but are intensively investigated in the main research centers abroad. (AU)
| Articles published in Agência FAPESP Newsletter about the research grant: |
| More itemsLess items |
| TITULO |
| Articles published in other media outlets ( ): |
| More itemsLess items |
| VEICULO: TITULO (DATA) |
| VEICULO: TITULO (DATA) |