Мы расскажем, как решать задачи комбинаторной оптимизации, используя методы метрической геометрии. Мы обсудим несколько базовых понятий и теорем метрической геометрии, расскажем о связи метрической геометрии и теории аппроксимационных алгоритмов, увидим, как решаются задачи Balanced Cut, Sparsest Cut, Minimum Linear Arrangement.
Semester | Branch |
---|---|
autumn 2017 | Saint Petersburg |