Комбинаторная оптимизация

  • Паросочетания и вершинные покрытия в двудольных и недвудольных графах
  • Алгоритм Куна поиска максимальных паросочетаний в двудольных графах
  • Линейные и целочисленные программы
  • Политоп семейства множеств
  • Слабая и сильная двойственность в линейном программировании
  • Тотальная унимодулярность
  • Потоки в сетях, алгоритмы Форда-Фалксерсона и Эдмондса-Карпа
  • Метод проталкивания предпотока
  • Кратчайшие пути, потенциальные преобразования и циклы минимального среднего веса
  • Потоки минимальной стоимости
  • Метод эллипсоидов, эквивалентность задач оптимизации и отделения
  • Тотальная двойственная целочисленность, теорема Эдмонсда-Джайлса
  • Политоп недвудольных паросочетаний, теорема Канингхема-Марша
  • Матроиды и жадные алгоритмы, политопы независимых множеств и баз
  • Пересечения матроидов