Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks

DOI10.1137/22m1501787zbMath1527.90189arXiv2205.03718OpenAlexW4380434217MaRDI QIDQ6098526

Jingbo Liu, Xun Gao, Mikhail D. Lukin, Unnamed Author, Unnamed Author

Publication date: 14 June 2023

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationindependent setgeneric tensor networksolution space property

Mathematics Subject Classification ID

Graph polynomials (05C31) Combinatorial optimization (90C27) Enumerative problems (combinatorial problems) in algebraic geometry (14N10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tensor-Train Decomposition
• A practical introduction to tensor networks: Matrix product states and projected entangled pair states
• Tensor network contractions for \#SAT
• On the independence complex of square grids
• On generating all maximal independent sets
• Local algorithms for independent sets are half-optimal
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• On independent sets and bicliques in graphs
• The complexity of tropical matrix factorization
• Fast multiplication of large numbers
• A review on algorithms for maximum clique problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Julia: A Fresh Approach to Numerical Computing
• Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
• Anderson localization makes adiabatic quantum optimization fail
• Simulating Quantum Computation by Contracting Tensor Networks
• On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Introduction to Domination Polynomial of a Graph
• Algorithm 457: finding all cliques of an undirected graph
• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
• Limits of local algorithms over sparse random graphs

This page was built for publication: Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks