Coarse-to-Fine Dynamic Programming Export

@article{citeulike:5810927, abstract = {We introduce an extension of dynamic programming (DP) we call "Coarse-to-Fine Dynamic Programming" (CFDP), ideally suited to DP problems with large state space. CFDP uses dynamic programming to solve a sequence of coarse approximations which are lower bounds to the original DP problem. These approximations are developed by merging states in the original graph into "superstates" in a coarser graph which uses an optimistic arc cost between superstates. The approximations are designed so that when CFDP terminates the optimal path through the original state graph has been found. CFDP leads to significant decreases in the amount of computation necessary to solve many DP problems and can, in some instances, make otherwise infeasible computations possible. CFDP generalizes to DP problems with continuous state space and we offer a convergence result for this extension. The computation of the approximations requires that we bound the arc cost over all possible arcs associated with an adjacent pair of superstates; thus the feasibility of our proposed method requires the identification of such a lower bound. We demonstrate applications of this technique to optimization of functions and boundary estimation in mine recognition.}, address = {Los Alamitos, CA, USA}, author = {Raphael, C.}, citeulike-article-id = {5810927}, citeulike-linkout-0 = {http://doi.ieeecomputersociety.org/10.1109/34.977562}, citeulike-linkout-1 = {http://dx.doi.org/10.1109/34.977562}, doi = {10.1109/34.977562}, issn = {0162-8828}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, keywords = {compbio, dynamic\_programming, graphicalmodels, hmm, probabilistic}, number = {12}, pages = {1379--1390}, posted-at = {2009-09-21 07:13:32}, priority = {0}, publisher = {IEEE Computer Society}, title = {Coarse-to-Fine Dynamic Programming}, url = {http://dx.doi.org/10.1109/34.977562}, volume = {23}, year = {2001} }

TY - JOUR ID - citeulike:5810927 L3 - citeulike-article-id:5810927 N2 - We introduce an extension of dynamic programming (DP) we call "Coarse-to-Fine Dynamic Programming" (CFDP), ideally suited to DP problems with large state space. CFDP uses dynamic programming to solve a sequence of coarse approximations which are lower bounds to the original DP problem. These approximations are developed by merging states in the original graph into "superstates" in a coarser graph which uses an optimistic arc cost between superstates. The approximations are designed so that when CFDP terminates the optimal path through the original state graph has been found. CFDP leads to significant decreases in the amount of computation necessary to solve many DP problems and can, in some instances, make otherwise infeasible computations possible. CFDP generalizes to DP problems with continuous state space and we offer a convergence result for this extension. The computation of the approximations requires that we bound the arc cost over all possible arcs associated with an adjacent pair of superstates; thus the feasibility of our proposed method requires the identification of such a lower bound. We demonstrate applications of this technique to optimization of functions and boundary estimation in mine recognition. IS - 12 JF - IEEE Transactions on Pattern Analysis and Machine Intelligence SN - 0162-8828 AD - Los Alamitos, CA, USA EP - 1390 TI - Coarse-to-Fine Dynamic Programming PB - IEEE Computer Society VL - 23 SP - 1379 KW - compbio KW - dynamic_programming KW - graphicalmodels KW - hmm KW - probabilistic AU - Raphael, C PY - 2001/// UR - http://dx.doi.org/10.1109/34.977562 ER -