تفاصيل مارك
| 000 -الفاتح |
|---|
| حقل البيانات ثابتة الطول |
08063cam a2200385 a 4500 |
| 001 - رقم الضبط |
|---|
| رقم الضبط |
671709856 |
| 003 - محدد رقم الضبط |
|---|
| رقم الضبط |
OCoLC |
| 005 - وقت وتاريخ اخر تعامل مع التسجيلة |
|---|
| رقم الضبط |
20150408114107.0 |
| 008 - عناصر البيانات ثابتة الطول - معلومات عامة |
|---|
| حقل البيانات ثابتة الطول |
110114s2011 nyua b 001 0 eng |
| 010 ## - رقم ضبط مكتبة الكونجرس |
|---|
| رقم ضبط مكتبة الكونجرس |
2011001945 |
| 020 ## - الرقم الدولى المعيارى للكتب |
|---|
| الرقم الدولى المعيارى للكتاب |
9780521195270 (hardback) |
| 020 ## - الرقم الدولى المعيارى للكتب |
|---|
| الرقم الدولى المعيارى للكتاب |
0521195276 (hardback) |
| 035 ## - رقم ضبط النظام |
|---|
| رقم ضبط النظام |
(OCoLC)671709856 |
| 040 ## - مصدر الفهرسة |
|---|
| وكالة الفهرسة الأصلية |
DLC |
| وكالة النسخ |
DLC |
| وكالة التعديل |
YDX |
| -- |
BTCTA |
| -- |
YDXCP |
| -- |
CDX |
| -- |
GIKBM |
| -- |
INU |
| 042 ## - رمز التحقق |
|---|
| رمز التحقق |
pcc |
| 050 00 - رقم طلب مكتبة الكونجرس |
|---|
| رقم التصنيف |
QA221 |
| رقم المادة |
.W55 2011 |
| 082 00 - رقم تصنيف ديوى العشرى |
|---|
| رقم التصنيف |
518.5 |
| رقم الطبعة |
22 |
| رقم المادة |
WDD |
| 100 1# - المدخل الرئيسى - إسم شخصى |
|---|
| الإسم الشخصى |
Williamson, David P. |
| 9 (RLIN) |
19125 |
| 245 14 - بيان العنوان |
|---|
| العنوان |
The design of approximation algorithms / |
| بيان المسئوليه,etc |
David P. Williamson, David B. Shmoys. |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) |
|---|
| مكان الناشر او الموزع |
New York : |
| اسم الناشر او الموزع |
Cambridge University Press, |
| تاريخ النشر أو التوزيع |
2011. |
| 300 ## - الوصف المادى |
|---|
| التعداد |
xi, 504 p. : |
| تفاصيل ماديه اخرى للوعاء |
ill. ; |
| أبعاد الوعاء |
26 cm. |
| 504 ## - تبصرة ببليوجرافية |
|---|
| تبصرة ببليوجرافية,الخ |
Includes bibliographical references and indexes. |
| 505 00 - تبصرة محتويات-الفهرس |
|---|
| معلومات متنوعة |
Machine generated contents note: |
| -- |
I. |
| العنوان |
An Introduction to the Techniques -- |
| معلومات متنوعة |
1. |
| العنوان |
An Introduction to Approximation Algorithms -- |
| معلومات متنوعة |
1.1. |
| العنوان |
The Whats and Whys of Approximation Algorithms -- |
| معلومات متنوعة |
1.2. |
| العنوان |
An Introduction to the Techniques and to Linear Programming: The Set Cover Problem -- |
| معلومات متنوعة |
1.3. |
| العنوان |
A Deterministic Rounding Algorithm -- |
| معلومات متنوعة |
1.4. |
| العنوان |
Rounding a Dual Solution -- |
| معلومات متنوعة |
1.5. |
| العنوان |
Constructing a Dual Solution: The Primal-Dual Method -- |
| معلومات متنوعة |
1.6. |
| العنوان |
A Greedy Algorithm -- |
| معلومات متنوعة |
1.7. |
| العنوان |
A Randomized Rounding Algorithm -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
2. |
| العنوان |
Greedy Algorithms and Local Search -- |
| معلومات متنوعة |
2.1. |
| العنوان |
Scheduling Jobs with Deadlines on a Single Machine -- |
| معلومات متنوعة |
2.2. |
| العنوان |
The k-Center Problem -- |
| معلومات متنوعة |
2.3. |
| العنوان |
Scheduling Jobs on Identical Parallel Machines -- |
| معلومات متنوعة |
2.4. |
| العنوان |
The Traveling Salesman Problem -- |
| معلومات متنوعة |
2.5. |
| العنوان |
Maximizing Float in Bank Accounts -- |
| معلومات متنوعة |
2.6. |
| العنوان |
Finding Minimum-Degree Spanning Trees -- |
| معلومات متنوعة |
2.7. |
| العنوان |
Edge Coloring -- |
| -- |
Exercises -- |
| -- |
Chapter Notes. |
| 505 00 - تبصرة محتويات-الفهرس |
|---|
| معلومات متنوعة |
3. |
| العنوان |
Rounding Data and Dynamic Programming -- |
| معلومات متنوعة |
3.1. |
| العنوان |
The Knapsack Problem -- |
| معلومات متنوعة |
3.2. |
| العنوان |
Scheduling Jobs on Identical Parallel Machines -- |
| معلومات متنوعة |
3.3. |
| العنوان |
The Bin-Packing Problem -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
4. |
| العنوان |
Deterministic Rounding of Linear Programs -- |
| معلومات متنوعة |
4.1. |
| العنوان |
Minimizing the Sum of Completion Times on a Single Machine -- |
| معلومات متنوعة |
4.2. |
| العنوان |
Minimizing the Weighted Sum of Completion Times on a Single Machine -- |
| معلومات متنوعة |
4.3. |
| العنوان |
Solving Large Linear Programs in Polynomial Time via the Ellipsoid Method -- |
| معلومات متنوعة |
4.4. |
| العنوان |
The Prize-Collecting Steiner Tree Problem -- |
| معلومات متنوعة |
4.5. |
| العنوان |
The Uncapacitated Facility Location Problem -- |
| معلومات متنوعة |
4.6. |
| العنوان |
The Bin-Packing Problem -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
5. |
| العنوان |
Random Sampling and Randomized Rounding of Linear Programs -- |
| معلومات متنوعة |
5.1. |
| العنوان |
Simple Algorithms for MAX SAT and MAX CUT -- |
| معلومات متنوعة |
5.2. |
| العنوان |
Derandomization -- |
| معلومات متنوعة |
5.3. |
| العنوان |
Flipping Biased Coins -- |
| معلومات متنوعة |
5.4. |
| العنوان |
Randomized Rounding -- |
| معلومات متنوعة |
5.5. |
| العنوان |
Choosing the Better of Two Solutions -- |
| معلومات متنوعة |
5.6. |
| العنوان |
Nonlinear Randomized Rounding -- |
| معلومات متنوعة |
5.7. |
| العنوان |
The Prize-Collecting Steiner Tree Problem. |
| 505 00 - تبصرة محتويات-الفهرس |
|---|
| معلومات متنوعة |
5.8. |
| العنوان |
The Uncapacitated Facility Location Problem -- |
| معلومات متنوعة |
5.9. |
| العنوان |
Scheduling a Single Machine with Release Dates -- |
| معلومات متنوعة |
5.10. |
| العنوان |
Chernoff Bounds -- |
| معلومات متنوعة |
5.11. |
| العنوان |
Integer Multicommodity Flows -- |
| معلومات متنوعة |
5.12. |
| العنوان |
Random Sampling and Coloring Dense 3-Colorable Graphs -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
6. |
| العنوان |
Randomized Rounding of Semidefinite Programs -- |
| معلومات متنوعة |
6.1. |
| العنوان |
A Brief Introduction to Semidefinite Programming -- |
| معلومات متنوعة |
6.2. |
| العنوان |
Finding Large Cuts -- |
| معلومات متنوعة |
6.3. |
| العنوان |
Approximating Quadratic Programs -- |
| معلومات متنوعة |
6.4. |
| العنوان |
Finding a Correlation Clustering -- |
| معلومات متنوعة |
6.5. |
| العنوان |
Coloring 3-Colorable Graphs -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
7. |
| العنوان |
The Primal-Dual Method -- |
| معلومات متنوعة |
7.1. |
| العنوان |
The Set Cover Problem: A Review -- |
| معلومات متنوعة |
7.2. |
| العنوان |
Choosing Variables to Increase: The Feedback Vertex Set Problem in Undirected Graphs -- |
| معلومات متنوعة |
7.3. |
| العنوان |
Cleaning Up the Primal Solution: The Shortest s-t Path Problem -- |
| معلومات متنوعة |
7.4. |
| العنوان |
Increasing Multiple Variables at Once: The Generalized Steiner Tree Problem -- |
| معلومات متنوعة |
7.5. |
| العنوان |
Strengthening Inequalities: The Minimum Knapsack Problem -- |
| معلومات متنوعة |
7.6. |
| العنوان |
The Uncapacitated Facility Location Problem. |
| 505 00 - تبصرة محتويات-الفهرس |
|---|
| معلومات متنوعة |
7.7. |
| العنوان |
Lagrangean Relaxation and the k-Median Problem -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
8. |
| العنوان |
Cuts and Metrics -- |
| معلومات متنوعة |
8.1. |
| العنوان |
The Multiway Cut Problem and a Minimum-Cut -- Based Algorithm -- |
| معلومات متنوعة |
8.2. |
| العنوان |
The Multiway Cut Problem and an LP Rounding Algorithm -- |
| معلومات متنوعة |
8.3. |
| العنوان |
The Multicut Problem -- |
| معلومات متنوعة |
8.4. |
| العنوان |
Balanced Cuts -- |
| معلومات متنوعة |
8.5. |
| العنوان |
Probabilistic Approximation of Metrics by Tree Metrics -- |
| معلومات متنوعة |
8.6. |
| العنوان |
An Application of Tree Metrics: Buy-at-Bulk Network Design -- |
| معلومات متنوعة |
8.7. |
| العنوان |
Spreading Metrics, Tree Metrics, and Linear Arrangement -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
II. |
| العنوان |
Further Uses of the Techniques -- |
| معلومات متنوعة |
9. |
| العنوان |
Further Uses of Greedy and Local Search Algorithms -- |
| معلومات متنوعة |
9.1. |
| العنوان |
A Local Search Algorithm for the Uncapacitated Facility Location Problem -- |
| معلومات متنوعة |
9.2. |
| العنوان |
A Local Search Algorithm for the k-Median Problem -- |
| معلومات متنوعة |
9.3. |
| العنوان |
Minimum-Degree Spanning Trees -- |
| معلومات متنوعة |
9.4. |
| العنوان |
A Greedy Algorithm for the Uncapacitated Facility Location Problem -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
10. |
| العنوان |
Further Uses of Rounding Data and Dynamic Programming. |
| 505 00 - تبصرة محتويات-الفهرس |
|---|
| معلومات متنوعة |
10.1. |
| العنوان |
The Euclidean Traveling Salesman Problem -- |
| معلومات متنوعة |
10.2. |
| العنوان |
The Maximum Independent Set Problem in Planar Graphs -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
11. |
| العنوان |
Further Uses of Deterministic Rounding of Linear Programs -- |
| معلومات متنوعة |
11.1. |
| العنوان |
The Generalized Assignment Problem -- |
| معلومات متنوعة |
11.2. |
| العنوان |
Minimum-Cost Bounded-Degree Spanning Trees -- |
| معلومات متنوعة |
11.3. |
| العنوان |
Survivable Network Design and Iterated Rounding -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
12. |
| العنوان |
Further Uses of Random Sampling and Randomized Rounding of Linear Programs -- |
| معلومات متنوعة |
12.1. |
| العنوان |
The Uncapacitated Facility Location Problem -- |
| معلومات متنوعة |
12.2. |
| العنوان |
The Single-Source Rent-or-Buy Problem -- |
| معلومات متنوعة |
12.3. |
| العنوان |
The Steiner Tree Problem -- |
| معلومات متنوعة |
12.4. |
| العنوان |
Everything at Once: Finding a Large Cut in a Dense Graph -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
13. |
| العنوان |
Further Uses of Randomized Rounding of Semidefinite Programs -- |
| معلومات متنوعة |
13.1. |
| العنوان |
Approximating Quadratic Programs -- |
| معلومات متنوعة |
13.2. |
| العنوان |
Coloring 3-Colorable Graphs -- |
| معلومات متنوعة |
13.3. |
| العنوان |
Unique Games -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
14. |
| العنوان |
Further Uses of the Primal-Dual Method. |
| 505 00 - تبصرة محتويات-الفهرس |
|---|
| معلومات متنوعة |
14.1. |
| العنوان |
The Prize-Collecting Steiner Tree Problem -- |
| معلومات متنوعة |
14.2. |
| العنوان |
The Feedback Vertex Set Problem in Undirected Graphs -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
15. |
| العنوان |
Further Uses of Cuts and Metrics -- |
| معلومات متنوعة |
15.1. |
| العنوان |
Low-Distortion Embeddings and the Sparsest Cut Problem -- |
| معلومات متنوعة |
15.2. |
| العنوان |
Oblivious Routing and Cut-Tree Packings -- |
| معلومات متنوعة |
15.3. |
| العنوان |
Cut-Tree Packings and the Minimum Bisection Problem -- |
| معلومات متنوعة |
15.4. |
| العنوان |
The Uniform Sparsest Cut Problem -- |
| -- |
Exercises -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
16. |
| العنوان |
Techniques in Proving the Hardness of Approximation -- |
| معلومات متنوعة |
16.1. |
| العنوان |
Reductions from NP-Complete Problems -- |
| معلومات متنوعة |
16.2. |
| العنوان |
Reductions that Preserve Approximation -- |
| معلومات متنوعة |
16.3. |
| العنوان |
Reductions from Probabilistically Checkable Proofs -- |
| معلومات متنوعة |
16.4. |
| العنوان |
Reductions from Label Cover -- |
| معلومات متنوعة |
16.5. |
| العنوان |
Reductions from Unique Games -- |
| -- |
Chapter Notes -- |
| معلومات متنوعة |
17. |
| العنوان |
Open Problems. |
| 520 ## - التبصرة الخاصة بالتعليق أو التلخيص |
|---|
| ملخص,الخ |
"Discrete optimization problems are everywhere, from traditional operations research planning problems, such as scheduling, facility location, and network design; to computer science problems in databases; to advertising issues in viral marketing. Yet most such problems are NP-hard. Thus unless P = NP, there are no efficient algorithms to find optimal solutions to such problems. This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions. The book is organized around central algorithmic techniques for designing approximation algorithms, including greedy and local search algorithms, dynamic programming, linear and semidefinite programming, and randomization. Each chapter in the first part of the book is devoted to a single algorithmic technique, which is then applied to several different problems. The second part revisits the techniques but offers more sophisticated treatments of them. The book also covers methods for proving that optimization problems are hard to approximate. Designed as a textbook for graduate-level algorithms courses, the book will also serve as a reference for researchers interested in the heuristic solution of discrete optimization problems"-- |
| 650 #0 - المدخل الاضافى بالموضوع-مصطلح موضوعى |
|---|
| مصطلح موضوعي أو اسم جغرافي كعنصر مدخل |
Approximation theory. |
| 9 (RLIN) |
19126 |
| 650 #0 - المدخل الاضافى بالموضوع-مصطلح موضوعى |
|---|
| مصطلح موضوعي أو اسم جغرافي كعنصر مدخل |
Mathematical optimization. |
| 9 (RLIN) |
12151 |
| 700 1# - المدخل الاضافى - اسم شخصى |
|---|
| الإسم الشخصى |
Shmoys, David Bernard. |
| 9 (RLIN) |
19127 |
| 856 42 - الوصول و الموقع الالكترونى |
|---|
| مواد محددة |
Cover image |
| معرف المصدر الموحد |
<a href="http://assets.cambridge.org/97805211/95270/cover/9780521195270.jpg">http://assets.cambridge.org/97805211/95270/cover/9780521195270.jpg</a> |
| 942 ## - عناصر المدخل الإضافي( كوها) |
|---|
| مصدر التصنيف او مخطط الترفيف |
Dewey Decimal Classification |
| Koha [default] item type |
DVD |
