Felzenszwalb, Pedro F.McAuley, Julian2015-12-100162-8828http://hdl.handle.net/1885/52265The MAP inference problem in many graphical models can be solved efficiently using a fast algorithm for computing min-sum products of n × n matrices. The class of models in question includes cyclic and skip-chain models that arise in many applications. AKeywords: Expected time; Fast algorithms; Fast inference; GraphicaL model; Inference problem; Input matrices; Matrix products; Min-sum; NAtural language processing; Performance Gain; Product operations; Uniform distribution; Worst-case complexity; Algorithms; Compu Graphical models; MAP inference; min-sum matrix product201110.1109/TPAMI.2011.1212016-02-24