Eprint first made available on ORBi (E-prints, working papers and research blog)
Short Prime Quadratizations of Cubic Negative Monomials
Crama, Yves; Rodriguez Heck, Elisabeth
2014
 

Files


Full Text
Tech_Report_ERH_2014_05.pdf
Publisher postprint (130.68 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
integer programming; quadratic optimization
Abstract :
[en] Pseudo-Boolean functions naturally model problems in a number of different areas such as computer science, statistics, economics, operations research or computer vision, among others. Pseudo-Boolean optimization (PBO) is NP-hard, even for quadratic polynomial objective functions. However, much progress has been done in finding exact and heuristic algorithms for the quadratic case. Quadratizations are techniques aimed at reducing a general PBO problem to a quadratic polynomial one. Quadratizing single monomials is particularly interesting because it allows quadratizing any pseudo-Boolean function by termwise quadratization. A characterization of short quadratizations for negative monomials has been provided. In this report we present a proof of this characterization for the case of cubic monomials, which requires a different analysis than the case of higher degree.
Research center :
QuantOM - HEC - ULiège
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Crama, Yves  ;  Université de Liège - ULiège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Rodriguez Heck, Elisabeth ;  Université de Liège - ULiège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Language :
English
Title :
Short Prime Quadratizations of Cubic Negative Monomials
Publication date :
18 July 2014
Name of the research project :
PAI COMEX
Funders :
BELSPO - SPP Politique scientifique - Service Public Fédéral de Programmation Politique scientifique
Available on ORBi :
since 18 July 2014

Statistics


Number of views
144 (36 by ULiège)
Number of downloads
79 (13 by ULiège)

Bibliography


Similar publications



Contact ORBi