Eu reduzi meu problema (algoritmo de layout de tabela) para o seguinte problema:

Imagine que eu tenho N variáveis ​​X1X2, ..., XN. Eu também tenho um número (indeterminado) de desigualdades, como:

X1 > = 2
x2 + X3 > = 13
etc.

Cada desigualdade é uma soma de uma ou mais variáveis ​​e é sempre comparada a uma constante usando o operador> =. Eu não posso dizer antecipadamente quantas desigualdades eu terei a cada vez, mas todas as variáveis ​​têm que ser não-negativas, então isso já é uma para cada variável.

Como resolver este sistema de tal forma que os valores das variáveis ​​sejam tão pequenos quanto possível?

Adicionado: Leia o artigo da wikipedia e percebi que esqueci de mencionar que as variáveis ​​precisam ser números inteiros. Acho que isso torna NP difícil, né?