Accelerating Dynamic Programs via Nested Benders Decomposition with Application to Multi-Person Pose Estimation

Shaofei Wang, Alexander Ihler, Konrad Kording, Julian Yarkony; Proceedings of the European Conference on Computer Vision (ECCV), 2018, pp. 652-666

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) which iteratively lower-bounds 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.