| Grant number: | 14/23269-8 |
| Support type: | Scholarships in Brazil - Post-Doctorate |
| Effective date (Start): | March 01, 2015 |
| Effective date (End): | February 28, 2017 |
| Field of knowledge: | Physical Sciences and Mathematics - Computer Science |
| Principal Investigator: | Carlos Eduardo Ferreira |
| Grantee: | Aritanan Borges Garcia Gruber |
| Home 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 Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case.Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision and machine learning, various techniques have been recently developed to reduce the general case to the quadratic one, at the cost of increasing the number of variables.The focus of this project is to further study and develop these quadratization approaches (from both theoretical and practical standpoints), and to investigate possible relations that they may have with other strategies that appear in the literature, like hierarchies of relaxations / extended formulations and sum-of-squares of polynomials. (AU) | |