J'ai toujours eu du mal à comprendre l'importance de l' écart d' intégrité (IG) et des limites qui s'y rattachent. IG est le rapport entre (la qualité de) une réponse entière optimale à (la qualité de) une solution réelle optimale de la relaxation du problème. Prenons la couverture de vertex (VC)...
Lorsque nous considérons un algorithme d'approximation pour un problème de minimisation, l'écart d'intégralité d'une formulation IP pour ce problème donne une limite inférieure d'un rapport d'approximation pour certaines classes d'algorithmes (comme l'arrondi ou l'algorithme primal-dual). En fait,...
Nous savons que si l'écart entre les valeurs d'un programme entier et son dual (le "gap de dualité") est nul, alors les relaxations de programmation linéaire du programme entier et le dual de la relaxation admettent toutes deux des solutions intégrales (intégrité nulle) écart"). Je veux savoir si...
Tout en essayant de résoudre un problème, j'ai fini par en exprimer une partie comme le programme linéaire entier suivant. Ici sont tous des entiers positifs donnés dans le cadre de l'entrée. Un sous-ensemble spécifié des variables x i j est mis à zéro, et le reste peut prendre des valeurs...