Czy istnieje algorytm wielomianowy do określania, czy rozpiętość zbioru macierzy zawiera macierz permutacji?

Chciałbym znaleźć algorytm wielomianowy, który określa, czy rozpiętość danego zestawu macierzy zawiera macierz permutacji.

Jeśli ktoś wie, czy ten problem ma inną klasę złożoności, byłoby to równie pomocne.

EDYCJA: Oznacziłem to pytanie za pomocą programowania liniowego, ponieważ mam poważne podejrzenia, że gdyby istniało takie rozwiązanie, byłby to rodzaj algorytmu programowania liniowego. Uważam, że powodem tego jest to, że skrajnymi punktami polytopu Birkhoffa są właśnie matryce permutacyjne. Jeśli możesz następnie znaleźć funkcję celu, która jest albo zmaksymalizowana, albo zminimalizowana tylko na wierzchołkach polytopu Birkhoffa, możesz ograniczyć swoją funkcję do przecięcia polytopu i podprzestrzeni wektora, a następnie zmaksymalizować ją w czasie wielomianowym. Gdyby ta wartość była macierzą permutacji, wiedziałbyś, że zestaw zawiera permutację. To są moje przemyślenia na ten temat.

EDYCJA 2: Po dłuższej refleksji wydaje mi się, że macierze permutacji są właśnie elementami polytopu Birkhoffa z normą euklidesową $\sqrt{n}$ , uważamy, że polytop Birkhoffa jest wypukłym kadłubemmatryc permutacyjnych $n \times n$ . Być może to może być również znaczące.

EDYCJA 3: Dodałem znacznik programowania półfinałowego, ponieważ po moim poprzednim komentarzu zaczynam myśleć, że rozwiązanie programowania półfinałowego może być możliwe, ponieważ jest to teraz liniowo ograniczony algorytm kwadratowej optymalizacji.

— Nacięcie
źródło

Jakiego rodzaju wpisy miałyby macierze wejściowe?

$\;$

Wpisy mogą znajdować się w dowolnym polu, istnieje pewna swoboda w konfigurowaniu macierzy; jednak chcesz mieć wystarczająco duże pole (więc pole charakterystyki 2 nie byłoby na przykład dobre).

— Nick

Czy można wyjaśnić, jaki jest zakres zestawu matryc?

— Mohammad Al-Turkistany,

Mohammad: Myślę, że jest to liniowa kombinacja zestawu matryc.

— Vivek Bagaria,

@DavidRicherby Myślę, że zamieszanie Mohammada wynika z faktu, że zwykle myślimy o matrycach jako o mapach liniowych, a rozpiętość mapy liniowej jest czasem używana jako inny termin określający jej zasięg. Ale to nie ma sensu, więc myślę, że powinniśmy myśleć o macierzach jako elementach przestrzeni wektorowej

— Sasho Nikolov

Odpowiedzi:

Twierdzenie. Problem na stanowisku jest trudny NP, przez redukcję z sumy częściowej.

Oczywiście wynika z tego, że mało prawdopodobne jest, aby problem zawierał algorytm wieloczasowy, zgodnie z żądaniem op.

Oto intuicja. Problem w poście jest

Czy istnieje macierz permutacji na rozpiętości danego zestawu macierzy?

Jest to w zasadzie to samo co

Czy istnieje macierz permutacyjna, która (myśląc o macierzy jako wektorze) spełnia pewne dane ograniczenia liniowe?

To z kolei jest takie samo jak

Czy istnieje idealne dopasowanie (na pełnym grafie dwudzielnym), którego wektor występowania spełnia określone ograniczenia liniowe?

Zmniejszenie sumy częściowej do tego drugiego problemu jest standardowym ćwiczeniem.

Oto szczegółowy dowód.

Zdefiniuj następujący problem pośredni:

Dopasowana suma:

dane wejściowe: Pełny, dwustronny wykres z nie-ujemnych wag krawędzi liczbę całkowitą, a nieujemną liczbą całkowitą docelowej . $G=(U,V,E)$ $T$

wynik: czy zawiera idealne dopasowanie masy dokładnie do ? $G$ $T$

Lemat 1 . Wielo-czasowy podzbiór sumy zmniejsza się do sumy dopasowania.

Udowodnienie, że jest to standardowe zadanie domowe. Dowód jest na końcu.

