算法设计中的矩形和贪婪的基础如何？

Question

最初， 矩形 被引入是为了概括一系列$ e $的线性独立概念，而不是某些地面套装$ i $。包含这种结构的某些问题允许贪婪算法找到最佳解决方案。概念 贪婪 后来引入以概括这种结构，以捕获更多的问题，这些问题允许通过贪婪的方法找到最佳的解决方案。

这些结构在算法设计中出现多久？

此外，贪婪的算法通常无法完全捕获找到最佳解决方案所需的内容，但仍可能找到非常好的近似解决方案（例如，bin填料）。鉴于这一点，是否有一种方法可以衡量一个问题是如何“关闭”的贪婪或矩阵？

Answer 1

很难回答“多久一次”的问题。但是，与所有“基础结构”一样，好处是因为人们意识到人们试图解决的根本问题具有矩形（或贪婪）结构。这不仅仅是矩形问题。矩阵交叉点问题具有特定的模型（两分匹配）。

尼克·哈维（Nick Harvey）获得了博士学位论文 最近，关于矩阵问题的算法，还相当考虑，还研究了函数优化（概括了矩阵问题）。阅读论文的引言和背景可能会有所帮助。