Efficiency Tradeoffs for Combinatorial Optimization Problems

理论计算机科学的基础学科之一是研究资源有限时的计算能力。事实上，许多现实生活中的优化问题，如果一个人假设无限的计算能力，例如，没有时间限制，以及参与进程的充分协调，就会承认易于描述和低效的算法解决方案。当一个人被限制使用有限资源的高效算法时，如何很好地解决这样的问题？

One of the fundamental subjects in Theoretical Computer Science is the study of computation capabilities when resources are limited. Indeed, many real-life optimization problems admit easy-to-describe and non-efficient algorithmic solutions if one assumes unlimited computation power, e.g. no restrictions in time, and full coordination of participating processes. How well can such a problem be solved when one is restricted to use efficient algorithms with limited resources?