國立高雄大學圖資館 |

Language: English

Back

Pedigree polytopesnew insights on computational complexity of combinatorial optimisation problems /

Record Type:	Electronic resources : Monograph/item
Title/Author:	Pedigree polytopesby Tirukkattuppalli Subramanyam Arthanari.
Reminder of title:	new insights on computational complexity of combinatorial optimisation problems /
Author:	Arthanari, Tirukkattuppalli Subramanyam.
Published:	Singapore :Springer Nature Singapore :2023.
Description:	xxv, 221 p. :ill., digital ;24 cm.
Contained By:	Springer Nature eBook
Subject:	Polytopes.
Online resource:	https://doi.org/10.1007/978-981-19-9952-9
ISBN:	9789811999529$q(electronic bk.)

Pedigree polytopesnew insights on computational complexity of combinatorial optimisation problems /
Arthanari, Tirukkattuppalli Subramanyam.

Pedigree polytopesnew insights on computational complexity of combinatorial optimisation problems /[electronic resource] :by Tirukkattuppalli Subramanyam Arthanari. - Singapore :Springer Nature Singapore :2023. - xxv, 221 p. :ill., digital ;24 cm.

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.

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.

ISBN: 9789811999529$q(electronic bk.)

Standard No.: 10.1007/978-981-19-9952-9doiSubjects--Topical Terms:

205957
Polytopes.

LC Class. No.: QA691

Dewey Class. No.: 516.158

Pedigree polytopesnew insights on computational complexity of combinatorial optimisation problems /
LDR:02709nmm a2200325 a 4500 001 642508
003 DE-He213
005 20230327132453.0
006 m d
007 cr nn 008maaau
008 231123s2023 si s 0 eng d
020 $a 9789811999529$q(electronic bk.)
020 $a 9789811999512$q(paper)
024 7 $a 10.1007/978-981-19-9952-9 $2 doi
035 $a 978-981-19-9952-9
040 $a GP $c GP
041 0 $a eng
050 4 $a QA691
072 7 $a UYA $2 bicssc
072 7 $a COM014000 $2 bisacsh
072 7 $a UYA $2 thema
082 0 4 $a 516.158 $2 23
090 $a QA691 $b .A787 2023
100 1 $a Arthanari, Tirukkattuppalli Subramanyam. $3 949861
245 1 0 $a Pedigree polytopes $h [electronic resource] : $b new insights on computational complexity of combinatorial optimisation problems / $c by Tirukkattuppalli Subramanyam Arthanari.
260 $a Singapore : $b Springer Nature Singapore : $b Imprint: Springer, $c 2023.
300 $a xxv, 221 p. : $b ill., digital ; $c 24 cm.
505 0 $a 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.
520 $a 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.
650 0 $a Polytopes. $3 205957
650 0 $a Combinatorial optimization. $3 185796
650 1 4 $a Computational Complexity. $3 913441
650 2 4 $a Optimization. $3 274084
650 2 4 $a Calculus of Variations and Optimization. $3 913393
650 2 4 $a Continuous Optimization. $3 558846
650 2 4 $a Field Theory and Polynomials. $3 274058
650 2 4 $a Operations Research, Management Science. $3 511451
710 2 $a SpringerLink (Online service) $3 273601
773 0 $t Springer Nature eBook
856 4 0 $u https://doi.org/10.1007/978-981-19-9952-9
950 $a Computer Science (SpringerNature-11645)