Problème de sous-ensemble avec de nombreuses conditions de divisibilité

28

Soit un ensemble de nombres naturels. Nous considérons sous l'ordre partiel de divisibilité, c'est-à-dire s_1 \ leq s_2 \ iff s_1 \ mid s_2 . LaisserS s 1s 2SSs1s2s1s2

α(S)=max{|V|VS,V an antichain } .

Si nous considérons le problème de la somme des sous-ensembles où le multi-ensemble de nombres est dans S , que pouvons-nous dire de la complexité du problème lié à α(S) ? Il est simple de voir si α(S)=1 , alors le problème est facile. Notez qu'il est facile même pour le problème de sac à dos plus difficile lorsque α(S)=1 .


Résolution de problèmes séquentiels de sacs à dos par M. Hartmann et T. Olmstead (1993)

Chao Xu
la source
1
Au lieu de "relation", je suggère d'utiliser les termes "ordre partiel". En outre, sur une réflexion minimale, le problème des pièces de monnaie Frobenius pourrait être pertinent (bien sûr, pas sûr, cependant)
Aryabhata

Réponses:

2

Ce problème peut être résolu en temps polynomial en utilisant une programmation linéaire, et cela est en fait vrai pour tout ordre partiel (S,) . Soit dit en passant, nous pouvons prouver par induction que pour tout ensemble d'ordre partiel fini (S,) , il existe un ensemble fini SN et une bijection f:SS , telle que pour tous s1,s2S,s1s2f(s1)|f(s2) .

Que C l'ensemble formé par les chaînes en S . Rappelez-vous que C est une chaîne ssi pour tout v,v en C , vv ou vv

Maintenant créer une variable booléenne pour chaque , et une variable booléenne pour chaque chaîne . Nous pouvons écrire le programme linéaire suivant pour notre problème: xvvSyCC(P)

MaxvSxvsubject tovCxv1,CCxv{0,1},vS

et son double :(D)

MinCCyCsubject toC:vCyC1,vSyC{0,1},CC

Ensuite, le problème de trouver la couverture minimale d'un ensemble ordonné par chaînes est le double de notre problème. Le théorème de Dilworth déclare que

Il existe une antichaine A, et une partition de l'ordre en une famille P de chaînes, de sorte que le nombre de chaînes dans la partition est égal à la cardinalité de A

ce qui signifie que la solution optimale de ces deux problèmes correspond:Opt(P)=Opt(D)

Soit ( resp. ) la relaxation de ( resp. ) ie le même programme linéaire où toutes les contraintes ( resp. ) sont remplacés par ( resp. ). Soit et leurs solutions optimales. Depuis nous avons: et une dualité faible le théorème établit que(P) (D)(P) (D)xv{0,1} yC{0,1}xv[0,1] yC[0,1]Opt(P)Opt(D){0,1}[0,1]

Opt(P)Opt(P) and Opt(D)Opt(D)
Opt(P)Opt(D)puis en mettant tout ensemble on a:
Opt(P)=Opt(P)=Opt(D)=Opt(D)

Ensuite, en utilisant la méthode Ellipsoïde , nous pouvons calculer ( ) en temps polynomial. Il existe un nombre exponentiel de contraintes mais il existe un oracle de séparation temporelle polynomiale. En effet étant donné une solution , on peut énumérer tous les couples et vérifier si ou , et donc décider en temps polynomial si est faisable ou sinon la contrainte associée à la chaîne est violé.Opt(P)=Opt(P)Xs1,s2Xs1s2s2s1X{v1,v2}

Mathieu Mari
la source
La méthode ellispoïde fonctionne quel que soit le nombre de contraintes, si nous avons (1) un nombre polynomial de variables et (2) un oracle de séparation qui, quelle que soit la solution, décide en temps polynomial si est faisable ou trouve une contrainte violée par . Je recommande de lire [ www-math.mit.edu/~goemans/18433S09/ellipsoid.pdf] , wikipedia n'est pas très clair sur ce pointxxx
Mathieu Mari
Merci d'avoir expliqué pourquoi le nombre exponentiel de contraintes n'est pas un problème et la pertinence de la dualité. Très agréable!
DW