Accelerating Dynamic Programs via Nested
Benders Decomposition with Application to
Multi-Person Pose Estimation
Abstract. We present a novel approach to solve dynamic programs
(DP), which are frequent in computer vision, on tree-structured graphs
with exponential node state space. Typical DP approaches have to enumerate the joint state space of two adjacent nodes on every edge of the
tree to compute the optimal messages. Here we propose an algorithm
based on Nested Benders Decomposition (NBD) that iteratively lowerbounds the message on every edge and promises to be far more efficient.
We apply our NBD algorithm along with a novel Minimum Weight Set
Packing (MWSP) formulation to a multi-person pose estimation problem. While our algorithm is provably optimal at termination it operates
in linear time for practical DP problems, gaining up to 500x speed up
over traditional DP algorithm which have polynomial complexity