{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:55:55Z","timestamp":1742388955809},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2010,2]]},"abstract":"<jats:p> Earth mover's distance (EMD for short) is a perceptually meaningful dissimilarity measure between histograms. The computation of EMD reduces to a network flow optimization problem; however, it lays a heavy computational burden when the number of locations of histograms is large. In this paper, we address an efficient formulation for computing the exact EMD value. We prove that the EMD problem reduces to a problem with half the number of constraints regardless of the ground distance. We then propose a further reduced formula in which the number of variables is reduced from O(m<jats:sup>2<\/jats:sup>) to O(m) for histograms with m locations when the ground distance is derived from a graph with a homogeneous neighborhood structure. Specifically, EMD problems with L<jats:sub>1<\/jats:sub>, L<jats:sub>\u221e<\/jats:sub> and D-norm ground distances can be reduced in this manner. Some experiments show that the reduction helps compute the EMD efficiently. <\/jats:p>","DOI":"10.1142\/s0217595910002545","type":"journal-article","created":{"date-parts":[[2010,4,9]],"date-time":"2010-04-09T11:10:43Z","timestamp":1270811443000},"page":"39-54","source":"Crossref","is-referenced-by-count":3,"title":["METRIC-PRESERVING REDUCTION OF EARTH MOVER'S DISTANCE"],"prefix":"10.1142","volume":"27","author":[{"given":"YUICHI","family":"TAKANO","sequence":"first","affiliation":[{"name":"Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YOSHITSUGU","family":"YAMAMOTO","sequence":"additional","affiliation":[{"name":"Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"Network Flows","author":"Ahuja R. K.","year":"1993"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2006.11.006"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.12.007"},{"key":"rf6","first-page":"725","volume":"8","author":"Grauman K.","journal-title":"J. Machine Learning Research"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(02)00399-9"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1038\/44565"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1058"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1006\/cviu.2001.0934"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/0734-189X(85)90055-6"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595910002545","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:44:44Z","timestamp":1565131484000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595910002545"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2]]},"references-count":10,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1142\/S0217595910002545"],"URL":"https:\/\/doi.org\/10.1142\/s0217595910002545","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,2]]}}}