Existe-t-il un algorithme de temps polynomial pour déterminer si la plage d'un ensemble de matrices contient une matrice de permutation?

Je voudrais trouver un algorithme de temps polynomial qui détermine si la durée d'un ensemble donné de matrices contient une matrice de permutation.

Si quelqu'un sait si ce problème est d'une classe de complexité différente, ce serait tout aussi utile.

EDIT: J'ai étiqueté cette question avec la programmation linéaire, car j'ai une forte suspicion que si une telle solution existait, ce serait une sorte d'algorithme de programmation linéaire. La raison pour laquelle je crois que c'est parce que les points extrêmes du polytope de Birkhoff sont précisément les matrices de permutation. Si vous pouviez alors trouver une fonction objective qui soit soit maximisée soit minimisée uniquement sur les sommets du polytope de Birkhoff, vous pourriez contraindre votre fonction à l'intersection du polytope et de votre sous-espace vectoriel, puis la maximiser en temps polynomial. Si cette valeur était une matrice de permutation, vous sauriez que l'ensemble contenait une permutation. Telles sont mes réflexions sur le sujet.

EDIT 2: Après un peu de réflexion, il me semble que les matrices de permutation sont précisément les éléments du polytope de Birkhoff avec la norme euclidienne , nous considérons le polytope de Birkhoff comme la coque convexe des matrices de permutation. Cela pourrait peut-être aussi être important. $\sqrt{n}$ $n \times n$

EDIT 3: J'ai ajouté la balise de programmation semi-définie, car après mon commentaire précédent, je commence à penser qu'une solution de programmation semi-définie peut être possible car il s'agit désormais d'un algorithme d'optimisation quadratique à contrainte linéaire.

cc.complexity-theory linear-algebra linear-programming semidefinite-programming polynomial-time Entaille
la source

Quel type d'entrées les matrices d'entrée auraient-elles?

$\;$

Les entrées peuvent être dans n'importe quel champ, il y a une certaine liberté dans la configuration des matrices; cependant, vous voulez un champ suffisamment grand (donc un champ de caractéristique 2 ne serait pas bon par exemple).

Nick

Peut expliquer quelle est la durée d'un ensemble de matrices?

Mohammad Al-Turkistany

Mohammad: Je pense que c'est une combinaison linéaire d'un ensemble de matrices.

Vivek Bagaria

@DavidRicherby Je pense que la confusion de Mohammad vient du fait que nous pensons généralement aux matrices comme représentant des cartes linéaires, et la portée de la carte linéaire est parfois utilisée comme un autre terme pour sa plage. Mais cela n'a pas de sens ici, donc je suppose que nous devons considérer les matrices comme des éléments d'un espace vectoriel

Sasho Nikolov

Réponses:

Théorème. Le problème dans le message est NP-difficile, par réduction de Subset-Sum.

Bien sûr, il s'ensuit que le problème est peu susceptible d'avoir un algorithme poly-temps comme demandé par op.

Voici l'intuition. Le problème dans le poste est

Existe-t-il une matrice de permutation dans l'intervalle d'un ensemble donné de matrices?

C'est essentiellement le même que

Existe-t-il une matrice de permutation qui (en considérant la matrice comme un vecteur) satisfait certaines contraintes linéaires données?

Ceci est à son tour le même que

Existe-t-il une correspondance parfaite (dans un graphique bipartite complet) dont le vecteur d'incidence satisfait certaines contraintes linéaires données?

Réduire le sous-ensemble-somme à ce dernier problème est un exercice standard.

Voici la preuve détaillée.

Définissez le problème intermédiaire suivant:

Correspondance-somme:

entrée: Complete, bipartite graphe avec des poids de bord de nombre entier non-négatif, et la cible de nombre entier non négatif . $G=(U,V,E)$ $T$

Sortie: Est-ce que contient une correspondance parfaite de poids exactement ? $G$ $T$

Lemme 1 . Le poly-temps de sous-somme se réduit à la somme de correspondance.

Le prouver est un exercice de devoirs standard. La preuve est à la fin.

Lemme 2. Le poly-temps de somme de correspondance se réduit au problème dans le message.