Lemat 2. Wielokrotnie dopasowywana suma sprowadza się do problemu na stanowisku.

Dowód lematu 2. Naprawić sumę dopasowującą: pełny wykres dwudzielny z nieujemnymi wagami całkowitymi krawędzi i docelowym , gdzie i $G=(U,V,E)$ $w:U\times V\rightarrow \mathbb{N}_+$ $T\in \mathbb{N}_+$ $U=\{u_1,\ldots,u_n\}$ . Dla każdego $V=\{v_1, \ldots, v_n\}$ , zdefiniuj jako macierz w gdzie i $i,j\in\{1,2,\ldots,n\}$ $M^{(ij)}$ $\mathbb{R}^{(n+1)\times (n+1)}$ $M^{(ij)}_{ij} = T$ , a wszystkie inne wpisy są zerowe. Redukcja generuje następujący zestaw macierzy: To określa redukcję. $M^{(ij)}_{n+1,n+1}=w(u_i, v_j)$

{{M.}^{(ja jot)} : ja, jot \in {1, \dots, n}} .

$\big\{M^{(ij)} : i,j\in\{1,\ldots,n\}\big\}.$

Roszczenie. Rozpiętość tego zestawu matrycy składa się z tych macierzy , spełniającego liniowe ograniczenia dla wszystkich i ograniczenie liniowe $M \in\mathbb{R}^{(n+1)\times(n+1)}$ $M_{h,n+1} = M_{n+1,h} = 0$ $h\le n$

\sum_{ja = 1}^{n} \sum_{jot = 1}^{n} {M.}_{ja jot} w (u_{ja}, v_{jot}) = 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}.$

( Potwierdzenie według zastrz. Poprzez kontrolę każdej macierzy w zestawie spełnia te ograniczenia, aby każdy liniową kombinacją tych macierzy nie. Z drugiej strony, jeśli spełnia ograniczeń , następnie równa się kombinacji liniowej macierzy, gdzie $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)}$ . Należy zauważyć w szczególności, że według różnych definicji i ograniczeń liniowych $\alpha_{ij} = M_{ij}/M^{(ij)}_{ij} = M_{ij}/T$ To potwierdza roszczenie.)

{M.}_{n + 1, n + 1}^{'} = \sum_{ja jot} α_{ja jot} w (u_{ja}, v_{jot}) = \sum_{ja jot} {M.}_{ja jot} w (u_{ja}, v_{jot}) / 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}.$

Teraz pokazujemy, że redukcja jest poprawna. Oznacza to, że dany wykres ma dopasowanie wagi wtedy i tylko wtedy, gdy zbiór macierzy obejmuje macierz permutacji. $G$ $T$

( Tylko jeśli. ) Najpierw załóżmy, że podany wykres ma idealne dopasowanie . Niech jest odpowiednia macierzy permutacji, z dodatkowego rzędu i kolumny dodaje się tak, że i $G$ $T$ $M'$ $M\in\{0,1\}^{(n+1)\times (n+1)}$ $n\times n$ $M_{n+1,n+1} = 1$ dla wszystkich. Zatemjest wagą , to znaczyi $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$ Tak liniowe ograniczenia w ładowni zastrzeżeń oraz rozpiętość dany zestaw matryc zawiera macierz permutacji . $M$

( If. ) Z drugiej strony, załóżmy, że przedział zawiera elementy macierzy permutacji . Przy żądaniu tylko niezerowej wejścia w wierszu lub kolumny to , to (a jest macierzą permutacji) musi być tak . Zatem usunięcie ostatniego wiersza i kolumny daje macierz permutacji . Niech być idealne dopasowanie $M$ $n+1$ $n+1$ $M_{n+1,n+1}$ $M$ $M_{n+1,n+1} = 1$ $n\times n$ $M'$ odpowiadające temu $G$ $n\times n$ macierzy permutacji . Masa jest , który (z zastrzeżeń) jest . Tak więc podany wykres ma dopasowanie , co dowodzi lematu 2. $M'$ $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$ $T M_{n+1,n+1} = T$ $T$ $~~\Box$

Oto opóźniony dowód na Lemat 1:

Dowód lematu 1. Biorąc pod uwagę instancję sumy częściowej , redukcja generuje instancję sumy dopasowania gdzie , $(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}\}$ dla każdego , krawędź ma masę , a wszystkie pozostałe krawędzie mają ciężar wynosił zero. $i\in\{1,\ldots,n\}$ $(u_i, v_i)$ $w_i$

