Maximizando funções de conjunto submodulares sujeitas a múltiplas restrições lineares

O conceito de submodularidade desempenha um papel vital na otimização combinatória. Em particular, muitos problemas importantes de otimização podem ser formulados como problemas de maximização submodular, incluindo cobertura máxima, localização máxima de instalações e corte máximo em gráficos direcionados/não direcionados. Neste artigo, apresentamos os primeiros algoritmos de aproximação conhecidos para o problema de maximizar uma função de conjunto submodular não decrescente sujeita a múltiplas restrições lineares. Dado um vetor de orçamento d-dimensional ¯ L, para algum d ≥ 1, e um oráculo para uma função de conjunto submodular não decrescente f sobre um universo U, onde cada elemento e ∈ U está associado a um vetor de custo d-dimensional, buscamos um subconjunto de elementos S ⊆ U cujo custo total seja no máximo ¯ L, de forma que f(S) seja maximizado. Desenvolvemos uma estrutura para maximizar funções submodulares sujeitas a d restrições lineares que produz uma aproximação de (1 − ε)(1 − e−1) ao ótimo para qualquer ε > 0, onde d > 1 é uma constante. Nosso estudo é motivado por uma variante do clássico problema de cobertura máxima que chamamos de cobertura máxima com múltiplas restrições de empacotamento. Usamos nossa estrutura para obter a mesma razão de aproximação para esse problema. Até onde sabemos, esta é a primeira vez que o limite teórico de 1 − e−1 é (quase) atingido para ambos os problemas.