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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The simplified Wasserstein barycenter problem consists in selecting one pointfrom $k$ given sets, each set consisting of $n$ points, with the aim ofminimizing the sum of distances to the barycenter of the $k$ points chosen.This problem is known to be NP-hard. We compute the Wasserstein barycenter byexploiting the Euclidean distance matrix structure to obtain a facially reduceddoubly nonnegative relaxation (DNN). The facial reduction provides a naturalsplitting for applying the symmetric alternating directions method ofmultipliers (sADMM) to the DNN relaxation. The sADMM method exploits structurein the subproblems to find strong upper and lower bounds.  The purpose of this paper is twofold. First we want to illustrate thestrength of this DNN relaxation with a splitting approach. Our numerical teststhen illustrate the surprising success on random problems, as we generally,efficiently, find the provable exact solution of this NP-hard problem.Comparisons with current commercial software illustrate this surprisingefficiency. However, we demonstrate and prove that there is a duality gap forproblems with enough multiple optimal solutions, and that this arises fromproblems with highly symmetrized structure.

Exact Solutions for the NP-hard Wasserstein Barycenter Problem using a Doubly Nonnegative Relaxation and a Splitting Method