Como minimizar a cardinalidade de um conjunto e partições disjuntas sujeitas a restrições no tempo polinomial?

O verdadeiro problema que estou enfrentando é o seguinte.

INSTANCE : tenho conjuntos$N:=\{1,\ldots,n\}$ e $K:=\{1,\ldots,k\}$ e matriz $a_{ij}>0$ para todos $i\in K$ e $j\in N$.

PERGUNTA : preciso encontrar um subconjunto$S$ do $N$ de tamanho o menor possível e particione o conjunto $K$ para dentro $|S|$ conjuntos disjuntos $K_j$ cuja união é igual $K$ tal que para todos $j\in S$, Eu tenho

$$\sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,$$ para todos os .$i\in K_j$

Exemplo:

Dado e a matriz $n=k=3$

$$\begin{bmatrix} 0.6 & 2.7 & 1.2\\ 1.3 & 2.6 & 0.8\\ 1.5 & 0.4 & 0.6 \end{bmatrix}.$$

Neste exemplo, deve ser igual a S = \ {1, 2 \} e K_1 = \ {3 \} e K_2 = \ {1,2 \} .$S$$S=\{1, 2\}$$K_1=\{3\}$$K_2=\{1,2\}$

Notei dois fatos:

• Se houver algum $j\in N$ tal que $a_{ij}\geqslant 1$ para todos os $i\in K$ então $S=\{j\}$ e $K_j=K$ ; e
• Se existir algum $i\in K$ tal que $a_{ij}<1$ então $S=\emptyset$ .

Minha pergunta : É possível resolver esse problema de otimização em tempo polinomial (pelo menos com algoritmo de aproximação)?

A primeira coisa que tentei fazer foi transformá-lo em um problema conhecido e depois aplicar um algoritmo conhecido para isso. Pensei em transformá-lo em uma tampa ou caixa de embalagem, mas falhei e também não acho que isso seja interessante.

---

O problema que tentei formular.

I têm conjuntos e e matriz para todos os e . Além disso, eu tenho conjuntos disjuntos para cada (eu adicionei como entradas porque não poderia formulá-lo de outra forma.)$N:=\{1,\ldots,n\}$$K:=\{1,\ldots,k\}$$a_{ij}>0$$i\in K$$j\in N$$n$$K_j\subset K$$j\in N$$K_j$

Por fim, recebo o seguinte:

$$\begin{align*} & {\underset{S}{\text{minimize}}} & & |S|\\[3pt] & \text{subject to} & & \sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,\forall\, j\in S,i\in K_j,\\[3pt] & & & S\subseteq N.\\ \end{align*}$$

Obrigado.

Mesmo a versão de decisão desse problema, na qual tentamos determinar simplesmente se existe alguma solução viável, é difícil de NP por redução do Exact Cover . (A versão de otimização, onde buscamos uma solução viável que minimize , é claramente pelo menos tão difícil quanto isso.)$|S|$

A matriz de linha única e coluna única contendo o valor 0,5 é um exemplo de entrada para a qual não há solução viável. Aqui está outro:

$$\begin{bmatrix} 0.2 & 4\\ 3.1 & 3\\ 5 & 0.6 \end{bmatrix}.$$

Criando um gadget "Escolha no máximo um"

Primeiro, observe que, se o valor máximo em alguma linha for , e essa linha contiver (pelo menos) duas cópias de , digamos em e , , não pode conter e , pois se o fez, um dos dois casos a seguir deve surgir, cada um dos quais leva a uma contradição:$a_i$$x > 0$$x$$a_{ij}$$a_{ij'}$$j' \ne j$$S$$j$$j'$

1. $i \in K_j \cup K_{j'}$ : suponha que wlog . Mas então , contradizendo o requisito que .$i \in K_j$$\Sigma_{m \in S, m \ne j}{a_{im}} \ge a_{ij'} = x = a_{ij}$$\Sigma_{m \in S, m \ne j}{a_{im}} \le a_{ij} - 1$
2. $i \notin K_j \cup K_{j'}$ : Suponha que . Mas então , e como é o máximo na linha , o mais alto que poderia ser é claramente , então devemos estar violando a mesma desigualdade de antes.$i \in K_p, p \notin \{j, j'\}$$\Sigma_{m \in S, m \ne p}{a_{im}} \ge a_{ij} + a_{ij'} = 2x$$x$$i$$a_{ip}$$x$

Assim, podemos escolher um valor máximo que é seguramente maior do que a soma de todos os valores não-máximas na linha, e usar cópias deste valor máximo para impor que, no máximo, uma daquelas colunas está incluída no .$S$

Podemos transformar essa restrição "escolher no máximo uma" em uma restrição "escolher exatamente uma" usando qualquer valor positivo menor que 1 como o valor "não máximo". Isso porque cada linha pertence a alguma parte da partição de linha e, se , o RHS da desigualdade se torna negativo para a linha , portanto não há como satisfazê-la: portanto, pelo menos um deve ser forçado a modo que .$i$$K_j$$a_{ij} < 1$$i$$j$$S$$a_{ij} \ge 1$

Portanto, para garantir que exatamente uma das colunas em algum conjunto seja forçada em , crie uma linha seguinte maneira:$T \subseteq N$$S$$a_i$

• Conjunto para cada .$a_{ij} = n+1$$j \in T$
• Defina para todos os outros .$a_{ij} = 0.5$$j$

Assim, a redução da tampa exacta é simples: há uma linha para cada elemento, uma coluna para cada conjunto, com , sempre conjunto inclui elemento e contrário. Ambas as direções ("A instância EC de entrada é uma instância YES instância construída do problema do OP é uma instância YES" e "A instância construída do problema do OP é uma instância YES a instância EC de entrada é uma instância YES") são claros.$a_{ij} = n+1$$j$$i$$a_{ij} = 0.5$$\implies$$\implies$