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 science that a problem included in theNP-completeclass may not have a polynomial algorithm to solve. By showingSTSPhas a polynomial algorithm, this book settles thePvsNPquestion.This book has...
This book defines and studies a combinatorial object called the pedigree and develops the theory for optimising a linear function over the convex hull...
