Nicht aus der Schweiz? Besuchen Sie lehmanns.de
Discrete Optimization -  R. Gary Parker,  Ronald L. Rardin

Discrete Optimization (eBook)

eBook Download: PDF
2014 | 1. Auflage
472 Seiten
Elsevier Science (Verlag)
978-1-4832-9480-3 (ISBN)
Systemvoraussetzungen
124,00 inkl. MwSt
(CHF 119,95)
Der eBook-Verkauf erfolgt durch die Lehmanns Media GmbH (Berlin) zum Preis in Euro inkl. MwSt.
  • Download sofort lieferbar
  • Zahlungsarten anzeigen
This book treats the fundamental issues and algorithmic strategies emerging as the core of the discipline of discrete optimization in a comprehensive and rigorous fashion. Following an introductory chapter on computational complexity, the basic algorithmic results for the two major models of polynomial algorithms are introduced--models using matroids and linear programming. Further chapters treat the major non-polynomial algorithms: branch-and-bound and cutting planes. The text concludes with a chapter on heuristic algorithms.Several appendixes are included which review the fundamental ideas of linear programming, graph theory, and combinatorics--prerequisites for readers of the text. Numerous exercises are included at the end of each chapter.
This book treats the fundamental issues and algorithmic strategies emerging as the core of the discipline of discrete optimization in a comprehensive and rigorous fashion. Following an introductory chapter on computational complexity, the basic algorithmic results for the two major models of polynomial algorithms are introduced--models using matroids and linear programming. Further chapters treat the major non-polynomial algorithms: branch-and-bound and cutting planes. The text concludes with a chapter on heuristic algorithms.Several appendixes are included which review the fundamental ideas of linear programming, graph theory, and combinatorics--prerequisites for readers of the text. Numerous exercises are included at the end of each chapter.

Front Cover 1
Discrete Optimization 4
Copyright Page 5
Table of Contents 8
Dedication 6
Preface 10
Chapter 1. Introduction to Discrete Optimization 14
1.1 Discrete Optimization Defined 15
1.2 Discrete Optimization and Integer Programming 17
1.3 Why are Discrete Optimization Problems Difficult to Solve? 18
1.4 Progress in Discrete Optimization 20
1.5 Organization of the Book 20
EXERCISES 21
Chapter 2. 
24 
2.1 Fundamental Concepts 25
2.2 Decision Problems 36
2.3 NP- Equivalent Problems 41
2.4 The P . NP Conjecture 58
2.5 Dealing with NP-Hard Problems 59
EXERCISES 64
Chapter 3. 
70 
3.1 Independence Systems and Matroids 71
3.2 Examples of Matroids 73
3.3 Matroid Duality 75
3.4 Optimization and Independence Systems 79
3.5 Matroid Intersection 84
3.6 Matroid Parity 101
3.7 Submodular Functions and Polymatroids 106
EXERCISES 112
Chapter 4. 
120 
4.1 Polynomial-Time Solution of Linear Programs 120
4.2 Integer Solvability of Linear Programs 144
4.3 Equivalences between Linear and Polynomial Solvability 153
4.4 Integer Programs with a Fixed Number of Variables 159
EXERCISES 162
Chapter 5. 
170 
5.1 Fundamentals of Partial Enumeration 171
5.2 Elementary Bounds 188
5.3 Conditional Bounds and Penalties 200
5.4 Heuristic Aspects of Branch and Bound 207
5.5 Constructive Dual Techniques 218
5.6 Primal Partitioning—Benders Enumeration 250
EXERCISES 262
Chapter 6. 
278 
6.1 Fundamentals of Polyhedral Description 278
6.2 Gomory's Cutting Algorithm 292
6.3 Minimal Inequalities 304
6.4 Disjunctive Characterizations 311
6.5 Subadditive Characterizations 335
6.6 Successive Integerized Sum Characterization 346
6.7 Direct Techniques 356
EXERCISES 360
Chapter 7. 
370 
7.1 The Nature of Nonexact Procedures 371
7.2 Measures of Algorithm Performance 373
7.3 Greedy Procedures 381
7.4 Local Improvement 388
7.5 Truncated Exponential Schemes 396
7.6 Some Negative Results 404
EXERCISES 411
Appendix A: Vectors, Matrices and Convex Sets 420
Appendix B: 
430 
Appendix C: Linear Programming Fundamentals 442
References 450
Index 474

Erscheint lt. Verlag 28.6.2014
Sprache englisch
Themenwelt Mathematik / Informatik Mathematik Graphentheorie
Technik
ISBN-10 1-4832-9480-3 / 1483294803
ISBN-13 978-1-4832-9480-3 / 9781483294803
Haben Sie eine Frage zum Produkt?
PDFPDF (Adobe DRM)
Größe: 26,3 MB

Kopierschutz: Adobe-DRM
Adobe-DRM ist ein Kopierschutz, der das eBook vor Mißbrauch schützen soll. Dabei wird das eBook bereits beim Download auf Ihre persönliche Adobe-ID autorisiert. Lesen können Sie das eBook dann nur auf den Geräten, welche ebenfalls auf Ihre Adobe-ID registriert sind.
Details zum Adobe-DRM

Dateiformat: PDF (Portable Document Format)
Mit einem festen Seiten­layout eignet sich die PDF besonders für Fach­bücher mit Spalten, Tabellen und Abbild­ungen. Eine PDF kann auf fast allen Geräten ange­zeigt werden, ist aber für kleine Displays (Smart­phone, eReader) nur einge­schränkt geeignet.

Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen eine Adobe-ID und die Software Adobe Digital Editions (kostenlos). Von der Benutzung der OverDrive Media Console raten wir Ihnen ab. Erfahrungsgemäß treten hier gehäuft Probleme mit dem Adobe DRM auf.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen eine Adobe-ID sowie eine kostenlose App.
Geräteliste und zusätzliche Hinweise

Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.

Mehr entdecken
aus dem Bereich

von Eiichi Bannai; Etsuko Bannai; Tatsuro Ito; Rie Tanaka

eBook Download (2021)
Walter de Gruyter GmbH & Co.KG (Verlag)
CHF 146,50