Znalezienie minimalnego pokrycia podzbioru skończonego produktu kartezjańskiego według produktów kartezjańskich

11

Biorąc pod uwagę podzbiór iloczynu kartezjańskiego dwóch skończonych zestawów, chciałbym znaleźć jego minimalną osłonę przez zestawy, które same są produktami kartezjańskimi.I×J

Na przykład, biorąc pod uwagę iloczyn między i , mogę obserwować podzbiór i spróbuj pokryć go minimalną liczbą produktów kartezjańskich.I={A,B,C}J={1,2,3}{(A,2),(B,3),(B,2)}

to zrobić na dwa sposoby: i , oba wymagają 2 produktów. Nieoptymalnym rozwiązaniem może być rozbicie go na 3 trywialne produkty.{A}×{2}+B×{2,3}{A,B}×{2}+{B}×{3}

Czy takie optymalne pokrycie można skutecznie znaleźć (np. W czasie wielomianowym)?

algorithms set-cover yuvalm2
źródło
przypomina mi o tym problemie: „faktoryzacji kartezjańskiego łączenia wektorów bitowych” (cstheory.SE, wyrażone znacznie inaczej), który ma powiązania z dolnymi granicami teorii obwodów. w jakim kontekście pojawia się twój problem?
vzn
Mój kontekst to bezpieczeństwo sieci. W dużej sieci z wieloma serwerami określa się zasady bezpieczeństwa, z którymi można rozmawiać. Jeśli taka polityka jest konstruowana przyrostowo przez długi czas, (jak to zwykle bywa), opis polityki bezpieczeństwa można uprościć, łącząc ze sobą reguły bezpieczeństwa. Chcę znaleźć optymalne takie uproszczenie.
yuvalm2
Czy to tylko liczba produktów, które chcesz zminimalizować? Jeśli tak, co jest złego w używaniu jako okładki? To obejmie wszystko w twoim podzbiorze (i kilka innych). Czy masz wymóg, aby rozwiązanie nie tylko obejmowało podzbiór, ale także unikało obejmowania czegokolwiek poza tym podzbiorem? I×J
DW
1
Ponadto, ponieważ pochodzi to z praktycznego zastosowania (a więc prawdopodobnie szukasz praktycznych rozwiązań), czy możesz podać typowe rozmiary parametrów? np. typowy rozmiar,i twój podzbiór z dokładnością do rzędu wielkości; lub zakresy typowych wartości? Może to pomóc ocenić, które techniki będą najbardziej skuteczne. Przypomina mi się minimalizacja logiki , mapy DNF i mapy Karnaugh . |I||J|
DW
3
Być może w inny sposób formułowania tego jest następujący: Z uwagi dwudzielny wykres znajduje się minimalną liczbę dwustronnego klik (lub bi-klik), które obejmują . Każda klika odpowiada unikalnemu produktowi w Twojej kartezjańskiej przestrzeni. G=(L,R,E)E
Nicholas Mancuso,

Odpowiedzi:

2

NM przeformułowuje ten problem w komentarzach jako znalezienie minimalnej liczby klik dwustronnych (bi-klik), które pokrywają wykres dwustronny. dwa zestawy, o których wspominasz, to 2 zestawy wierzchołków dwudzielnego wykresu. iloczyn kartezjański podzbiorów dwóch zestawów wierzchołków to bicliques. wikipedia twierdzi, że jest to problem dwustronny i jest to problem GT18 w Garey i Johnson , okazało się, że NP jest kompletny w oparciu o proste przeformułowanie problemu bazowego SP7.

vzn
źródło