000			03134nam a22003735i 4500
999			_c398141 _d398141 _x1
001			398141
003			ES-MaUEC
005			20240429180338.0
006			a||||fo|||| 00| 0
007			cr nn 008mamaa
008			230327s2023 si | o |||| 0|eng d
020			_a9789811999529
024	7		_a10.1007/978-981-19-9952-9 _2doi
040			_aES-MaUEC _bspa _cES-MaUEC _dES-MaUEC
050		4	_aQA267.7 _b2023 EB
100	1		_aArthanari, Tirukkattuppalli Subramanyam _eautor _4http://id.loc.gov/vocabulary/relators/aut _9689532
245	1	0	_aPedigree Polytopes : _bNew Insights on Computational Complexity of Combinatorial Optimisation Problems _cby Tirukkattuppalli Subramanyam Arthanari
250			_a1st ed 2023
264		1	_aSingapore _bSpringer Nature _c2023
300			_a1 recurso en línea
336			_atexto _btxt _2rdacontent
337			_aelectrónico _bc _2rdamedia
338			_arecurso electrónico _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 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.
988			_aSpringer_Computer_2023
650		7	_2embne _9165250 _aComplejidad computacional
856	4	0	_uhttps://go.openathens.net/redirector/universidadeuropea.es?url=https://doi.org/10.1007/978-981-19-9952-9 _zAcceso a este recurso digital (usuarios Universidad Europea de Madrid)
942			_2lcc _cLE
998			_b02/2024 _dz _ek _zSI