10.11.2015 О k-расширяемых системах подмножеств (Иван Толстоганов)

В докладе будет рассмотрено естественное обобщение матроида — k-расширяемая система подмножеств. Система построена таким образом, чтобы жадный алгоритм находил независимое множество с k-приближением. Планируется рассказать о нескольких применениях конструкции.