Mendeley出力
Pedigree Polytopes : New Insights on Computational Complexity of Combinatorial Optimisation Problems / by Tirukkattuppalli Subramanyam Arthanari
| データ種別 | 電子ブック |
|---|---|
| 版 | 1st ed. 2023. |
| 出版者 | (Singapore : Springer Nature Singapore : Imprint: Springer) |
| 出版年 | 2023 |
| 大きさ | XXV, 221 p. 83 illus., 50 illus. in color : online resource |
| 著者標目 | *Arthanari, Tirukkattuppalli Subramanyam author SpringerLink (Online service) |
書誌詳細を非表示
| 一般注記 | 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 HTTP:URL=https://doi.org/10.1007/978-981-19-9952-9 |
|---|---|
| 件 名 | LCSH:Computational complexity LCSH:Mathematical optimization LCSH:Calculus of variations LCSH:Algebraic fields LCSH:Polynomials LCSH:Operations research LCSH:Management science FREE:Computational Complexity FREE:Optimization FREE:Calculus of Variations and Optimization FREE:Continuous Optimization FREE:Field Theory and Polynomials FREE:Operations Research, Management Science |
| 分 類 | LCC:QA267.7 DC23:511.352 |
| 書誌ID | EB00001979 |
| ISBN | 9789811999529 |
類似資料
この資料の利用統計
このページへのアクセス回数：2回
※2019年3月27日以降
全貸出数：0回
(1年以内の貸出：0回)
※2019年3月27日以降