Quadratization of symmetric pseudo-Boolean functions

Autor(es)

Anthony, Martin ^[1] ; Boros, Endre ^{[2, 3]} ; Crama, Yves ^[4] ; Gruber, Aritanan ^[5]

Afiliação do(s) autor(es)

^[1] Univ London London Sch Econ & Polit Sci, Dept Math, London WC2A 2AE - England

^[2] Rutgers State Univ, MSIS, Piscataway, NJ 08855 - USA

^[3] Rutgers State Univ, RUTCOR, Piscataway, NJ 08855 - USA

^[4] Univ Liege, QuantOM, HEC Management Sch, B-4000 Liege - Belgium

^[5] Univ Sao Paulo, Inst Math & Stat, BR-05508 Sao Paulo - Brazil

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE APPLIED MATHEMATICS; v. 203, p. 1-12, APR 20 2016.
• Citações Web of Science: 5

Resumo

A pseudo-Boolean function is a real-valued function f (x) = f (x(1), x(2),center dot center dot center dot,x(n)) of n binary variables, that is, a mapping from [0, 1](n) to R. For a pseudo-Boolean function f (x) on [0, 1](n), we say that g (x, y) is a quadratization off if g(x, y) is a quadratic polynomial depending on x and on in auxiliary binary variables y(1), y(2),...,y(m) such that f (x) = min[g(x, y) : y is an element of [0,1](m)] for all x is an element of [0, 1](n). By means of quadratizations, minimization of f is reduced to minimization (over its extended set of variables) of the quadratic function g(x, y). This is of practical interest because minimization of quadratic functions has been thoroughly studied for the last few decades, and much progress has been made in solving such problems exactly or heuristically. A related paper by Anthony et al. (2015) initiated a systematic study of the minimum number of auxiliary y-variables required in a quadratization of an arbitrary function f (a natural question, since the complexity of minimizing the quadratic function g(x, y) depends, among other factors, on the number of binary variables). In this paper, we determine more precisely the number of auxiliary variables required by quadratizations of symmetric pseudo-Boolean functions f (x), those functions whose value depends only on the Hamming weight of the input x (the number of variables equal to 1). (C) 2016 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 14/23269-8 - Reformulações de problemas de otimização binária: algoritmos e complexidade
• Beneficiário: Aritanan Borges Garcia Gruber
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado