Peut-on échantillonner efficacement et de manière uniforme un voisin d'un sommet dans le graphique d'un polytope?

15

J'ai un polytope P défini par {x:Axb,x0} .

Question: Étant donné un sommet v de P , existe-t-il un algorithme polynomial de temps pour échantillonner uniformément à partir des voisins de v dans le graphique de P ? (Polynôme dans la dimension, le nombre d'équations et la représentation de b . Je peux supposer que le nombre d'équations est polynomial dans la dimension.)

Mise à jour: Je pense que j'ai pu montrer que c'est NP-difficile, voir ma réponse qui explique l'argument. (Et par NP -hard, je veux dire qu'un algorithme de temps polynomial prouverait RP=NP ... je ne sais pas quelle est la terminologie correcte ici.)

Mise à jour 2: Il existe une preuve de dureté NP lignes (étant donné le bon polytope combinatoire) et j'ai pu y trouver un article de Khachiyan. Voir la réponse pour la description et le lien. :-RÉ


Un problème équivalent :

Dans les commentaires, Peter Shor a souligné que cette question est équivalente à la question de savoir si nous pouvons échantillonner uniformément à partir des sommets d'un polytope donné. (Je pense que l'équivalence va comme ceci: dans une direction, nous pouvons passer d'un polytope P avec un sommet v à la figure du sommet àv ,P/v , et échantillonner les sommets deP/v équivaut à échantillonner les voisins dev surP Dans l'autre sens, on peut passer d'un polytopeP à un polytopeQ d'une dimension supérieure en ajoutant un cône de sommetv et de baseP. L'échantillonnage des voisins de v dans Q équivaut alors à l'échantillonnage des sommets de P )

Cette formulation de la question a déjà été posée: /mathpro/319930/sampling-uniformly-from-the-vertices-of-a-polytope


Lorenzo Najt
la source
Je ne connais pas la réponse à votre question, mais à ma connaissance, il n'y a pas de dureté NP connue pour échantillonner uniformément un sommet d'un polytope donné explicitement. Par exemple, approximativement les cycles d'échantillonnage sont durs en NP. Cependant, s'il y avait un programme linéaire dont les sommets codent les cycles, alors très probablement, vous pouvez optimiser la longueur du cycle, et donc résoudre Hamiltonian-Cycle.
Heng Guo
Une autre remarque est que même si votre question a une réponse positive, elle ne donne pas un échantillonneur uniforme pour les sommets (en supposant la conjecture de polytope 0-1). Dans la plupart des cas intéressants, le squelette du polytope n'est pas régulier et les degrés peuvent varier de façon exponentielle.
Heng Guo
@HengGuo Merci encore pour les commentaires, ils sont très utiles. Connaissez-vous un bon exemple où les degrés varient de façon exponentielle? (Je ne suis pas surpris que cela puisse se produire pour les polytopes généraux; ce serait bien d'avoir un exemple combinatoire si vous en connaissez un du haut de votre tête.)
Lorenzo Najt
Considérons le polytope d'ensemble indépendant d'un graphe biparti. Deux sommets (deux ensembles indépendants) sont connectés si leur différence symétrique induit un sous-graphique connecté. Maintenant, prenez un graphe bipartite dont un côté n'a que deux sommets, connecte à chaque sommet de l'autre côté etv1 un seul. Considérez les ensembles indépendants { v 1 } et { v 2 } . v2{v1}{v2}
Heng Guo
5
L'échantillonnage uniforme des sommets voisins d'un sommet donné d'un polytope est le même problème que l'échantillonnage uniforme d'un sommet aléatoire d'un polytope. Coupez un cône infiniment proche du sommet. On a alors un nouveau polytope, et si vous pouvez échantillonner un sommet de ce nouveau polytope, on peut échantillonner un sommet voisin du polytope d'origine. Je suppose que faire cela est approximativement dans BPP, mais je ne trouve aucun document qui le prouve.
Peter Shor

Réponses:

4

Edit 2: Embarrassamment, il y a une preuve à deux lignes du NP dureté , si l'on commence par le bon polytope.

Rappelons d'abord le polytope de circulation d'un graphe en bas de la page 4 de Générer tous les sommets d'un polyèdre est difficile .

Ses sommets sont en correspondance bijective avec les cycles simples dirigés. Par conséquent, ils sont difficiles à échantillonner ou à compter par la proposition JVV 5.1 . :-RÉ

Équipé de ces mots clés, j'ai pu trouver la dureté du résultat d'échantillonnage comme le théorème 1 des hypergraphes transversaux et des familles de cônes polyédriques de Khachiyan.


Edit: j'ai écrit l'argument ci-dessous, et il semble correct. Cependant, il y a un argument beaucoup plus simple, que je vais décrire ici:

a) Par analyse d'algorithmes de retour en arrière pour lister tous les sommets et toutes les faces d'un polyèdre convexe (Fukuda et al.), il est fortement difficile de résoudre le problème suivant sur les polytopes:

