دسترسی نامحدود
برای کاربرانی که ثبت نام کرده اند
دانلود کتاب Approximation algorithms
دانلود کتاب الگوریتم های تقریب
مشخصات کتاب
Approximation algorithms
دسته بندی: الگوریتم ها و ساختارهای داده ویرایش: نویسندگان: Vijay V. Vazirani سری: ISBN (شابک) : 9783540653677, 3540653678 ناشر: Springer سال نشر: 2004 تعداد صفحات: 396 زبان: English فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) حجم فایل: 1 مگابایت
قیمت کتاب (تومان) : 40,000
در صورت ایرانی بودن نویسنده امکان دانلود وجود ندارد و مبلغ عودت داده خواهد شد
در صورت تبدیل فایل کتاب Approximation algorithms به فرمت های PDF، EPUB، AZW3، MOBI و یا DJVU می توانید به پشتیبان اطلاع دهید تا فایل مورد نظر را تبدیل نمایند.
توجه داشته باشید کتاب الگوریتم های تقریب نسخه زبان اصلی می باشد و کتاب ترجمه شده به فارسی نمی باشد. وبسایت اینترنشنال لایبرری ارائه دهنده کتاب های زبان اصلی می باشد و هیچ گونه کتاب ترجمه شده یا نوشته شده به فارسی را ارائه نمی دهد.
توضیحاتی در مورد کتاب الگوریتم های تقریب
الگوریتم های تقریب در حال حاضر یک حوزه مرکزی و سریع در حال توسعه تحقیقات در علوم کامپیوتر نظری هستند. این تک نگاری تکنیک های اساسی مورد استفاده در آخرین کار تحقیقاتی را پوشش می دهد، تکنیک هایی که همه در این زمینه باید بدانند، و نشان می دهد که آنها آغاز یک نظریه امیدوارکننده را تشکیل می دهند. نویسنده پیشرفت های انجام شده تا کنون، از جمله برخی از نتایج بسیار اخیر را تثبیت می کند و تلاش زیادی برای انتقال زیبایی و هیجان کار در این زمینه انجام می دهد.
توضیحاتی درمورد کتاب به خارجی
Approximation algorithms are currently a central and fast-developing area of research in theoretical computer science. This monograph covers the basic techniques used in the latest research work, techniques that everyone in the field should know, and shows that they form the beginnings of a promising theory. The author consolidates progress made so far, including some very recent results, and makes a strong effort to convey the beauty and excitement of work in the field.
فهرست مطالب
Cover......Page 1
Approximation Algorithms......Page 4
Copyright......Page 5
Preface......Page 8
Table of Contents......Page 14
1 Introduction\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 22
1.1 Lower bounding OPT\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 23
1.1.2 Can the approximation guarantee be improved?\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 24
1.2 Well-characterized problems and min-max relations\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 26
1.3 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 28
1.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 31
Part I: Combinatorial Algorithms......Page 34
2 Set Cover\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 36
2.1 The greedy algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 37
2.2 Layering\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 38
2.3 Application to shortest superstring\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 40
2.4 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 43
2.5 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 47
3.1 Metric Steiner tree\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 48
3.1.1 MST-based algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 49
3.2 Metric TSP\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 51
3.2.1 A simple factor 2 algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 52
3.2.2 Improving the factor to 3/2\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 53
3.3 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 54
3.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 58
4.1 The multiway cut problem\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 59
4.2 The minimum k-cut problem\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 61
4.3 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 65
4.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 67
5.1 Parametric pruning applied to metric k-center\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 68
5.2 The weighted version\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 71
5.3 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 73
5.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 74
6.1 Cyclomatic weighted graphs\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 75
6.2 Layering applied to feedback vertex set\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 78
6.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 81
7.1 A factor 4 algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 82
7.2 Improving to factor 3\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 85
7.3 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 87
7.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 88
8 Knapsack\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 89
8.2 An FPTAS for knapsack\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 90
8.3 Strong NP-hardness and the existence of FPTAS\'s\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 92
8.4 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 93
8.5 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 94
9.1 An asymptotic PTAS\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 95
9.2 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 98
9.3 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 99
10.1 Factor 2 algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 100
10.2 A PTAS for minimum makespan\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 101
10.2.2 Reducing makespan to restricted bin packing\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 102
10.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 104
11.1 The algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 105
11.2 Proof of correctness\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 108
11.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 110
Part II: LP-Based Algorithms......Page 112
12.1 The LP-duality theorem\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 114
12.2 Min-max relations and LP-duality\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 118
12.3 Two fundamental algorithm design techniques\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 121
12.3.1 A comparison of the techniques and the notion of integrality gap\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 122
12.4 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 124
12.5 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 128
13.1 Dual-fitting-based analysis for the greedy set cover algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 129
13.1.1 Can the approximation guarantee be improved?\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 132
13.2.1 Dual fitting applied to constrained set multicover\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 133
13.3 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 137
13.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 138
14.1 A simple rounding algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 139
14.2 Randomized rounding\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 140
14.3 Half-integrality of vertex cover\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 142
14.4 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 143
14.5 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 144
15.1 Overview of the schema\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 145
15.2 Primal--dual schema applied to set cover\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 147
15.3 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 149
15.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 150
16 Maximum Satisfiability......Page 151
16.2 Derandomizing via the method of conditional expectation\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 152
16.3 Dealing with small clauses via LP-rounding\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 154
16.4 A 3/4 factor algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 156
16.5 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 157
16.6 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 159
17.1 Parametric pruning in an LP setting\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 160
17.2 Properties of extreme point solutions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 161
17.3 The algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 162
17.4 Additional properties of extreme point solutions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 163
17.5 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 164
17.6 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 165
18.1 The problems and their LP-relaxations\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 166
18.2 Primal-dual schema based algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 169
18.3 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 172
18.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 174
19.1 An interesting LP-relaxation\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 175
19.2 Randomized rounding algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 177
19.3 Half-integrality of node multiway cut\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 180
19.4 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 183
19.5 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 187
20.1 Sum multicommodity flow\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 188
20.2 LP-rounding-based algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 190
20.2.1 Growing a region: the continuous process\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 191
20.2.2 The discrete process\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 192
20.2.3 Finding successive regions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 193
20.3 A tight example\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 195
20.4 Some applications of multicut\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 196
20.5 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 197
20.6 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 199
21.1 Demands multicommodity flow\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 200
21.2 Linear programming formulation\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 201
21.3.1 Cut packings for metrics\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 203
21.3.2 \\ell_1-embeddability of metrics......Page 205
21.4 Low distortion \\ell_1-embeddings for metrics......Page 206
21.4.1 Ensuring that a single edge is not overshrunk\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 207
21.4.2 Ensuring that no edge is overshrunk\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 210
21.5 LP-rounding-based algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 211
21.6.2 Conductance\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 212
21.6.3 Balanced cut\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 213
21.6.4 Minimum cut linear arrangement\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 214
21.7 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 215
21.8 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 217
22.1 LP-relaxation and dual\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 218
22.2 Primal-dual schema with synchronization\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 219
22.3 Analysis\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 224
22.4 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 227
22.5 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 232
23.1 LP-relaxation and half-integrality\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 233
23.2 The technique of iterated rounding\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 237
23.3 Characterizing extreme point solutions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 239
23.4 A counting argument\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 241
23.5 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 244
23.6 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 251
24 Facility Location\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 252
24.1 An intuitive understanding of the dual\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 253
24.2 Relaxing primal complementary slackness conditions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 254
24.3 Primal-dual schema based algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 255
24.4 Analysis\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 256
24.4.2 Tight example\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 258
24.5 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 259
24.6 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 262
25.1 LP-relaxation and dual\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 263
25.2 The high-level idea\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 264
25.3 Randomized rounding\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 267
25.3.1 Derandomization\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 268
25.3.3 Tight example\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 269
25.4 A Lagrangian relaxation technique for approximation algorithms\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 270
25.5 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 271
25.6 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 274
26.1 Strict quadratic programs and vector programs\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 276
26.2 Properties of positive semidefinite matrices\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 278
26.3 The semidefinite programming problem\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 279
26.4 Randomized rounding algorithm\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 281
26.5 Improving the guarantee for MAX-2SAT\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 284
26.6 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 286
26.7 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 289
Part III: Other Topics......Page 292
27 Shortest Vector\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 294
27.1 Bases, determinants, and orthogonality defect\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 295
27.2 The algorithms of Euclid and Gauss\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 297
27.3 Lower bounding OPT using Gram-Schmidt orthogonalization\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 299
27.4 Extension to n dimensions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 301
27.5 The dual lattice and its algorithmic use\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 305
27.6 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 309
27.7 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 313
28 Counting Problems\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 315
28.1 Counting DNF solutions\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 316
28.2 Network reliability\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 318
28.2.1 Upperbounding the number of near-minimum cuts\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 319
28.2.2 Analysis\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 321
28.3 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 323
28.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 326
29.1 Reductions, gaps, and hardness factors\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 327
29.2 The PCP theorem\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 330
29.3 Hardness of MAX-3SAT\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 332
29.4 Hardness of MAX-3SAT with bounded occurrence of variables\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 334
29.5 Hardness of vertex cover and Steiner tree\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 337
29.6 Hardness of clique\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 339
29.7.1 The two-prover one-round characterization of NP\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 343
29.7.2 The gadget\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 345
29.7.3 Reducing error probability by parallel repetition\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 346
29.7.4 The reduction\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 347
29.8 Exercises\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 350
29.9 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 353
30.1 Problems having constant factor algorithms\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 355
30.2 Other optimization problems\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 357
30.3 Counting problems\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 359
30.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 364
A.1 Certificates and the class NP......Page 365
A.2 Reductions and NP-completeness\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 366
A.3 NP-optimization problems and approximation algorithms\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 367
A.4 Randomized complexity classes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 369
A.5 Self-reducibility\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 370
A.6 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 373
B.1 Expectation and moments......Page 374
B.2 Deviations from the mean\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 375
B.4 Notes\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 376
References\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 378
Problem Index\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 394
Subject Index\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0......Page 398
نظرات کاربران
کتاب های مرتبط
دانلود کتاب Ant Algorithms: Third International Workshop, ANTS 2002 Brussels, Belgium, September 12–14, 2002 Proceedings
دانلود کتاب Selected Papers on the Analysis of Algorithms
دانلود کتاب DNA Computing: New Computing Paradigms
دانلود کتاب Adaptive and Natural Computing Algorithms: 8th International Conference, ICANNGA 2007, Warsaw, Poland, April 11-14, 2007, Proceedings, Part II
دانلود کتاب Concise Algorithmics: The Basic Toolbox
دانلود کتاب Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra
دانلود کتاب Modeling Software with Finite State Machines: Practical Approach
دانلود کتاب Programming Interview Problems: Dynamic Programming (with solutions in Python)
دانلود کتاب Information theory
