Optimal transport : Theory and Applications
to cosmological Reconstruction and Image processing

Names of participants of the OTARIE project are underlined.


Author: G. Lavaux

MiniAuction is a slimmed version of the forthcoming full MAK (Monge–Ampère–Kantorovich) package. It is written in C++ and has support both for serial and MPI parallelization. The package comes with documentation and samples for the two algorithms. This package does not come with the mesh element generator. These belongs to the full MAK package that will be released later on. The current version is 1.0.

This project started as a rewrite of the Fortran code originally developed by M. Hénon in Fortran, based on an implementation of the auction algorithm by Dimitri Bertsekas. That code was never made public.

Download the MiniAuction code and documentation from the web page of the author.

Weighted nearest neighbor search

Authors: A. Andrievski, A. Sobolevski

WANN (Weighted Approximate Nearest Neighbors) is a library of C++ classes for weighted nearest neighbor search: given the set P of points p1, p2, …, pN endowed with weights w1, w2, …, wN and a query point q, find pk such that |q - pk|2 +wk is minimal. This problem arises as a building block in solution of the discrete optimal transport problem, where weights appear as dual variables of the corresponding linear program, but it is general enough to warrant a separate piece of software.

The WANN library is based on the ANN library of D. Mount and S. Arya and generalizes their implementation of nearest neighbor search (all wk = 0) to the weighted case. The code works for nearest neighbors both in open space and on a flat torus.

WANN is part of a multipurpose library for numerical transport optimization developed in the OTARIE project. It is licensed under LGPL.

Download a pre-release version of the WANN library, version 0.2 (beta, 1.07 MB), or its description in PDF.

The development of WANN has been co-supported by RFBR under project 07-01-922127-CNRSL-a.

Fast optimal transport on the circle

Author: J Salomon.

A Matlab implementation of the algorithm proposed in the preprint of J. Delon, J. Salomon and A. Sobolevski (2009), see the publications page.

Download the code (gzipped tar archive).

Last modified: Mon Jun 22 17:04:41 CEST 2009