کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
417873 | 681587 | 2016 | 12 صفحه PDF | دانلود رایگان |
A pseudo-Boolean function is a real-valued function f(x)=f(x1,x2,…,xn)f(x)=f(x1,x2,…,xn) of nn binary variables, that is, a mapping from {0,1}n{0,1}n to RR. For a pseudo-Boolean function f(x)f(x) on {0,1}n{0,1}n, we say that g(x,y)g(x,y) is a quadratization of ff if g(x,y)g(x,y) is a quadratic polynomial depending on xx and on mmauxiliary binary variables y1,y2,…,ymy1,y2,…,ym such that f(x)=min{g(x,y):y∈{0,1}m}f(x)=min{g(x,y):y∈{0,1}m} for all x∈{0,1}nx∈{0,1}n. By means of quadratizations, minimization of ff is reduced to minimization (over its extended set of variables) of the quadratic function g(x,y)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 yy-variables required in a quadratization of an arbitrary function ff (a natural question, since the complexity of minimizing the quadratic function g(x,y)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)f(x), those functions whose value depends only on the Hamming weight of the input xx (the number of variables equal to 1).
Journal: Discrete Applied Mathematics - Volume 203, 20 April 2016, Pages 1–12