Dureza NP de um problema de otimização

Enquanto estudava um problema na teoria algorítmica dos jogos, fiquei interessado na complexidade da seguinte pergunta de otimização:

Problema

Dado:

• conjunto de base dado por n ,$U = [n] = \{1,\ldots,n\}$$n$
• classificação dada como ordens totais ⟨ S i , σ i ⟩ onde S i ⊆ L ( 1 ≤ i ≤ m ),$m$$\langle S_i, \sigma_i \rangle$$S_i \subseteq U$$1 \leq i \leq m$
• vetor de peso para dado por w ∈ R n .$U$$w \in \mathbb{R}^n$

Meta: encontrar um subconjunto maximizar a seguinte soma: r ( G ) = Σ i ∈ [ m ] , S i ∩ L ≠ ∅ w ( t i ( L ) ) , onde t i ( L ) é o mais alto ponto classificados em L ∩ S i de acordo com σ i .$L \subseteq U$

I suspeitar que o problema é -Hard. Na verdade o problema parece ser difícil mesmo quando todos o S i 's são de tamanho 2 . No entanto, não fui capaz de provar isso.$\mathsf{NP}$$S_i$$2$

O que eu sei

É fácil ver que as seguintes restrições facilitam o problema:

• todos os pesos são uniformes: a seleção de todos os elementos é claramente ideal.
• todas as classificações são classificações completas sobre : a melhor solução é obtida pegando o elemento com o peso máximo.$U$
• os pesos são apenas binários ( ), então a seleção de todos os elementos com peso 1 é ideal.$w \in \{0,1\}^n$$1$

$\mathsf{NP}$$L$$\mathsf{NP}$$r(L) \geq k$

Um IP correspondente pode ser construído silenciosamente facilmente para uma determinada instância do problema, mas não vejo nenhuma semelhança suficiente com nenhum problema que eu conheça.

Questão

$\mathsf{NP}$

Bem, aqui está uma solução possível:

A redução será da 3SAT.

$m$$(\varphi_1,\ldots,\varphi_m)$$n$$(x_1,\ldots,x_n)$

$x_i, \overline x_i$$True$$x_i$$t$$\{x_i,\overline x_i\}_{i=1,…,n}$$1$$t$$1.5$

Crie dois conjuntos de consumidores:

$x_1,\ldots,x_n$$\{x_i,\overline x_i\}$$True$$i=1,\ldots,n$

$\sigma_{i1}: x_i\succ t\\ \sigma_{i2}: \overline x_i \succ t \\ \sigma_{i3}: x_i \succ \overline x_i \\ \sigma_{i4}: x_i \succ \overline x_i$

$t$$x_i$$\overline x_i$$4$$3$$4.5$

$\varphi_j=\ell_{j1} \vee \ell_{i2} \vee \ell_{j3}$$\sigma_j: \ell_{j1} > \ell_{j2} > \ell_{j3}$$\varphi_j$$\ell_{j1}, \ell_{j2}$$\ell_{j3}$$1$$\sigma_j$

$m+4.5n$