License
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://drops.dagstuhl.de/opus/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
Seminar: 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Issue Date: 2018
Date of publication: 18.12.2018


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