For any perfect matching with edge weights summing to $T$ , the set $S=\{i : (u_i, v_i)\in M, i\le n\}$ is a solution to the given Subset-Sum instance (as these are the only non-zero weight edges in $M$ ).

$S\subseteq\{1,\ldots,n\}$ $\sum_{i\in S} w_i = T$ $\{(u_i, v_i) : i \in S\}$ $T$ $T$

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

$\{(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})\}.$

$~~~\Box$

p.s. As an aside, according to this answer, the restriction of Matching-Sum to instances with polynomially-bounded edge weights is in P. But I'm sure that the restriction of the problem in the post to matrices with polynomially-bounded (integer) entries remains NP hard.

— Neal Young
źródło

It seems like you take the convex hull of the matrices rather than the span. The span of the matrices you described is the full space of matrices. Or am I missing something?

— Vanessa

@Squark, you are correct - I misinterpreted "span". Thanks. I corrected the proof to use the correct definition of span (as any linear combination of the matrices.)

— Neal Young

Miły! Myślę, że lepiej byłoby pomnożyć definicję

M^{(i j)}

$M^{(ij)}$ przez

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

$w(u_i,v_j)$ , abyśmy nie musieli dzielić przez coś, co może wynosić 0? Wydaje się również, że dowód można nieco uprościć, łącząc dwie redukcje bez pośredniego problemu.

— Vanessa,

Dobra uwaga na temat dzielenia przez zero. Naprawię to. Obie redukcje zostawię osobno, dla mnie jest to bardziej intuicyjne.

— Neal Young

Regarding the problem of computing the diameter of a polytope presented as the intersection of halfspaces, the problem is NP-hard in general, and also NP-hard to approximate within any constant factor, see Brieden's paper and references therein. I think for centrally symmetric polytopes, an SDP gives an $O(\sqrt{\log m})$ approximation where $m$ is the number of inequalities defining the polytope. I sketch this below the line.

In your case the Birkhoff polytope $P$ is not centrally symmetric, but working with the convex hull of $P$ and $-P$ suffices for your purposes. I think this "symmetric Birkhoff" polytope can be represented as the set of all square matrices $M$ that satisfy:

\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$

If this is a correct representation (not sure), then you can just add the constraints that restrict this polytope to your given subspace. It is not hard to adapt the SDP below the line to this representation, but I choose not to go through it in order to keep notation managable.

I am not sure what approximate diameter does for your problem: it probably lets you decide if the given subspace is close to a permutation matrix or far from all of them, but I have not worked out the calculations.

Let me finish with a sketch of the SDP rounding (which is fairly standard fare). Let $P = \{x: -b \leq Ax \leq b\}$ be a centrally symmetric polytope, where $A$ is $m \times n$ . Zdefiniuj program wektorowy:

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

z zastrzeżeniem:

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

Wyżej $v_i$ zasięg powyżej $n$ wektory wymiarowe. Można to zapisać jako SDP w standardowy sposób i jest to rozluźnienie średnicy $P$ , tj $\alpha$ jest co najmniej średnicą euklidesową $P$ .

Teraz to twierdzę $\alpha \leq O(\sqrt{\log m})\cdot \text{diam}(P)$ . Aby to pokazać, dam ci algorytm, który, biorąc pod uwagę $(v_i)_{i=1}^n$ wartości $\alpha$ , wyjścia $x \in P$ co najmniej długości $\frac{\alpha}{O(\sqrt{\log m})}$ . The algorithm is just a random projection: pick a random $n$ -dimensional vector $g$ where each $g_i$ is a standard gaussian. Set $\tilde{x}_i = g^T v_i$ . By standard properties of gaussians:

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}.$ where the last bound holds for large enough

C

$C$ (this is a standard fact about the maximum of

m

$m$ subguassian random variables, and can be proven using the Chernoff bound).

The two equations already imply there exists an $x$ such that $x \in P$ and $\|x\|_2^2 \geq \frac{1}{C\sqrt{\log m}}\alpha$ . Lub używając granic stężenia, możesz to pokazać ze stałym prawdopodobieństwem $\frac{1}{2C\sqrt{\log m}}\tilde{x} \in P$ i $\|\tilde{x}\|_2\geq \frac{1}{2}\alpha$ .

— Sasho Nikolov
źródło