On the complexity of binary polynomial optimization over acyclic hypergraphs

DOI10.1007/s00453-022-01086-9arXiv2007.05861OpenAlexW4313421121MaRDI QIDQ6174810

Silvia Di Gregorio, Alberto Del Pia

Publication date: 17 August 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2007.05861

zbMATH Keywords

hardness of approximationacyclic hypergraphsstrongly polynomial-time algorithmbinary polynomial optimization

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

A polyhedral study of lifted multicuts

Cites Work

• Quadratization of symmetric pseudo-Boolean functions
• Satisfiability of acyclic and almost acyclic CNF formulas
• The unconstrained binary quadratic programming problem: a survey
• Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs
• Concave extensions for nonlinear 0-1 maximization problems
• Pseudo-Boolean optimization
• Noise stability of functions with low influences: invariance and optimality
• On the notion of cycles in hypergraphs
• A solvable case of quadratic 0-1 programming
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Some simplified NP-complete graph problems
• On decomposability of multilinear sets
• A class of valid inequalities for multilinear 0-1 optimization problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Berge-acyclic multilinear 0-1 optimization problems
• On the impact of running intersection inequalities for globally solving polynomial optimization problems
• The basic algorithm for pseudo-Boolean programming revisited
• Compact quadratizations for pseudo-Boolean functions
• On the Desirability of Acyclic Database Schemes
• Degrees of acyclicity for hypergraphs and relational database schemes
• Integer Programming
• Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
• On the power of unique 2-prover 1-round games
• L’algebre de Boole et ses applications en recherche operationnelle
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Gadgets, Approximation, and Linear Programming
• The Multilinear Polytope for Acyclic Hypergraphs
• LP Formulations for Polynomial Optimization Problems
• The Running Intersection Relaxation of the Multilinear Polytope
• Tight Cycle Relaxations for the Cut Polytope
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• A Polyhedral Study of Binary Polynomial Programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of binary polynomial optimization over acyclic hypergraphs