000			03830nam a22006015i 4500
001			978-981-19-9952-9
003			DE-He213
005			20240423125500.0
007			cr nn 008mamaa
008			230327s2023 si | s |||| 0|eng d
020			_a9789811999529 _9978-981-19-9952-9
024	7		_a10.1007/978-981-19-9952-9 _2doi
050		4	_aQA267.7
072		7	_aUYA _2bicssc
072		7	_aCOM014000 _2bisacsh
072		7	_aUYA _2thema
082	0	4	_a511.352 _223
100	1		_aArthanari, Tirukkattuppalli Subramanyam. _eauthor. _4aut _4http://id.loc.gov/vocabulary/relators/aut
245	1	0	_aPedigree Polytopes _h[electronic resource] : _bNew Insights on Computational Complexity of Combinatorial Optimisation Problems / _cby Tirukkattuppalli Subramanyam Arthanari.
250			_a1st ed. 2023.
264		1	_aSingapore : _bSpringer Nature Singapore : _bImprint: Springer, _c2023.
300			_aXXV, 221 p. 83 illus., 50 illus. in color. _bonline resource.
336			_atext _btxt _2rdacontent
337			_acomputer _bc _2rdamedia
338			_aonline resource _bcr _2rdacarrier
347			_atext file _bPDF _2rda
505	0		_aChapter 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.
520			_aThis 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 theseproofs 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.
650		0	_aComputational complexity.
650		0	_aMathematical optimization.
650		0	_aCalculus of variations.
650		0	_aAlgebraic fields.
650		0	_aPolynomials.
650		0	_aOperations research.
650		0	_aManagement science.
650	1	4	_aComputational Complexity.
650	2	4	_aOptimization.
650	2	4	_aCalculus of Variations and Optimization.
650	2	4	_aContinuous Optimization.
650	2	4	_aField Theory and Polynomials.
650	2	4	_aOperations Research, Management Science.
710	2		_aSpringerLink (Online service)
773	0		_tSpringer Nature eBook
776	0	8	_iPrinted edition: _z9789811999512
776	0	8	_iPrinted edition: _z9789811999536
776	0	8	_iPrinted edition: _z9789811999543
856	4	0	_uhttps://doi.org/10.1007/978-981-19-9952-9
912			_aZDB-2-SCS
912			_aZDB-2-SXCS
942			_cSPRINGER
999			_c178421 _d178421