@Article{Werner-Kiev-2011,
  IS = { zkontrolovano 10 Jan 2012 },
  UPDATE  = { 2011-12-29 },
  author =     {Werner, Tom{\'a}{\v s}},
  title    =   {How to Compute Primal Solution from Dual One in LP 
                Relaxation of MAP Inference in MRF? },
  year =       {2011},
  month =      {March--April},
  pages =      {86--93},
  journal =    {Control Systems and Computers},
  publisher =  {National Academy of Sciences of Ukraine},
  address =    {Kiev, Ukraine},
  issn =       {0130-5395},
  volume =     {2011},
  number =     {2},
  authorship = {100},
  annote = {In LP relaxation of MAP inference in Markov random
    fields (MRF), the primal LP maximizes the MAP objective over
    relaxed labelings (pseudomarginals) and the dual LP minimizes an
    upper bound on the true MAP solution by
    reparameterizations. Having solved the dual~LP, we have no direct
    access to the corresponding primal solution. We propose a simple
    way to compute an optimal primal solution from an optimal dual
    solution. Precisely, we given an algorithm that either shows that
    the upper bound for a given problem can be further decreased by
    reparameterizations (i.e., it is not dual-optimal) or computes the
    corresponding optimal relaxed labeling.  This is done by first
    removing inactive dual constraints and then solving the resulting
    feasibility problem by a very simple message-passing algorithm,
    sum-product diffusion.},
  keywords =   {weighted constraint satisfaction, arc consistency, 
                Markov random fields },
  project =    {FP7-ICT-247022 MASH only EU, MSM6840770038},
  psurl  = { [PDF]},
}