Soluções máximas mínimas de LPs

Hoje em dia, a programação linear é muito bem compreendida. Temos muito trabalho que caracteriza a estrutura de soluções viáveis e a estrutura de soluções ideais. Temos a forte dualidade, algoritmos de poli-tempo, etc.

Mas o que se sabe sobre soluções mínimas máximas de LPs? Ou, equivalentemente, soluções mínimas máximas?

(Esta não é realmente uma pergunta de pesquisa, mas talvez possamos ter algo menos técnico para as férias. Só estou curioso e, depois de pesquisar no Google, tive a sensação de que devo estar perdendo as palavras-chave corretas. Parece óbvio. problema para estudar, mas só encontrei alguns artigos esporádicos que mencionam o problema.)

Para simplificar, vamos nos concentrar em embalar e cobrir LPs . Em um LP de embalagem nos é dado um não negativo matriz . Um vetor é possível se e . Dizemos que é máximo se possível e não podemos aumentar avidamente qualquer componente. Ou seja, se e , não é viável. E, finalmente, é uma solução máxima mínima , se minimizar a função objetivo $A$ $x$ $x \ge 0$ $Ax \le 1$ $x$ $y \ge 0$ $y \ne 0$ $x + y$ $x$ $\sum_i x_i$ entre todas as soluções máximas.

(Você pode definir uma solução mínima mínima de um LP de cobertura de maneira análoga.)

Como é o espaço das soluções máximas mínimas? Como podemos encontrar essas soluções? Quão difícil é encontrar essas soluções? Como podemos aproximar essas soluções? Quem estuda essas coisas e qual é o termo certo para isso?

Essas perguntas foram originalmente motivadas por sets dominantes nas arestas e combinações máximas mínimas . É bem sabido (e bastante fácil de ver) que uma correspondência máxima mínima é um conjunto dominante de borda mínima; por outro lado, dado um conjunto mínimo de dominância de arestas, é fácil construir uma correspondência mínima mínima.

Então eles são, em essência, o mesmo problema. Ambos os problemas são NP-hard e APX-hard. Existe um algoritmo trivial de 2 aproximações: qualquer correspondência máxima.

No entanto, seus relaxamentos "naturais" do LP parecem muito diferentes. Se você pegar o problema dominante do conjunto e formar um relaxamento natural do LP, receberá um LP de cobertura. No entanto, se você tiver o problema de encontrar uma correspondência máxima mínima e tentar criar um relaxamento de LP, o que você ganha? Bem, é claro que combinações fracionárias são soluções viáveis para um LP de embalagem; as correspondências fracionárias máximas são soluções máximas de tais LPs e as correspondências fracionárias máximas mínimas são, portanto, soluções máximas mínimas de tais LPs. :)

cc.complexity-theory ds.algorithms reference-request linear-programming optimization Jukka Suomela
fonte

Sua definição de máximo como "não podemos aumentar avidamente nenhum componente" soa muito como o Nash Equilibrium. Existe uma conexão oculta com a teoria dos jogos aqui?

Derrick Stolee

Não é o caso de cada solução máxima no exemplo de embalagem LP, ? Então, essencialmente, estamos procurando uma solução mínima (em L_ -norm) do sistema de equações lineares.

x^{'}

$x'$

A x^{'} = 1

$Ax'=1$

L_{\infty}

$L_{\infty}$

Imran Rauf

@Imran: Não, eu não acho que isso esteja correto. Uma solução máxima (e uma solução máxima) sempre existe, mesmo se não tivermos uma solução para .

A x = 1

$Ax = 1$

Jukka Suomela

Você está familiarizado com programas lineares de gargalo , nos quais o aspecto minimax está na função objetivo?

Mike Spivey

Maximalidade e minimalidade: são tipos de otimização de Pareto.
Complexidade: acho que encontrar uma solução máxima mínima é difícil para o NP. Eu reduziria o problema de dominação da independência (também conhecido como problema mínimo de conjunto independente máximo) em gráficos bipartidos. Sabe-se que esse problema (mais precisamente sua versão de decisão) é NP-completo (DG Corneil e Y. Perl, Clustering e dominação em gráficos perfeitos. Discrete Applied Mathematics 9 (1984) 27-39). Como um gráfico bipartido é perfeito, seu conjunto polítopo independente é determinado pelas desigualdades de clique e o número de cliques em um gráfico bipartido é polinomial. Portanto, podemos explicitamente escrever um sistema de desigualdades lineares Ax <= 1, x> = 0 para o conjunto independente de politopo. As soluções extremas correspondem aos conjuntos independentes e as soluções máximas extremas correspondem aos conjuntos independentes máximos.

Yoshio Okamoto
fonte

Soluções máximas mínimas de LPs

Respostas: