Understanding and Using Linear Programming I: Integral Bipartite Matchings, Total Unimodularity and König's TheoremTextbook
Many combinatorial optimization problems are integer programs: linear objectives and linear constraints, with the extra requirement that the variables be integers. Dropping that requirement gives the LP relaxation, which is solvable efficiently but in general only bounds the integer optimum. For a small but important class of problems the relaxation loses…