In search of perfect algorithms

Scientists and students from 20 countries took part in advanced courses on algorithms, combinatorics and optimization

By Diego Freire  |  Agência FAPESP – Algorithms are a key component of practically every type of technology in use today, from the GPS and satellite navigation systems in cars and smartphones to the complex software that controls a Mars space probe. These mathematical “recipes” that comprise a self-contained step-by-step set of operations to be performed by a machine or device are an object of study for scientists in different areas associated with computer science. A number of them assembled on July 18-29 in Brazil to participate in the São Paulo School of Advanced Science on Algorithms, Combinatorics & Optimization.

Organized by the Computer Science Department at the University of São Paulo’s Mathematics & Statistics Institute (IME-USP) with support from FAPESP’s São Paulo School of Advanced Science Program (SPSAS), the event offered 150 young researchers and students from institutions in 20 countries courses, presentations and other activities involving algorithms, combinatorics and optimization, all of which are interrelated branches of mathematics and computer science with numerous technological applications.

“Algorithms are finite sequences of instructions for the performance of specific activities, while combinatorics and optimization deal with the possible permutations to solve problems and the selection of the most efficient solution respectively. In their home countries and institutions, the researchers selected for SPSAS work with algorithms to meet the increasingly varied and growing global demand for this kind of technology, which requires the development of new techniques to solve increasingly complex problems,” said Yoshiko Wakabayashi (http://www.bv.fapesp.br/en/pesquisador/31598/), academic director of the course.

Wakabayashi is one of the co-principal investigators for the Thematic Project “Combinatorial structures, optimization, and algorithms in theoretical computer science”, which is supported by FAPESP. The purpose of the project is to develop new algorithms and strategies for solutions to problems in different knowledge areas.

This was how her group achieved progress with the treatment of a persistent problem in the analysis of phylogenetic trees, which are branching diagrams that plot the evolutionary relationships among various biological species or other entities that may have a common ancestor.

“Phylogenetic trees are represented by graphs, sets of points called vertices connected by edges, which mathematically model any number of phenomena – in the case of our study, the traits shared by individuals of the same species. By analyzing the relationships between the vertices and edges you can discover mathematically whether there is a biological chain that points to kinship between individuals, for example,” said Karla Roberta Pereira Sampaio Lima, a researcher at the University of São Paulo’s School of Arts, Sciences & Humanities (EACH-USP).

Computer-based analysis of these relationships is no easy task. Analyzing a graph with 50 vertices – 50 individuals of the same species in the case of a phylogenetic tree – would normally take around 17 hours and answer only one question about the relationships involved. The researchers used programming techniques and optimization methods to speed the process up, eliminating uninteresting solutions and ensuring the system focused on optimal answers.

Experiments showed that an algorithm developed for the research project can be used to solve graphs with 1,500 vertices in 40 minutes. This performance is far superior to those of other algorithms reported in the literature. An article with the results has been published by Manoel Campêlo, Alexandre S. Freire, Karla R. Lima, Phablo F. S. Moura and Yoshiko Wakabayashi in the journal Mathematical Programming and can be viewed at http://link.springer.com/article/10.1007%2Fs10107-015-0880-7.

The secretary problem

Computer science has a problem, according to the experts. Several, in fact, but one in particular, the “P versus NP” problem. A solution to this problem would help solve the rest more efficiently. Basically the P versus NP problem asks which computational problems can be solved efficiently by “smart” algorithms (P) and which ones can apparently be solved only by testing the possible answers one by one (NP).

The approach developed at IME-USP tackles the analysis of a phylogenetic tree by using “smart” algorithms to eliminate the possible answers that have no chance of being the best solution.

“We’re talking about an effort by many researchers who are working on solutions to problems for which no efficient algorithms are known at this time. Whenever a researcher discovers an efficient solution, the number of problems known to be in class P increases, showing that there can be efficient solutions to certain computational problems,” said Yoshiharu Kohayakawa, also affiliated with IME-USP and a member of the organizing committee for the São Paulo School of Advanced Science on Algorithms, Combinatorics & Optimization.

Another participant was Robert Kleinberg from Cornell University in New York State, USA, one of the most eminent researchers at work on optimal solutions to complex problems. During SPSAS Kleinberg taught a course on combinatorial stochastic search and selection, a mathematical field that includes the modeling of systems with random but probabilistic behavior.

“The course focused on problems that involve designing algorithms for decision making in situations of uncertainty about future entries and combinatorial constraints. An example of this is the classic ‘secretary problem’, extensively studied in applied probability, statistics and decision theory,” Kleinberg said.

The problem imagines a situation in which an executive who wants to hire a secretary is interviewing applicants and aims to hire the best candidate of all but has to decide about each candidate immediately after the interview. Rejected applicants cannot be recalled. Candidates can be ranked by comparison with those interviewed previously but the executive cannot know in advance about the qualifications of those who have yet to be interviewed.

“So what strategies can be chosen to know when to stop interviewing without decreasing the probability that you will select the best candidate? If the decision could be delayed until all applicants had been interviewed, it would be easy to design an algorithm to arrive at the optimal answer because you could assume all the candidates’ qualifications would be known,” Kleinberg said. “If the secretary has to be hired immediately, the optimal algorithm will select the best candidate based on the number of interviews yet to be held. If you interview only three candidates, the best solution is to base your decision on the second. If this candidate is better than the first, you hire her, and if not you hire the third and last candidate. If there are five applicants for the job, you need to wait until the third to begin forming your decision, and so on.”

Kleinberg’s course and those taught by other researchers at the SPSAS took place at the University of São Paulo’s Center for International Diffusion.

“This São Paulo School of Advanced Science is one more effort by FAPESP to promote interaction between researchers and institutions in São Paulo State and the international scientific community,” said Carlos Henrique Brito Cruz, FAPESP’s Scientific Director, during the opening ceremony. “The goal is to present leading local contributions to the world, highlight the potential to be developed, and attract brilliant young researchers from all continents to collaborate with colleagues here.”

Also speaking at the opening, University of São Paulo Rector Marco Antonio Zago stressed the importance of the event for stimulating scientific exchange. “FAPESP helps make academia and research in São Paulo State even more diverse by supporting such courses and also offering other forms of support. The University of São Paulo is delighted to welcome you with open arms,” Zago said.

In addition to Zago and Brito Cruz, the participants in the opening ceremony also included IME-USP Director Clodoaldo Grotta Ragazzo, Marcelo Viana, Director General of the National Institute of Pure & Applied Mathematics (IMPA), and Roberto Marcondes César Junior, a member of FAPESP’s Adjunct Panel for Physics, Mathematics, Chemistry and Engineering.

More information on the São Paulo School of Advanced Science on Algorithms, Combinatorics & Optimization (SPSAS) is available at http://sp-school2016.ime.usp.br.