Spanning tree constrained determinantal point processes are hard to (approximately) evaluate

DOI10.1016/j.orl.2021.02.004OpenAlexW3132144444MaRDI QIDQ2060533

Tatsuya Matsuoka, Naoto Ohsaka

Publication date: 13 December 2021

Published in: Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

spanning treedeterminantal point processnormalizing constant\#P-hardness

Mathematics Subject Classification ID

Computer science (68-XX) Linear and multilinear algebra; matrix theory (15-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Random generation of combinatorial structures from a uniform distribution
• Approximating the permanent of graphs with large factors
• A partial k-arboretum of graphs with bounded treewidth
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• The relative complexity of approximate counting problems
• Eynard-Mehta theorem, Schur process, and their Pfaffian analogs
• Determinantal Point Processes for Machine Learning
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Graph minors. II. Algorithmic aspects of tree-width
• The coincidence approach to stochastic point processes
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
• On the Complexity of Constrained Determinantal Point Processes
• A general framework for graph sparsification
• Mathematical Foundations of Computer Science 2005
• Parameterized Algorithms
• Systems of distinct representatives and linear algebra
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic