DPA - A DETERMINISTIC APPROACH TO THE MAP PROBLEM

Deterministic pseudo-annealing (DPA) is a new deterministic optimizati on method for finding the maximum aposteriori (MAP) labeling in a Mark ov random held, in which the probability of a tentative labeling is ex tended to a merit function on continuous labelings. This function is m ade convvex by changing its definition domain. This unambiguous maximi zation problem is solved, and the solution is followed down to the ori ginal domain, yielding a good, if suboptimal, solution to the original labeling assignment problem. The performance of DPA is analyzed on ra ndomly weighted graphs.