License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2019.6
URN: urn:nbn:de:0030-drops-100321
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10032/
Go to the corresponding OASIcs Volume Portal

Quanrud, Kent

Approximating Optimal Transport With Linear Programs

pdf-format:
OASIcs-SOSA-2019-6.pdf (0.4 MB)

Abstract

In the regime of bounded transportation costs, additive approximations for the optimal transport problem are reduced (rather simply) to relative approximations for positive linear programs, resulting in faster additive approximation algorithms for optimal transport.

BibTeX - Entry

@InProceedings{quanrud:OASIcs:2018:10032,
  author =	{Kent Quanrud},
  title =	{{Approximating Optimal Transport With Linear Programs}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{6:1--6:9},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{69},
  editor =	{Jeremy T. Fineman and Michael Mitzenmacher},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10032},
  URN =		{urn:nbn:de:0030-drops-100321},
  doi =		{10.4230/OASIcs.SOSA.2019.6},
  annote =	{Keywords: optimal transport, fast approximations, linear programming}
}

Keywords: optimal transport, fast approximations, linear programming
Collection: 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI