Approximation Algorithms and Linear Programming

This course continues our data structures and algorithms specialization by focussing on the use of linear and integer programming formulations for solving algorithmic problems that seek optimal solutions to problems arising from domains such as resource allocation, scheduling, task assignment, and variants of the traveling salesperson problem. Next, we will study algorithms for NP-hard problems whose solutions are guaranteed to be within some approximation factor of the best possible solutions. Such algorithms are often quite efficient and provide useful bounds on the optimal solutions. The learning will be supported by instructor provided notes, readings from textbooks and assignments. Assignments will include conceptual multiple-choice questions as well as problem solving assignments that will involve programming and testing algorithms. This course can be taken for academic credit as part of CU Boulder’s Masters of Science in Computer Science (MS-CS) degrees offered on the Coursera platform. This fully accredited graduate degree offer targeted courses, short 8-week sessions, and pay-as-you-go tuition. Admission is based on performance in three preliminary courses, not academic history. CU degrees on Coursera are ideal for recent graduates or working professionals. Learn more: MS in Computer Science: https://coursera.org/degrees/ms-computer-science-boulder

• Linear Programming
• This module introduces the basics of linear programs and shows how some algorithm problems (such as the network flow problem) can be posed as a linear program. We will provide hands-on tutorials on how to pose and solve a linear programming problem in Python. Finally, we will provide a brief overview of linear programming algorithms including the famous Simplex algorithm for solving linear programs. The problem set will guide you towards posing and solving some interesting problems such as a financial portfolio problem and the optimal transportation problem as linear programs.
• Integer Linear Programming
• This module will cover integer linear programming and its use in solving NP-hard (combinatorial optimization) problems. We will cover some examples of what integer linear programming is by formulating problems such as Knapsack, Vertex Cover and Graph Coloring. Next, we will study the concept of integrality gap and look at the special case of integrality gap for vertex cover problems. We will conclude with a tutorial on formulating and solving integer linear programs using the python library Pulp.
• Approximation Algorithms : Scheduling, Vertex Cover and MAX-SAT
• We will introduce approximation algorithms for solving NP-hard problems. These algorithms are fast (often greedy algorithms) that may not produce an optimal solution but guarantees that its solution is not "too far away" from the best possible. We will present some of these algorithms starting from a basic introduction to the concepts involved followed by a series of approximation algorithms for scheduling problems, vertex cover problem and the maximum satisfiability problem.
• Travelling Salesperson Problem (TSP) and Approximation Schemes
• We will present the travelling salesperson problem (TSP): a very important and widely applicable combinatorial optimization problem, its NP-hardness and the hardness of approximating a general TSP with a constant factor. We present integer linear programming formulation and a simple yet elegant dynamic programming algorithm. We will present a 3/2 factor approximation algorithm by Christofides and discuss some heuristic approaches for solving TSPs. We will conclude by presenting approximation schemes for the knapsack problem.