Seminários em Computação: Quadratizations of Pseudo-Boolean Functions (Aritanan Gruber)

• Responsável: CMCC - Centro de Matemática, Computação e Cognição
• Câmpus: Santo André
• Local: Bloco A, sala S-205-0
• Data: 26/07/2017
• Horário: 16:00 às 18:00
• Descrição:

  * Resumo: Pseudo-Boolean functions are real-valued mappings over the set of binary vectors, and it is well known that such functions admit unique representations as multi linear polynomials over their variables. The problem of minimizing pseudo-Boolean functions has received a lot of attention in the past five decades since it encompasses numerous optimization models, including the well-known MAX-SAT and MAX-CUT problems, and has applications in areas ranging from combinatorics to computational complexity to physics to computer vision. When the model or application leads to the minimization of a quadratic pseudo-Boolean function, the optimal solution can be efficiently obtained provided the function possesses the diminishing returns structure (i.e, submodularity). In the past decade, many applications of pseudo-Boolean optimization, especially those stemming from the machine learning and computer vision communities, require a higher-degree multilinear polynomial to capture the existing nuances, resulting in super-quadratic objective functions. In these cases, however, much fewer effective techniques are available. In particular, there is no analog to the persistencies provided by roof-duality for the quadratic case. The increased interest led to the study of methods to reduce higher-degree minimization problems to quadratic ones. In the span of six years, many techniques were developed to achieve that goal. We follow a global approach, considering all possible quadratizations of a given higher-degree pseudo-Boolean function. In fact, we consider several different types of quadratizations and provide sharp lower and upper bounds on the number of extra variables required to “quadratize” the function (Anthony, Boros, Crama, and Gruber, 2016, 2017). Our results give rise to new quadratization algorithms as well. We also report on some preliminary computational evaluations (Fix, Gruber, Boros, and Zabih, 2015). (Joint work with M. Anthony, E. Boros, and Y. Crama).

• Necessita inscrição: Não
• Link de divulgação: http://poscomp.ufabc.edu.br/seminarios-em-computacao/seminario-aritanan-gruber/
• Calendário do Google: https://www.google.com/calendar/event?ei ...

Para visualizar o calendário completo ou para solicitar divulgação de eventos, acesse aqui.