Pedigree Polytopes

This book defines and studies a combinatorial object called the pedigree and develops the theory for optimising a linear function over the convex hull of pedigrees (the Pedigree polytope). A strongly polynomial algorithm implementing the framework given in the book for checking membership in the pedigree polytope is a major contribution.

This book challenges the popularly held belief in computer sc...