Better bounds for densities of distance-avoiding sets and better approximation algorithms for the maximum-cut problem

• Grant number: 16/21527-5
• Support Opportunities: Research Grants - Visiting Researcher Grant - International
• Start date: February 14, 2017
• End date: February 21, 2017
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Fernando Mario de Oliveira Filho
• Grantee: Fernando Mario de Oliveira Filho
• Visiting researcher: Frank Vallentin
• Visiting researcher institution: University of Cologne (UoC), Germany
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science, AP.TEM

Abstract

During his stay of 2 weeks, prof. Vallentin will collaborate with the host on at least two research problems: finding better upper bounds for the densities of distance-avoiding sets and finding better approximation algorithms for the maximum-cut problem. Prof. Vallentin will have the opportunity to present a seminar to the local Combinatorics and Optimization group, he will be able to interact with its members and to work with master's and PhD students of the host who currently work on the problems mentioned above. Moreover, prof. Vallentin will take part in the master's thesis defense of Fabrício Caluza Machado. (AU)