東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Pedigree polytopes = new insights on...

Arthanari, Tirukkattuppalli Subramanyam.

Linked to FindBook

Google Book

Amazon

博客來

Pedigree polytopes = new insights on computational complexity of combinatorial optimisation problems /

Record Type:	Electronic resources : Monograph/item
Title/Author:	Pedigree polytopes/ by 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.
[NT 15003449]:	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.
Contained By:	Springer Nature eBook
Subject:	Polytopes. -
Online resource:	https://doi.org/10.1007/978-981-19-9952-9
ISBN:	9789811999529

Pedigree polytopes = new 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

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

704968
Polytopes.

LC Class. No.: QA691

Dewey Class. No.: 516.158

Pedigree polytopes = new insights on computational complexity of combinatorial optimisation problems /
LDR:02709nmm a2200325 a 4500 001 2316979
003 DE-He213
005 20230327132453.0
006 m d
007 cr nn 008maaau
008 230902s2023 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 3630643
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 704968
650 0 $a Combinatorial optimization. $3 544215
650 1 4 $a Computational Complexity. $3 3538876
650 2 4 $a Optimization. $3 891104
650 2 4 $a Calculus of Variations and Optimization. $3 3538813
650 2 4 $a Continuous Optimization. $3 1566748
650 2 4 $a Field Theory and Polynomials. $3 891077
650 2 4 $a Operations Research, Management Science. $3 1532996
710 2 $a SpringerLink (Online service) $3 836513
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)