28 февраля 2014 года

Эффективные алгоритмы решения слабопереопределенных тропических линейных систем

Алексей Павлович Давыдов (Академический университет РАН, С.-Петербург)

В отличие от классического случая, эффективного алгоритма для разрешения тропический линейных систем неизвестно. В 2013 году было доказано, что данная задача эквивалентна задаче о двухсторонних min-plus системах, которая в свою очередь эквивалентна задаче о циклических играх. Эти задачи известны уже более 30 лет и имеют непосредственное приложение в ряде оптимизационных задач, при этом эффективных алгоритмов решений для них так же неизвестно. На данный момент известны полиномиальные алгоритмы проверки слабопереопределенных систем на разрешимость, но не было известно ни одного эффективного алгоритма для нахождения решния слабопереопределенных систем. О двух новых алгоритмах, позволяющих находить решение слабопереопределенной тропической системы за полиномиальное время, и пойдет речь в данном докладе.