Как быстро мы можем решить полностью унимодулярную целочисленную линейную программу?

(Это продолжение этого вопроса и его ответа .)

У меня есть следующая полностью унимодулярная (TU) целочисленная линейная программа (ILP). Здесь - все натуральные числа, заданные как часть входных данных. Указанное подмножество переменных x i j устанавливается в ноль, а остальные могут принимать положительные целые значения:$\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$$x_{ij}$

Минимизировать

$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$

При условии:

$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$

$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$

Матрица коэффициентов стандартной формы является матрица с элементами из - 1 , 0 , 1 .$(2\ell+m)\times \ell m$${-1,0,1}$

Мой вопрос:

Каковы лучшие верхние границы, известные для времени выполнения алгоритмов полиномиального времени, которые решают такую ​​ILP? Не могли бы вы указать мне некоторые ссылки на это?

Я провел некоторый поиск, но в большинстве мест они заканчивают тем, что говорят, что ILP TU может быть решен за полиномиальное время с использованием алгоритмов полиномиального времени для LP. Одна вещь, которая выглядела многообещающе, - это работа Тардоса, сделанная в 1986 году [1], где она доказывает, что такие проблемы могут быть решены за полиномиальный по времени размер матрицы коэффициентов. Однако, насколько я мог понять из статьи, время выполнения этого алгоритма зависит, в свою очередь, от времени работы алгоритма полиномиального времени для решения LP.

Известны ли нам алгоритмы, которые решают этот частный случай (TU ILP) значительно быстрее, чем общие алгоритмы, которые решают проблему LP?

Если не,

Какой алгоритм для LP решит такой ILP быстрее всего (в асимптотическом смысле)?

[1] Сильно полиномиальный алгоритм для решения комбинаторных линейных программ, Ева Тардос, исследование операций 34 (2), 1986

Я полагаю, что в классе совершенно унимодулярных матриц Яннакакис дает ответ на ваш вопрос для особого случая TU ILP (если в двудольном графе нет нечетных циклов, получаемых при рассмотрении матрицы коэффициентов в качестве матрицы смежности).

В этой статье есть ссылка на полиномиальные алгоритмы для класса линейных программ , который, кажется, обрабатывает все абсолютно унимодулярные матрицы, но я не уверен, насколько он более эффективен по сравнению с универсальными алгоритмами для LP.

$O([n^3/\ln n]L)$

Было показано, что полностью унимодулярная LP разрешима за сильно полиномиальное время при «предположении вырождения» - здесь ссылка (таким образом, если ILP имеет полностью унимодулярную (TU) формулировку с теми же предположениями, то этот алгоритм будет решать TU ILP, в сильное полиномиальное время. Это развитие методов Тардоса, подразумевающее более жесткие границы для формулировки ILP TU (полностью унимодулярной).