Students are finalists for national IC award in computing
The work was selected from 105 studies for the final phase of the SBC competition
Scientific paper, the result of research carried out by IMPA Tech students, was among the three best in Brazil and was selected for oral presentation at the Scientific Initiation Paper Competition (CTIC) of the Brazilian Computer Society (SBC), the most traditional competition in the field. The work was carried out collectively by students Alan Santos, Cristiane Sampaio, Felipe Ribeiro, Lucas Fraga, Marcelo Alves and Vinicius Prestes, under the guidance of teacher Uéverton Souza, during their directed studies of “Exponential Exact Algorithms”.
The article “On Computing a Minimal Maximal Set Cover: Exact Algorithms and Lower Bounds Based on (S)ETH” analyzes the computational limitations of solving a variant of the classic Set Cover, a fundamental problem in computing. The discussion began with a collective reading of chapters from the textbook Exact Exponential Algorithms, written by Fedor V. Fomin and Dieter Kratsch.
The group investigated a max-min version of a challenging minimization problem also known as “Set Coverage”, which consists of finding efficient combinations of data sets within a large volume of information. The aim was to create algorithms and mathematical solutions to solve the problem in the shortest possible time. While the classic problem consists of finding the smallest combination to cover all the elements provided, the research carried out analyzed the question of computing the maximum minimal combination to cover the elements, a natural variant for the subject.
“We investigated properties of Set Cover, Vertex Cover, Dominating Set and Upper Domination, which are cover problems in graphs and systems of sets. These are classic problems, which have many published studies, but we tackled a problem that didn’t have many studies, which is the Maximum Minimal Set Cover, and had an interesting opportunity to make advances. More specifically, we studied algorithms to identify this minimal maximal structure in any set system, and we came up with several results about which algorithm we can use,” explained Prestes, a student who will represent the team at CTIC.
As a result, the undergraduates managed to develop a solution that speeds up data processing and, more than that, proved mathematically what the insurmountable limits of this task are.
The CTIC selects exceptional works developed by undergraduate students, which are awarded prizes and published in the proceedings of the CSBC as well as in the SBC’s Electronic Journal of Scientific Initiation in Computing (REIC). of the SBC. The final phase of the competition, with the presentation of the article, will take place in July, in Gramado (RS), during the SBC Congress (CSBC), the main meeting of the Computing community in Latin America.
This year’s competition saw a record number of submissions, with 105 entries. “The selection was a big surprise. It’s the first time I’ve had an article published and chosen for a competition like this. It was nice to see that we managed to make a significant contribution to knowledge in some way,” said Prestes.
For Professor Uéverton, the level of scientific maturity demonstrated by the group was the big difference. “It’s quite an achievement. The students were always very critical and the research changed focus throughout the process. We discussed different possibilities and manipulated the problem in different ways, leading to non-trivial results,” he said.