Preuve du lemme 2. Fixer une entrée de somme de correspondance: un graphe bipartite complet avec des poids de bord entiers non négatifs , et cible , où et . Pour chaque , définissez comme étant la matrice dans où , et , et toutes les autres entrées sont nulles . La réduction génère l'ensemble de matrices suivant: $G=(U,V,E)$ $w:U\times V\rightarrow \mathbb{N}_+$ $T\in \mathbb{N}_+$ $U=\{u_1,\ldots,u_n\}$ $V=\{v_1, \ldots, v_n\}$ $i,j\in\{1,2,\ldots,n\}$ $M^{(ij)}$ $\mathbb{R}^{(n+1)\times (n+1)}$ $M^{(ij)}_{ij} = T$ $M^{(ij)}_{n+1,n+1}=w(u_i, v_j)$

{M^{(i j)} : i, j \in {1, \dots, n}} .

$\big\{M^{(ij)} : i,j\in\{1,\ldots,n\}\big\}.$ Ceci définit la réduction.

Prétendre. L'étendue de cet ensemble de matrices est constituée des matrices satisfaisant aux contraintes linéaires pour tout et la contrainte linéaire $M \in\mathbb{R}^{(n+1)\times(n+1)}$ $M_{h,n+1} = M_{n+1,h} = 0$ $h\le n$

\sum_{i = 1}^{n} \sum_{j = 1}^{n} M_{i j} w (u_{i}, v_{j}) = T M_{n + 1, n + 1} .

$\textstyle\sum_{i=1}^n\sum_{j=1}^n M_{ij}\,w(u_i, v_j) = T\, M_{n+1,n+1}.$

