CSC373H1 Study Guide - Final Guide: If And Only If, Malik, Poutine
Document Summary
Integer programming: more restricted version where all constants and variables are integers. Example: minimum vertex cover: given an undirected graph g = (v, e), identify a subset of vertices c that covers every edge (i. e. , each edge has at least one endpoint in c), with minimum size. This 0-1 integer program is completely equivalent to original problem, through correspondence: vi in cover i xi = 1. Unfortunately, integer programming (ip) is np-hard, so the problem cannot be solved in polytime this way. In the next lecture we will propose an algorithm to approximate the solution. Solution can be found in polytime, but may include fractional values of xi"s. Suppose the solution to the relaxed lp is x i for each variable xi. For i = 1, , n, let x0i = 1 if vi in c0; x0i = 0 otherwise. x01, , x0n is a.
