On Quadratization of Pseudo-Boolean Functions
We survey current term-wise techniques for quadratizing high-degree pseudo-Boolean functions and introduce a new one, which allows multiple splits of terms. We also introduce the first aggregative approach, which splits a collection of terms based on their common parts.
Code (0)
등록된 구현이 없습니다.
Tasks
SurveySimilar Papers 제목 키워드 기반
Quadratization of Symmetric Pseudo-Boolean Functions
A pseudo-Boolean function is a real-valued function $f(x)=f(x_1,x_2,\ldots,x_n)$ of $n$ binary variables; that is, a mapping from $\{0,1\}^n$ to $\mathbb{R}$. For a pseudo-Boolean function $f(x)$ on $\{0,1\}^n$, we say t…
Quadratization in discrete optimization and quantum mechanics
A book about turning high-degree optimization problems into quadratic optimization problems that maintain the same global minimum (ground state). This book explores quadratizations for pseudo-Boolean optimization, pertur…
FormMerging variables: one technique of search in pseudo-Boolean optimization
In the present paper we describe new heuristic technique, which can be applied to the optimization of pseudo-Boolean functions including Black-Box functions. This technique is based on a simple procedure which consists i…
Learning pseudo-Boolean k-DNF and Submodular Functions
We prove that any submodular function f: {0,1}^n -> {0,1,...,k} can be represented as a pseudo-Boolean 2k-DNF formula. Pseudo-Boolean DNFs are a natural generalization of DNF representation for functions with integer ran…
2kLEMMAPAC learningSystematic and Efficient Construction of Quadratic Unconstrained Binary Optimization Forms for High-order and Dense Interactions
Quantum Annealing (QA) can efficiently solve combinatorial optimization problems whose objective functions are represented by Quadratic Unconstrained Binary Optimization (QUBO) formulations. For broader applicability of …
Combinatorial Optimization