Pedigree Polytopes (Record no. 178421)
[ view plain ]
000 -LEADER | |
---|---|
fixed length control field | 03830nam a22006015i 4500 |
001 - CONTROL NUMBER | |
control field | 978-981-19-9952-9 |
003 - CONTROL NUMBER IDENTIFIER | |
control field | DE-He213 |
005 - DATE AND TIME OF LATEST TRANSACTION | |
control field | 20240423125500.0 |
007 - PHYSICAL DESCRIPTION FIXED FIELD--GENERAL INFORMATION | |
fixed length control field | cr nn 008mamaa |
008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
fixed length control field | 230327s2023 si | s |||| 0|eng d |
020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
International Standard Book Number | 9789811999529 |
-- | 978-981-19-9952-9 |
024 7# - OTHER STANDARD IDENTIFIER | |
Standard number or code | 10.1007/978-981-19-9952-9 |
Source of number or code | doi |
050 #4 - LIBRARY OF CONGRESS CALL NUMBER | |
Classification number | QA267.7 |
072 #7 - SUBJECT CATEGORY CODE | |
Subject category code | UYA |
Source | bicssc |
072 #7 - SUBJECT CATEGORY CODE | |
Subject category code | COM014000 |
Source | bisacsh |
072 #7 - SUBJECT CATEGORY CODE | |
Subject category code | UYA |
Source | thema |
082 04 - DEWEY DECIMAL CLASSIFICATION NUMBER | |
Classification number | 511.352 |
Edition number | 23 |
100 1# - MAIN ENTRY--PERSONAL NAME | |
Personal name | Arthanari, Tirukkattuppalli Subramanyam. |
Relator term | author. |
Relator code | aut |
-- | http://id.loc.gov/vocabulary/relators/aut |
245 10 - TITLE STATEMENT | |
Title | Pedigree Polytopes |
Medium | [electronic resource] : |
Remainder of title | New Insights on Computational Complexity of Combinatorial Optimisation Problems / |
Statement of responsibility, etc | by Tirukkattuppalli Subramanyam Arthanari. |
250 ## - EDITION STATEMENT | |
Edition statement | 1st ed. 2023. |
264 #1 - | |
-- | Singapore : |
-- | Springer Nature Singapore : |
-- | Imprint: Springer, |
-- | 2023. |
300 ## - PHYSICAL DESCRIPTION | |
Extent | XXV, 221 p. 83 illus., 50 illus. in color. |
Other physical details | online resource. |
336 ## - | |
-- | text |
-- | txt |
-- | rdacontent |
337 ## - | |
-- | computer |
-- | c |
-- | rdamedia |
338 ## - | |
-- | online resource |
-- | cr |
-- | rdacarrier |
347 ## - | |
-- | text file |
-- | |
-- | rda |
505 0# - FORMATTED CONTENTS NOTE | |
Formatted contents note | 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 ## - SUMMARY, ETC. | |
Summary, etc | 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 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 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Computational complexity. |
650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Mathematical optimization. |
650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Calculus of variations. |
650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Algebraic fields. |
650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Polynomials. |
650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Operations research. |
650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Management science. |
650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Computational Complexity. |
650 24 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Optimization. |
650 24 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Calculus of Variations and Optimization. |
650 24 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Continuous Optimization. |
650 24 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Field Theory and Polynomials. |
650 24 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
Topical term or geographic name as entry element | Operations Research, Management Science. |
710 2# - ADDED ENTRY--CORPORATE NAME | |
Corporate name or jurisdiction name as entry element | SpringerLink (Online service) |
773 0# - HOST ITEM ENTRY | |
Title | Springer Nature eBook |
776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
Display text | Printed edition: |
International Standard Book Number | 9789811999512 |
776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
Display text | Printed edition: |
International Standard Book Number | 9789811999536 |
776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
Display text | Printed edition: |
International Standard Book Number | 9789811999543 |
856 40 - ELECTRONIC LOCATION AND ACCESS | |
Uniform Resource Identifier | <a href="https://doi.org/10.1007/978-981-19-9952-9">https://doi.org/10.1007/978-981-19-9952-9</a> |
912 ## - | |
-- | ZDB-2-SCS |
912 ## - | |
-- | ZDB-2-SXCS |
942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
Koha item type | eBooks-CSE-Springer |
No items available.