Combinatorial optimization (CO) plays a vital role in many areas of operations research and computer science. However, many of the natural CO problems that arise are known to be NP-hard, so hope for polynomial-time algorithms is slim. By easing the requirement of finding true optimal solutions, approximation algorithms provide a framework for balancing optimality and runtime. But how does one construct and estimate performance of approximation algorithms? To answer this question, we will apply methods and theory from Linear Programming, such as relaxation and duality theory, to construct approximation algorithms for various graph theoretic CO problems.

Though this talk is in person in Hylan 105, it might be streamed also in Zoom meeting room 986 2892 7517