On optimization problems in acyclic hypergraphs

DOI10.1016/j.ipl.2023.106390OpenAlexW4323671194MaRDI QIDQ6161450

Naoyuki Kamiyama

Publication date: 5 June 2023

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2023.106390

zbMATH Keywords

algorithmshypergraphbinary polynomial optimization\(\beta\)-acyclicity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Pseudo-Boolean optimization
• Algorithms for the maximum satisfiability problem
• On the notion of cycles in hypergraphs
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• The maximum clique problem
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• The basic algorithm for pseudo-Boolean programming revisited
• On characterization of maximal independent sets via quadratic optimization
• Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
• Degrees of acyclicity for hypergraphs and relational database schemes
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• LP Formulations for Polynomial Optimization Problems
• The Running Intersection Relaxation of the Multilinear Polytope

This page was built for publication: On optimization problems in acyclic hypergraphs