.png){kind=icon}
返回
A problem reduction based approach to discrete optimization algorithm design
.png){kind=icon}
PRE
AI
DOI：10.1007/s00607-010-0085-0.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The paper presents a novel approach to formal algorithm design for a typical class of discrete optimization problems. Using a concise set of program calculation rules, our approach reduces a problem into subproblems with less complexity based on function decompositions, constructs the problem reduction graph that describes the recurrence relations between the problem and subproblems, from which a provably correct algorithm can be mechanically derived. Our approach covers a large variety of algorithms and bridges the relationship between conventional methods for designing efficient algorithms (including dynamic programming and greedy) and some effective methods for coping with intractability (including approximation and parameterization).
Keyword:
Discrete optimization
Program calculation
Problem reduction graph (PRG)
Algorithm design
期刊
C
IF:
2.8
论文数:
2.3K
被引数:
3.5K
机构
引用论文
.png){kind=icon}
分享收藏
分享收藏
查看更多内容