Optimal Multimarginal Schrödinger Bridge: Minimum Spanning Tree over Measure-valued Vertices

• URL: http://arxiv.org/abs/2509.10626v1
• Date: Fri, 12 Sep 2025 18:15:42 GMT
• Title: Optimal Multimarginal Schrödinger Bridge: Minimum Spanning Tree over Measure-valued Vertices
• Authors: Georgiy A. Bondar, Abhishek Halder,
• Abstract summary: The Multimarginal Schr"odinger Bridge (MSB) finds the optimal coupling among a collection of random vectors with known statistics and a known correlation structure.<n>We find that computing the optimal MSB amounts to solving the minimum spanning tree problem over measure-valued vertices.
• Score: 0.15469452301122175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Multimarginal Schr\"odinger Bridge (MSB) finds the optimal coupling among a collection of random vectors with known statistics and a known correlation structure. In the MSB formulation, this correlation structure is specified \emph{a priori} as an undirected connected graph with measure-valued vertices. In this work, we formulate and solve the problem of finding the optimal MSB in the sense we seek the optimal coupling over all possible graph structures. We find that computing the optimal MSB amounts to solving the minimum spanning tree problem over measure-valued vertices. We show that the resulting problem can be solved in two steps. The first step constructs a complete graph with edge weight equal to a sum of the optimal value of the corresponding bimarginal SB and the entropies of the endpoints. The second step solves a standard minimum spanning tree problem over that complete weighted graph. Numerical experiments illustrate the proposed solution.

Related papers

• Precedence-Constrained Decision Trees and Coverings [0.8594140167290095]
  This work considers a number of optimization problems and reductive relations between them.<n>The two main problems we are interested in are the emph Optimal Decision Tree and emphSet Cover.
  arXiv  Detail & Related papers  (2026-02-24T19:33:36Z)
• Optimizing Cost Hamiltonian Compilation for Max-Cut QAOA on Unweighted Graphs Using Global Controls and Qubit Bit Flips [0.0]
  We study a cost Hamiltonian compilation problem for the quantum approximate optimization algorithm (QAOA) applied to the Max-Cut problem.<n>Instead of standard compilation with CNOT and Rz gates, we employ global coupling operations and single-qubit bit flips.
  arXiv  Detail & Related papers  (2025-08-29T18:12:20Z)
• Bounds on Perfect Node Classification: A Convex Graph Clustering Perspective [50.3088702686312]
  We present an analysis of the transductive node classification problem, where the underlying graph consists of communities that agree with the node labels and node features.<n>For node classification, we propose a novel optimization problem that incorporates the node-specific information in a spectral graph clustering framework.
  arXiv  Detail & Related papers  (2025-08-27T19:22:35Z)
• Improved Approximations for Hard Graph Problems using Predictions [13.827632579682795]
  We design improved approximation algorithms for NP-hard graph problems by incorporating predictions.<n>Our prediction model builds upon and extends the $varepsilon$-prediction framework by Cohen-Addad, d'Orsi, Gupta, Lee, and Panigrahi.
  arXiv  Detail & Related papers  (2025-05-29T19:47:09Z)
• On lower bounds of the density of planar periodic sets without unit distances [55.2480439325792]
  We introduce a novel approach to estimating $m_1(mathbbR2)$ by reformulating the problem as a Maximal Independent Set (MIS) problem on graphs constructed from flat torus.<n>Our experimental results, supported by theoretical justifications of proposed method, demonstrate that for a sufficiently wide range of parameters this approach does not improve the known lower bound.
  arXiv  Detail & Related papers  (2024-11-20T12:07:19Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  We tackle the problem of exactly recovering an unknown ground-truth binary labeling of the nodes from a single corrupted observation of each edge. We apply a hierarchy of relaxations known as the sum-of-squares hierarchy, to the problem. We show that the solution of the dual of the relaxed problem is related to finding edge weights of the Johnson and Kneser graphs.
  arXiv  Detail & Related papers  (2021-02-16T08:36:19Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples [6.810856082577402]
  The Quantum Approximate Optimization Algorithm can be applied to search problems on graphs with a cost function that is a sum of terms corresponding to the edges. We show that the QAOA with $(d-1)2p nA$ for any $A1$, can only achieve an approximation ratio of 1/2 for Max-Cut on bipartite random d-regular graphs for d large.
  arXiv  Detail & Related papers  (2020-05-18T14:23:09Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.