( Preuve de revendication. En inspectant chaque matrice de l'ensemble satisfait ces contraintes, donc chaque combinaison linéaire de ces matrices le fait. Inversement, si satisfait les contraintes, alors est égal à la combinaison linéaire des matrices, où Notons en particulier que, par les différentes définitions et les contraintes linéaires, Cela prouve la revendication.) $M^{(ij)}$ $M\in\mathbb{R}^{(n+1) \times (n+1)}$ $M$ $M'=\sum_{i=1}^n \sum_{j=1}^n \alpha_{ij} M^{(ij)}$ $\alpha_{ij} = M_{ij}/M^{(ij)}_{ij} = M_{ij}/T$

M_{n + 1, n + 1}^{'} = \sum_{i j} α_{i j} w (u_{i}, v_{j}) = \sum_{i j} M_{i j} w (u_{i}, v_{j}) / T = (T M_{n + 1, n + 1}) / T = M_{n + 1, n + 1} .

$\textstyle M'_{n+1,n+1} = \sum_{ij} \alpha_{ij} w(u_i, v_j) = \sum_{ij} M_{ij} w(u_i, v_j)/T = (T\, M_{n+1,n+1})/T = M_{n+1,n+1}.$

Nous montrons maintenant que la réduction est correcte. C'est-à-dire que le graphe donné a une pondération correspondant si et seulement si l'ensemble de matrices s'étend sur une matrice de permutation. $G$ $T$

( Seulement si. ) Supposons d'abord que le graphe donné ait une pondération parfaite . Soit la matrice de permutation correspondante , avec une ligne et une colonne supplémentaires ajoutées de telle sorte que et pour tout . Alors est le poids de , c'est-à-dire et , donc les contraintes linéaires dans la revendication se maintiennent, et la plage de l'ensemble donné de matrices contient la matrice de permutation $G$ $T$ $M'$ $M\in\{0,1\}^{(n+1)\times (n+1)}$ $n\times n$ $M_{n+1,n+1} = 1$ $M_{h,n+1}=M_{n+1,h}=0$ $h\le n$ $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$ $M'$ $T$ $M_{n+1,n+1}=1$ $M$ .

( Si. ) Inversement, supposons que la durée contient toute matrice de permutation . Selon la revendication, la seule entrée non nulle dans la ligne ou la colonne est , donc (comme est une matrice de permutation), il doit être que . Ainsi, la suppression de la dernière ligne et colonne donne une matrice de permutation . Soit l'appariement parfait de correspondant à cette matrice de permutation . Le poids de est , qui (selon la revendication) est $M$ $n+1$ $n+1$ $M_{n+1,n+1}$ $M$ $M_{n+1,n+1} = 1$ $n\times n$ $M'$ $G$ $n\times n$ $M'$ $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$ $T M_{n+1,n+1} = T$ . Donc, le graphe donné a une correspondance poids- , prouvant le lemme 2. $T$ $~~\Box$

Voici la preuve retardée du lemme 1:

Preuve du lemme 1. Étant donné l'instance de sous-somme , la réduction génère l'instance de somme de correspondance où , , pour chaque , le bord a le poids et tous les bords restants ont le poids zéro. $(w,T)\in\mathbb{N}^n_+ \times \mathbb{N}_+$ $(G=(U,V,E), T)$ $U=\{u_1, u_2, \ldots, u_{2n}\}$ $V=\{v_1, v_2, \ldots, v_{2n}\}$ $i\in\{1,\ldots,n\}$ $(u_i, v_i)$ $w_i$

Pour toute correspondance parfaite avec des poids de bord sommant à , l'ensemble est une solution à l'instance de sous-ensemble donnée (car ce sont les seuls bords de poids non nuls en ). $T$ $S=\{i : (u_i, v_i)\in M, i\le n\}$ $M$

Inversement, étant donné toute solution à l'instance de sous-ensemble-somme, disons avec , l'ensemble des arêtes est une correspondance partielle avec le poids , et il s'étend facilement à une correspondance parfaite de poids- en ajoutant, par exemple, l'ensemble suivant d'arêtes (de poids nul): $S\subseteq\{1,\ldots,n\}$ $\sum_{i\in S} w_i = T$ $\{(u_i, v_i) : i \in S\}$ $T$ $T$

{(u_{i + n}, v_{i + n}) : i \in S} \cup ⋃_{i \in {1, \dots, n} ∖ S} {(u_{i}, v_{i + n}), (u_{i + n}, v_{i})} .

$\{(u_{i+n}, v_{i+n}) : i\in S\} \cup \bigcup_{i\in\{1,\ldots,n\}\setminus S}\{(u_i, v_{i+n}), (u_{i+n}, v_{i})\}.$

Cela prouve le lemme 1. Le théorème découle des lemmes 1 et 2. $~~~\Box$

ps En passant, selon cette réponse , la restriction de Matching-Sum aux instances avec des poids de bord polynomialement bornés est en P. Mais je suis sûr que la restriction du problème dans le post aux matrices avec polynomialement borné (entier ) entrées NP reste difficile.

Neal Young
la source

Il semble que vous preniez la coque convexe des matrices plutôt que la travée. L'étendue des matrices que vous avez décrites est l'espace complet des matrices. Ou est-ce que je manque quelque chose?

Vanessa

@Squark, vous avez raison - j'ai mal interprété "span". Merci. J'ai corrigé la preuve pour utiliser la définition correcte de span (comme toute combinaison linéaire des matrices.)

Neal Young

Agréable! Je pense qu'il vaudrait mieux multiplier la définition de par , afin que nous n'ayons pas à diviser par quelque chose qui pourrait être 0? De plus, il semble que la preuve puisse être quelque peu simplifiée en combinant les deux réductions sans problème intermédiaire.

M^{(i j)}

$M^{(ij)}$

w (u_{i}, v_{j})

$w(u_i,v_j)$

Vanessa

Bon point sur la division par zéro. Je vais arranger ça. Je vais cependant laisser les deux réductions séparées, pour moi, c'est plus intuitif de cette façon.

Neal Young

En ce qui concerne le problème du calcul du diamètre d'un polytope présenté comme l'intersection de demi-espaces, le problème est NP-dur en général, et aussi NP-difficile à approximer à l'intérieur de tout facteur constant, voir l'article de Brieden et ses références. Je pense que pour les polytopes à symétrie centrale, un SDP donne une approximation où est le nombre d'inégalités définissant le polytope. J'esquisse ceci sous la ligne. $O(\sqrt{\log m})$ $m$

Dans votre cas, le polytope Birkhoff n'est pas symétrique au centre, mais travailler avec la coque convexe de et suffit pour vos besoins. Je pense que ce polytope "Birkhoff symétrique" peut être représenté comme l'ensemble de toutes les matrices carrées qui satisfont: $P$ $P$ $-P$ $M$

\forall i^{*}, j^{*} : \sum_{i} M_{i j^{*}} = \sum_{j} M_{i^{*} j} = c

$\forall i^*, j^*: \sum_{i}{M_{ij^*}} = \sum_j{M_{i^*j}} = c$

\forall i, j : - 1 \leq M_{i j} \leq 1

$\forall i,j: -1 \leq M_{ij} \leq 1$

- 1 \leq c \leq 1

$-1 \leq c \leq 1$

S'il s'agit d'une représentation correcte (pas sûr), vous pouvez simplement ajouter les contraintes qui restreignent ce polytope à votre sous-espace donné. Il n'est pas difficile d'adapter le SDP en dessous de la ligne à cette représentation, mais j'ai choisi de ne pas le parcourir afin de garder une notation gérable.

Je ne sais pas quel diamètre approximatif fait pour votre problème: il vous permet probablement de décider si le sous-espace donné est proche d'une matrice de permutation ou loin de tous, mais je n'ai pas travaillé sur les calculs.

Permettez-moi de terminer avec un croquis de l'arrondissement SDP (qui est un tarif assez standard). Soit un polytope à symétrie centrale, où est . Définissez le programme vectoriel: $P = \{x: -b \leq Ax \leq b\}$ $A$ $m \times n$

$\alpha^2 = \max \sum_{i = 1}^n{\|v_i\|_2^2}$

sujet à:

$\forall 1 \leq i \leq m: \|\sum_{j = 1}^n{A_{ij} v_j}\|_2^2 \leq b_i^2$

Au-dessus de la plage sur des vecteurs à dimensions. Cela peut être écrit comme un SDP de manière classique et est une relaxation du diamètre de , ie est au moins le diamètre euclidienne de . $v_i$ $n$ $P$ $\alpha$ $P$

Je prétends maintenant que . Pour le montrer, je vais vous donner un algorithme qui, étant donné de valeur , produit de longueur au moins . L'algorithme n'est qu'une projection aléatoire: choisissez un vecteur dimensions aléatoires où chaque est un gaussien standard. Définissez . Par les propriétés standard des gaussiens: $\alpha \leq O(\sqrt{\log m})\cdot \text{diam}(P)$ $(v_i)_{i=1}^n$ $\alpha$ $x \in P$ $\frac{\alpha}{O(\sqrt{\log m})}$ $n$ $g$ $g_i$ $\tilde{x}_i = g^T v_i$

E ‖ \tilde{x} ‖_{2}^{2} = α^{2}

$\mathbb{E}\ \|\tilde{x}\|_2^2 = \alpha^2$

\forall i \leq m : E | (A \tilde{x})_{i} |^{2} \leq b_{i}^{2} \Rightarrow E {max}_{i = 1}^{m} \frac{| (A \tilde{x})_{i} |}{b_{i}} \leq C \sqrt{\log m} .

$\forall i \leq m: \mathbb{E}\ |(A\tilde{x})_i|^2 \leq b_i^2 \ \ \Rightarrow \ \ \mathbb{E}\ \max_{i=1}^m{\frac{|(A\tilde{x})_i|}{b_i}} \leq C\sqrt{\log m}.$ où la dernière borne vaut pour un suffisamment grand (c'est un fait standard sur le maximum de variables aléatoires sous-guassiennes, et cela peut être prouvé en utilisant la borne de Chernoff).

C

$C$

m

$m$

Les deux équations impliquent déjà qu'il existe un tel que et . Ou, en utilisant des limites de concentration, vous pouvez montrer qu'avec une probabilité constante et . $x$ $x \in P$ $\|x\|_2^2 \geq \frac{1}{C\sqrt{\log m}}\alpha$ $\frac{1}{2C\sqrt{\log m}}\tilde{x} \in P$ $\|\tilde{x}\|_2\geq \frac{1}{2}\alpha$

Sasho Nikolov
la source