English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Solving linear programs by using entropic penalization has recently attractednew interest in the optimization community, since this strategy forms the basisfor the fastest-known algorithms for the optimal transport problem, with manyapplications in modern large-scale machine learning. Crucial to theseapplications has been an analysis of how quickly solutions to the penalizedprogram approach true optima to the original linear program. More than 20 yearsago, Cominetti and San Mart\'in showed that this convergence is exponentiallyfast; however, their proof is asymptotic and does not give any indication ofhow accurately the entropic program approximates the original program for anyparticular choice of the penalization parameter. We close this long-standinggap in the literature regarding entropic penalization by giving a new proof ofthe exponential convergence, valid for any linear program. Our proof isnon-asymptotic, yields explicit constants, and has the virtue of beingextremely simple. We provide matching lower bounds and show that the entropicapproach does not lead to a near-linear time approximation scheme for thelinear assignment problem.

An explicit analysis of the entropic penalty in linear programming