Pytania otagowane jako matching

Dopasowanie jest podzbiorem krawędzi grafu, tak że żadna krawędź w podzbiorze nie ma wspólnego wierzchołka z innym.

5
Jaka jest maksymalna liczba trwałych małżeństw w przypadku problemu stabilnego małżeństwa?
Problem stabilnego małżeństwa: http://en.wikipedia.org/wiki/Stable_marriage_problem Zdaję sobie sprawę, że w przypadku SMP możliwe jest wiele innych stabilnych małżeństw, z wyjątkiem algorytmu Gale-Shapleya. Jeśli jednak otrzymamy tylko , liczbę mężczyzn / kobiet, zadajemy następujące pytanie: Czy możemy stworzyć listę preferencji, która daje maksymalną liczbę trwałych małżeństw? Jaka jest górna granica takiej liczby?nnn
2
Maksymalna liczba wewnętrznych ścieżek st nieparzystych wierzchołków
Niech będzie prostym grafem bezkierunkowym i niech będą odrębnymi wierzchołkami. Niech długość prostej ścieżki st będzie liczbą krawędzi na ścieżce. Interesuje mnie obliczenie maksymalnego rozmiaru zestawu prostych ścieżek st, tak że każda ścieżka ma nieparzystą długość, a zestawy wierzchołków każdej pary ścieżek przecinają parami tylko s i t. Innymi słowy, …
1
Czy możemy zdecydować, czy stały ma unikalny termin?
Załóżmy, że otrzymujemy macierz n przez n, M, z wpisami liczb całkowitych. Czy możemy zdecydować w P, czy istnieje permutacjaσσ\sigma taka, że ​​dla wszystkich permutacji mamy ?π≠ σπ≠σ\pi\ne\sigmaΠ Mi σ( i )≠ Õ Mi π( i )ΠM.jaσ(ja)≠ΠM.jaπ(ja)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Uwagi Oczywiście można wymienić produkt na sumę, problem pozostaje ten …
1
Czy wystarczy, aby ograniczenia programu liniowego były spełnione w oczekiwaniu?
W artykule Randomized Primal-Dual analiza RANKING dla Online Dwustronnego dopasowywania , udowadniając jednocześnie, że algorytm RANKING jest -konkurencyjne, autorzy pokazują, że dualność jest wykonalna w oczekiwaniu (patrz Lemat 3 na stronie 5). Moje pytanie brzmi:(1−1e)(1−1e)\left(1 - \frac{1}{e}\right) Czy wystarczy, aby ograniczenia programu liniowego były spełnione w oczekiwaniu? Jedną rzeczą jest …
1
Idealne dopasowania na szachownicy?
Zastanów się nad problemem znalezienia maksymalnej liczby rycerzy, którzy mogą zostać postawieni na szachownicy bez atakowania się dwóch z nich. Odpowiedź brzmi 32: nie jest zbyt trudno znaleźć idealne dopasowanie (wykres wywołany ruchami rycerza jest dwustronny, i istnieje idealne dopasowanie dla planszy 4 × 4), co jest oczywiście minimalną osłoną …
3
Rozszerzenie problemu stabilnego małżeństwa?
To może brzmieć bardziej jak pytanie z nauk społecznych niż TCS, ale tak nie jest. Czytając „ Randomizowane algorytmy ” opisujące problem stabilnego małżeństwa, można przeczytać następujące informacje (str. 54) „Można wykazać, że dla każdego wyboru list preferencji istnieje co najmniej jedno stabilne małżeństwo. (Co ciekawe, nie dzieje się tak …
2
Maksymalne dopasowanie M z warunkiem G [M] jest wolne od 2K_2
Czy w literaturze jest coś zbliżonego do następującego problemu: Biorąc pod uwagę dwuczęściowy wykres ze zrównoważonym dwuczęściowym , czy istnieje idealne dopasowanie w tak że dla każdej 2 krawędzi występuje krawędź lub krawędź (lub oba) w ?G ( V, E)G(V,E)G(V,E){ U, W}{U,W} \{U,W\}M.M M solG G u1w1,u2)w2)∈ M.u1w1,u2w2∈Mu_1w_1, u_2w_2\in M …
11 matching 
1
Dopasowanie maksymalnej masy i funkcje podmodularne
Biorąc pod uwagę dwudzielny wykres G=(U∪V,E)G=(U∪V,E)G = (U \cup V, E) z dodatnimi wagami, niech f:2U→Rf:2U→Rf: 2^U \rightarrow \mathbb{R} z f(S)f(S)f(S) równym maksymalnemu dopasowaniu masy na wykresie .G[S∪V]G[S∪V]G[S\cup V] Czy to prawda, że jest funkcją podmodularną?fff
1
Dopasowanie masy „sprawiedliwe”
Interesuje mnie wariant maksymalnego dopasowania wagi na wykresie, który nazywam „maksymalnym uczciwym dopasowaniem”. Załóżmy, że wykres jest pełny (tj E=V×VE=V×VE=V\times V) Ma liczbę nawet wierzchołków, a masa jest podawana przez funkcję zysk . Biorąc pod uwagę pasujące , oznacz przez zysk krawędzi jest dopasowany.p:(V2)→Np:(V2)→Np:{V\choose 2}\to \mathbb NMMMM(v)M(v)M(v)vvv Pasujące jest sprawiedliwym …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.