Pedigree polytopes : new insights on computational complexity of combinatorial optimization problems / Tirukkattuppalli Subramanyam Arthanari.
2023
QA691
Linked e-resources
Linked Resource
Online Access
Concurrent users
Unlimited
Authorized users
Authorized users
Document Delivery Supplied
Can lend chapters, not whole ebooks
Details
Title
Pedigree polytopes : new insights on computational complexity of combinatorial optimization problems / Tirukkattuppalli Subramanyam Arthanari.
Author
Arthanari, T. S., 1946-
ISBN
9789811999529 (electronic bk.)
981199952X (electronic bk.)
9811999511
9789811999512
981199952X (electronic bk.)
9811999511
9789811999512
Publication Details
Singapore : Springer, 2023.
Language
English
Description
1 online resource
Item Number
10.1007/978-981-19-9952-9 doi
Call Number
QA691
Dewey Decimal Classification
516/.158
Summary
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 the NP-complete class may not have a polynomial algorithm to solve. By showing STSP has a polynomial algorithm, this book settles the P vs NP question. This book has illustrative examples, figures, and easily accessible proofs for showing this unexpected result. This book introduces novel constructions and ideas previously not used in the literature. Another interesting feature of this book is it uses basic max-flow and linear multicommodity flow algorithms and concepts in these proofs establishing efficient membership checking for the pedigree polytope. Chapters 3-7 can be adopted to give a course on Efficient Combinatorial Optimization. This book is the culmination of the author's research that started in 1982 through a presentation on a new formulation of STSP at the XIth International Symposium on Mathematical Programming at Bonn.
Bibliography, etc. Note
Includes bibliographical references and index.
Access Note
Access limited to authorized users.
Source of Description
Online resource; title from PDF title page (SpringerLink, viewed April 11, 2023).
Available in Other Form
Print version: 9789811999512
Linked Resources
Online Access
Record Appears in
Online Resources > Ebooks
All Resources
All Resources
Table of Contents
Chapter 1: Prologue
Chapter 2: Notations, Definitions and Briefs
Chapter 3: Motivation for Studying Pedigrees
Chapter 4: Structure of the Pedigree Polytope
Chapter 5: Membership Checking in Pedigree Polytopes
Chapter 6: Computational Complexity of Membership Checking
Chapter 7: Efficient Checking of Membership in Pedigree Polytope and its Implications
Chapter 8: Epilogue.
Chapter 2: Notations, Definitions and Briefs
Chapter 3: Motivation for Studying Pedigrees
Chapter 4: Structure of the Pedigree Polytope
Chapter 5: Membership Checking in Pedigree Polytopes
Chapter 6: Computational Complexity of Membership Checking
Chapter 7: Efficient Checking of Membership in Pedigree Polytope and its Implications
Chapter 8: Epilogue.