Theory and Approximate Solvers for Branched Optimal Transport with Multiple Sources

• URL: http://arxiv.org/abs/2210.07702v1
• Date: Fri, 14 Oct 2022 10:51:16 GMT
• Title: Theory and Approximate Solvers for Branched Optimal Transport with Multiple Sources
• Authors: Peter Lippmann, Enrique Fita Sanmart\'in, Fred A. Hamprecht
• Abstract summary: Branched Optimal Transport (BOT) is a generalization of optimal transport in which transportation costs along an edge are subadditive. We show how to efficiently find the best geometry of a BOT network for many sources and sinks, given a topology.
• Score: 12.139222986297263
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Branched Optimal Transport (BOT) is a generalization of optimal transport in which transportation costs along an edge are subadditive. This subadditivity models an increase in transport efficiency when shipping mass along the same route, favoring branched transportation networks. We here study the NP-hard optimization of BOT networks connecting a finite number of sources and sinks in $\mathbb{R}^2$. First, we show how to efficiently find the best geometry of a BOT network for many sources and sinks, given a topology. Second, we argue that a topology with more than three edges meeting at a branching point is never optimal. Third, we show that the results obtained for the Euclidean plane generalize directly to optimal transportation networks on two-dimensional Riemannian manifolds. Finally, we present a simple but effective approximate BOT solver combining geometric optimization with a combinatorial optimization of the network topology.

Related papers

• Improving Neural Optimal Transport via Displacement Interpolation [16.474572112062535]
  Optimal Transport (OT) theory investigates the cost-minimizing transport map that moves a source distribution to a target distribution. We propose a novel method to improve stability and achieve a better approximation of the OT Map by exploiting displacement. We demonstrate that DIOTM outperforms existing OT-based models on image-to-image translation tasks.
  arXiv  Detail & Related papers  (2024-10-03T16:42:23Z)
• Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently [14.262270388108112]
  We propose a new framework for formulating optimal transport distances between Markov chains. We show that calculating optimal transport distances in the full space of joint distributions can be equivalently formulated as solving a linear program.
  arXiv  Detail & Related papers  (2024-06-06T13:25:14Z)
• Fast 3D Molecule Generation via Unified Geometric Optimal Transport [25.89095414975696]
  This paper proposes a new 3D molecule generation framework, called GOAT, for fast and effective 3D molecule generation. We formulate a geometric transport formula for measuring the cost of mapping multi-modal features between a base distribution and a target data distribution. Our formula is solved within a unified, equivalent, and smooth representation space.
  arXiv  Detail & Related papers  (2024-05-24T06:22:01Z)
• Heuristic Optimal Transport in Branching Networks [0.0]
  We discuss a fast branching method for optimal transport in networks. We also provide several applications to synthetic examples, a simplified cardiovascular network, and the "Santa Claus" distribution network which includes 141,182 cities around the world.
  arXiv  Detail & Related papers  (2023-11-11T19:39:50Z)
• A Computational Framework for Solving Wasserstein Lagrangian Flows [48.87656245464521]
  In general, the optimal density path is unknown, and solving these variational problems can be computationally challenging. We propose a novel deep learning based framework approaching all of these problems from a unified perspective. We showcase the versatility of the proposed framework by outperforming previous approaches for the single-cell trajectory inference.
  arXiv  Detail & Related papers  (2023-10-16T17:59:54Z)
• Hierarchical Multi-Marginal Optimal Transport for Network Alignment [52.206006379563306]
  Multi-network alignment is an essential prerequisite for joint learning on multiple networks. We propose a hierarchical multi-marginal optimal transport framework named HOT for multi-network alignment. Our proposed HOT achieves significant improvements over the state-of-the-art in both effectiveness and scalability.
  arXiv  Detail & Related papers  (2023-10-06T02:35:35Z)
• Unpaired Image Super-Resolution with Optimal Transport Maps [128.1189695209663]
  Real-world image super-resolution (SR) tasks often do not have paired datasets limiting the application of supervised techniques. We propose an algorithm for unpaired SR which learns an unbiased OT map for the perceptual transport cost. Our algorithm provides nearly state-of-the-art performance on the large-scale unpaired AIM-19 dataset.
  arXiv  Detail & Related papers  (2022-02-02T16:21:20Z)
• Score-based Generative Neural Networks for Large-Scale Optimal Transport [15.666205208594565]
  In certain cases, the optimal transport plan takes the form of a one-to-one mapping from the source support to the target support. We study instead the Sinkhorn problem, a regularized form of optimal transport whose solutions are couplings between the source and the target distribution. We introduce a novel framework for learning the Sinkhorn coupling between two distributions in the form of a score-based generative model.
  arXiv  Detail & Related papers  (2021-10-07T07:45:39Z)
• Optimal transport in multilayer networks [68.8204255655161]
  We propose a model where optimal flows on different layers contribute differently to the total cost to be minimized. As an application, we consider transportation networks, where each layer is associated to a different transportation system. We show an example of this result on the real 2-layer network of the city of Bordeaux with bus and tram, where in certain regimes the presence of the tram network significantly unburdens the traffic on the road network.
  arXiv  Detail & Related papers  (2021-06-14T07:33:09Z)
• Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark [133.46066694893318]
  We evaluate the performance of neural network-based solvers for optimal transport. We find that existing solvers do not recover optimal transport maps even though they perform well in downstream tasks.
  arXiv  Detail & Related papers  (2021-06-03T15:59:28Z)
• Joint Multi-Dimension Pruning via Numerical Gradient Update [120.59697866489668]
  We present joint multi-dimension pruning (abbreviated as JointPruning), an effective method of pruning a network on three crucial aspects: spatial, depth and channel simultaneously. We show that our method is optimized collaboratively across the three dimensions in a single end-to-end training and it is more efficient than the previous exhaustive methods.
  arXiv  Detail & Related papers  (2020-05-18T17:57:09Z)

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.