Review of Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics by Juraj Hromkovič. Springer 2001
Review of Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics by Juraj Hromkovič. Springer 2001
复制标题
困难问题的算法回顾：组合优化、随机化、近似和启发式介绍，作者：Juraj Hromkovič，2001 年。
DOI：
10.1145/882116.882121
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
H. Masum
中科院分区：
文献类型：
--
作者：
H. Masum
1概述《困难问题的解决方案》是一本有趣的新书，试图填补一个不足的利基：实用的方法来解决那些讨厌的NP难问题，但仍然必须处理。总的来说，这本书写得很好，对各种各样的算法方法进行了有益的介绍。本专栏的许多读者可能会发现它是一个方便的集合，收集了重要的想法，否则可能会分散在各种来源。虽然不是高级文本或全面的参考，但即使对于那些已经了解大部分设计方法的人来说，它也可能是一个方便的复习资料。由于各章相对独立，我将穿插章节具体的评论与本书的逐章内容列表：1）介绍。通过预览本书其余部分所涵盖的主题并讨论动机和目标来设置舞台。这本书的目标有一个有趣的“投入-约束-成本-目标”的表述。大多数目标都实现了，但有一些需要注意的地方。在介绍性说明中，针对本书的粗略版本提到了高年级本科生和研究生的目标受众;然而，通过增加更多的练习（和一些解决方案），可以提高课堂的相关性。2)基本概念。数学基础（线性代数，组合数学，布尔函数，数论，概率）和算法（语言，问题规范，复杂性理论，设计范式）。460页非索引页中有132页是关于数学和复杂性理论的。虽然这对于本专栏的读者来说是多余的，但对于没有很强的理论背景的学生和面向应用程序的用户来说可能是有帮助的。虽然这一部分写得很好，但它确实看起来像是投入到基础知识中的过多空间。我会建议作者需要更好地关注他的目标受众-如果
1 Overview Algorithmics for Hard Problems is an intriguing new book that attempts to fill an underserved niche: practical methods for attacking those pesky problems that are NP-hard but must nevertheless be dealt with. On the whole, the book is well-written and forms a useful introduction to a wide variety of algorithmic methods. Many readers of this column may find it a handy collection, collecting important ideas that might otherwise be scattered across a variety of sources. While not an advanced text or comprehensive reference, it may prove a handy refresher even for those who already know most of the design methods. Since the chapters are relatively self-contained, I will intersperse chapter-specific comments with a chapter-by-chapter contents listing of the book: 1) Introduction. Setting the stage via previewing the topics covered in the rest of the book and discussing motivation and aims. There is an amusing "input-constraints-cost-objective" formulation of the goals of the book. Most of the goals are achieved, with some caveats. In the introductory notes, a target audience of senior undergraduate and graduate students is mentioned for the rough versions of the book; however, the relevance for the classroom could be improved by including more exercises (and some solutions). 2) Basic Concepts. Fundamentals of math (linear algebra, combinatorics, Boolean functions , number theory, probability) and algorithms (languages, problem specification, complexity theory, design paradigms). 132 of 460 non-index pages are devoted to background mathematics and complexity theory. While largely superfluous for readers of this column, this could be helpful for students and application-oriented users without a strong theory background. Although the section is well-written, it does seem like an excessive amount of space to devote to elementary knowledge. I would suggest that the author needs to focus on his target audience a little better-if