Article ID: | iaor2007904 |
Country: | Netherlands |
Volume: | 3 |
Issue: | 3 |
Start Page Number: | 220 |
End Page Number: | 229 |
Publication Date: | Sep 2006 |
Journal: | Discrete Optimization |
Authors: | Niedermeier Rolf, Betzler Nadja, Uhlmann Johannes |
Keywords: | programming: dynamic, sets |
We propose a simple and effective heuristic to save memory in dynamic programming on tree decompositions when solving graph optimization problems. The introduced ‘anchor technique’ is based on a tree-like set covering problem. We substantiate our findings by experimental results. Our strategy has negligible computational overhead concerning running time but achieves memory savings for nice tree decompositions and path decompositions between 60% and 98%.