<<
>>

Примечания и дополнительная литература

Задача устойчивых паросочетаний была впервые определена и проанализирована Гейлом и Шепли (Gale, Shapley, 1962); по словам Дэвида Гейла, побудительной причиной для анализа задачи стала история, прочитанная ими в еженедельнике «Нью-Йоркер» о сложностях организации вступительных экзаменов в колледжах (Gale, 2001).
Поиск устойчивых паросочетаний превратился в самостоятельную область исследований, которая рассматривается в книгах Гасфилда и Ирвинга (Gusfield, Irving, 1989) и Кнута (Knuth, 1997c). Гасфилд и Ирвинг также предостав- ляют хороший обзор «параллельной» истории задачи устойчивых паросочетаний на примере механизма, который был разработан для подбора сочетаний кандидатов и нанимателей в медицине и других областях.

Как упоминалось в этой главе, наши пять типичных задач будут занимать цен- тральное место в основных темах книги — а именно «жадных» алгоритмах, дина- мическом программировании, нахождении потока в сети, ЖР-полноте и PSPACE- полноте. Все эти задачи будут рассмотрены в указанных контекстах позднее в книге.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Примечания и дополнительная литература:

  1. Дополнительная литература
  2. Дополнительная литература
  3. Дополнительная литература
  4. Дополнительная литература
  5. Дополнительная литература
  6. Дополнительная литература
  7. Дополнительная литература
  8. Дополнительная литература
  9. Дополнительная литература
  10. Дополнительная литература
  11. Список дополнительной литературы