Skip to content
Email: poscomp@ufabc.edu.br
facebook
twitter
youtube
instagram
linkedin
PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
  • Início
  • Sobre o programa
    • Apresentação
    • Objetivos e perfil
    • Estrutura do curso
    • Perguntas frequentes
    • Premiações e destaques
  • Processos seletivos
    • Mestrado e Doutorado
      • Resultados dos Processos Seletivos
    • Aluno especial
    • Mestrado Acadêmico para Inovação
    • Doutorado Acadêmico Industrial
    • Doutorado sanduiche
    • Pós-doutorado
    • Histórico de Processos Seletivos
  • Pesquisa
    • Linhas de pesquisa
    • Laboratórios
  • Docentes
  • Discentes
    • Disciplinas ofertadas
    • Dúvidas sobre matrículas em geral (alunos regulares)
    • Manual de sobrevivência
    • Bolsas de estudo
    • Proficiência em inglês e exame
    • Exame de qualificação
    • Defesa de dissertação ou tese
    • Bancas agendadas ↗
    • Código de ética da UFABC
    • Ex-alunos (Alumni)
  • Eventos
    • Seminários em computação
    • Workshops
    • Mini-Cursos
    • Histórico
  • Institucional
    • Coordenação
    • Documentos e normativas
    • Lista de orientandos por orientadores ↗
    • Dissertações e teses defendidas ↗
    • Calendário acadêmico ↗
    • Eleições para coordenação
    • (Re)Credenciamento de docentes
  • Pós-Graduação UFABC ↗
  • Social

Aritanan Gruber

Home > Seminários em computação > Aritanan Gruber

Aritanan Gruber

Posted on 19/07/201724/08/2021 by Coordenador
0

Título: Quadratizations of Pseudo-Boolean Functions

Palestrante: Aritanan Borges Garcia Gruber (CMCC-UFABC)

Data e local: Quarta-feira, 26 de julho, às 16h, Santo André, Bloco A, sala S-205-0.

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). When submodularity is absent, one of the most frequently used technique is based on roof-duality (Hamer, Hansen, and Simeone, 1984), which aims at finding in polynomial time a simpler form of the given quadratic minimization problem by fixing some of the variables at their provably optimum value (persistency) and decomposing the residual problem into variable disjoint smaller sub problems (Boros and Hammer, 1989). Evaluations on real and synthetic data have shown such method to be very effective, sometimes fixing up to 80-90% of the variables at their provably optimum value (Boros, Hammer, Sun, and Tavares, 2008).

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. Despite the apparent variety, they all share the common theme of being based on local transformations, and it is not at all clear how good those transformations are and how large the resulting quadratic problems can be.

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)

PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO

  • Início
  • Sobre o programa
  • Processos seletivos
  • Docentes
  • Discentes

Acesso rápido

  • Perguntas frequentes
  • Como chegar
  • Institucional

Translate

Contato e Endereço

Email: poscomp@ufabc.edu.br

Universidade Federal do ABC - UFABC

Endereço: Av dos Estados, 5001 - Bairro Bangu - Santo André - SP
CEP: 09210-580

© 2025 PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO | WordPress Theme: Enlighten
Translate »