Entrée: Un polytope Ax=b,x0 dansRn un sous-ensembleSn

Sortie: s'il existe un sommet v de P différent de zéro sur chacune des coordonnées de S .

b) Compte tenu de cela, on peut faire la construction suivante: introduire de nouvelles variables yik pour iS et k=1,,d , et introduire l'inégalité 0yikxi . Appelons le polytope résultant PS,d . Le but de cette construction est d'introduire un hypercube au dessus de chaque sommet, de dimensiond|supp(x)S|.

c) On peut vérifier que les sommets de ce polytope se trouvent tous au-dessus des sommets de l'ancien polytope, et que le nombre de sommets sur un sommet est de 2d|supp(x)S|, oùsuppest la fonction qui envoie un sommet aux coordonnées où il est différent de zéro.

d) Par une chaîne habituelle d'arguments de type bigons, il s'ensuit qu'en prenant d suffisamment grand, un échantillon uniforme des sommets dePS,d donnerait (avec une probabilité élevée) un échantillon des sommets maximisant la taille de leur intersection avecS .

Il semble y avoir diverses extensions de cela. Je mettrai à jour avec un lien lorsque l'écriture sera terminée.


(L'ancien argument était ici - il se trouve dans l'historique des modifications. Je l'ai supprimé car il est très long et gênera la recherche de la bonne réponse à la question.)

Lorenzo Najt
la source
Ceci est un argument très intéressant! Je n'ai pas vérifié tous les détails dans la partie 3) (quelles sont les fonctions , H 0 , l e a v e s ?), Mais en principe, toute structure non s'étendant ne peut qu'encourir une explosion super exponentielle, qui ainsi peut être contrôlé en prenant d polynôme grand. H1H0leavesd
Heng Guo
@HengGuo Merci d'avoir lu! Par Je veux dire le nombre de composants, et | H 1 | la dimension de l'espace cyclique (rang du circuit), et "laisse" le nombre de sommets de degré 1. Je vais ajouter ces définitions. |H0||H1|
Lorenzo Najt
Il doit y avoir quelque chose de mal à cela. S'il existe un polytope dont les sommets sont des lassos et des cycles simples, ne pouvons-nous pas utiliser la programmation linéaire pour maximiser la fonction linéaire que nous voulons sur ce polytope? Et cela ne nous permettrait-il pas de trouver un lasso couvrant en temps polynomial?
Peter Shor
@PeterShor Je pense que cela ne se produit pas parce que le polytope vit à l'intérieur de l'hyperplan défini en définissant la somme des variables de bord à un. Cette fonction est donc constante sur le polytope. La fonction qui représente le nombre d'arêtes est la taille du support du vecteur, qui n'est pas linéaire sur ce polytope.
Lorenzo Najt
@PeterShor J'ai ajouté une preuve que la fonction 'nombre d'arêtes' ne peut pas être linéaire, voir l'image en bas.
Lorenzo Najt