| Введение | 5 |
| Глава 1. Основы теории полиномиальной сводимости задач | 8 |
| Глава 2 . Локальный поиск | 21 |
| 2.1. Локальный поиск для задачи о максимальном разрезе | 26 |
| 2.2. Сложность локального поиска | 29 |
| 2.3. Окрестности, основанные на структурной близости решений | 33 |
| 2.4. Локальный поиск фиксированной глубины | 35 |
| 2.4.1 Локальный поиск для задачи о разбиении гра ф а | 42 |
| 2.5. Локальный поиск переменной глубины | 44 |
| 2.6. Эвристики, основанные на локальном поиске | 47 |
| 2.6.1. Алгоритм имитации отжига | 47 |
| 2.6.2. Поиск с запретами | 49 |
| 2.6.3. Генетические алгоритмы | 51 |
| Глава 3 . Приближенные алгоритмы с гарантиро ванными оценками точности | 55 |
| 3.1. Задача k-разбиения | 64 |
| 3.2. Нижняя оценка оптимального решения | 64 |
| 3.3. Приближенные методы для задачи k-разбиения | 71 |
| 3.3.1. Алгоритмы свертки | 71 |
| 3.3.2. Алгоритмы "в минимапьно загруженный" | 73 |
| 3.3.3. Обменный алгоритм | 74 |
| 3.3.4. Прямо-двойственный подход | 78 |
| 3.4. Задача 3-разбиения | 90 |
| 3.4.1. Описание алгоритма | 92 |
| 3.4.2. Приложения в теории расписаний | 98 |
| 3.5. Задача теории расписаний с задержками | 101 |
| 3.6. Задача о разбиении | 105 |
| 3.7. Градиентный алгоритм | 106 |
| 3.8. Semi on-line версия задачи разбиения | 118 |
| 3.8.1. Наличие буфера для хранения данных | 119 |
| 3.8.2. Два парanлельных процессора | 124 |
| 3.8.3. Известная обпщая сумма | 128 |
| 3.9. On-line алгоритмы для задачи k-упаковки | 130 |
| 3.10. Построение вполне полиномиальных –приближенных алгоритмов | 134 |