Quão rápido podemos resolver um programa linear inteiro totalmente unimodular?

(Este é um acompanhamento para esta pergunta e sua resposta .)

Eu tenho o seguinte programa linear inteiro totalmente unimodular (TU) (ILP). Aqui $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ são números inteiros positivos dados como parte da entrada. Um subconjunto especificado das variáveis é definido como zero e o restante pode assumir valores integrais positivos:$x_{ij}$

Minimizar

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

Sujeito a:

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

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

A matriz do coeficiente do formulário padrão é uma matriz com entradas de .$(2\ell+m)\times \ell m$${-1,0,1}$

Minha pergunta é:

Quais são os melhores limites superiores conhecidos pelo tempo de execução dos algoritmos de tempo polinomial que resolvem esse ILP? Você poderia me indicar algumas referências sobre isso?

Eu fiz algumas pesquisas, mas na maioria dos lugares eles param dizendo que um TU ILP pode ser resolvido em tempo polinomial usando algoritmos de tempo polinomial para LP. Uma coisa que parecia promissora é um artigo de 1986 de Tardos [1], onde ela prova que esses problemas podem ser resolvidos em tempo polinomial no tamanho da matriz do coeficiente. Tanto quanto pude descobrir no artigo, no entanto, o tempo de execução desse algoritmo depende, por sua vez, do tempo de execução de um algoritmo de tempo polinomial para resolver LP.

Conhecemos algoritmos que resolvem esse caso especial (de TU ILP) significativamente mais rápido que os algoritmos gerais que resolvem o problema de LP?

Se não,

Qual algoritmo para LP resolveria esse ILP o mais rápido (em um sentido assintótico)?

[1] Um algoritmo fortemente polinomial para resolver programas lineares combinatórios, Eva Tardos, Operations Research 34 (2), 1986

Eu acredito que Em uma classe de matrizes totalmente unimodulares , de Yannakakis, dá uma resposta à sua pergunta para um caso especial de TU ILP (sempre que não houver ciclos ímpares em um gráfico bipartido obtido pela visualização da matriz do coeficiente como matriz de adjacência).

Nesse artigo, há uma referência aos algoritmos polinomiais para uma classe de programas lineares , que parece lidar com todas as matrizes totalmente unimodulares, mas não tenho certeza sobre o quanto mais eficiente ele é comparado aos algoritmos genéricos para LPs.

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

Foi demonstrado que LP totalmente unimodular é solúvel em tempo fortemente polinomial sob uma "suposição de degenerescência" - link aqui (portanto, se o ILP tiver uma formulação Totalmente Unimodular (TU) com as mesmas suposições, esse algoritmo resolveria um ILP de TU, em tempo polinomial forte.Este é um desenvolvimento dos métodos de Tardos e implica limites mais estreitos para uma formulação de ILP TU (Totalmente Unimodular).