Aplikacje Vertex Cover w prawdziwym świecie

22

Jakie aplikacje mają problemy z wierzchołkiem w prawdziwym świecie?

Które projekty branżowe lub badawcze wykorzystują faktycznie zaimplementowane oprogramowanie oparte na teoretycznych wynikach problemu dotyczącego Vertex Cover? W szczególności, czy któryś z poniższych wyników teoretycznych jest wdrażany w używanym oprogramowaniu?

Algorytmy aproksymacyjne dla pokrywy wierzchołków
Algorytmy czasu wykładniczego dla osłony wierzchołków
Trwałe parametry algorytmów dla pokrycia wierzchołków
Algorytmy jądra dla Cover Vertex

ds.algorithms graph-theory graph-algorithms

— scatman
źródło

6

jednym z dobrych przykładów jest wiki na temat warunków wyścigu: en.wikipedia.org/wiki/Vertex_cover#Examples Również jako motywację ludzie podają przykład monitorowania. Na każdym wierzchołku rozwiązania monitorujemy. Osobiście uważam, że przeglądanie tej odpowiedzi jest lepszą opcją niż zadawanie jej tutaj.

— singhsumit

5

Jak myślisz, dlaczego ta pokrywa wierzchołków ma jakieś zastosowania w świecie rzeczywistym?

— Jukka Suomela,

3

Wydaje mi się, że odpowiedź jest taka, że pokrywy wierzchołków nie mają znaczącego zastosowania. Ale ludzie je badają, ponieważ osłony wierzchołków są prostym specjalnym przypadkiem problemu z ustawioną osłoną. Zestaw okładek ma aplikacje. I nie możesz naprawdę zrozumieć złożoności obliczeniowej problemu pokrycia zestawu, jeśli najpierw nie zrozumiesz prostych (i nie tak prostych) specjalnych przypadków, takich jak pokrycia wierzchołków, pokrycia krawędzi, zestawy dominujące itp.

— Jukka Suomela

3

Jak zauważono na en.wikipedia.org/wiki/Vertex_cover#Properties, wierzchołki nie w najmniejszej osłonie wierzchołków tworzą największy niezależny zestaw, więc są to zasadniczo ten sam problem. Istnieje wiele rzeczywistych zastosowań niezależnego zestawu problemów, na przykład ponieważ każdy problem związany z satysfakcją z ograniczeń można bezpośrednio do niego zredukować.

— András Salamon,

5

@ András: To dobra uwaga, ale korespondencja dotyczy tylko najmniejszej pokrywy wierzchołków i największego niezależnego zestawu. Z punktu widzenia dokładnych algorytmów są to zasadniczo ten sam problem, ale jeśli interesują nas wydajne algorytmy, zwykle jesteśmy zadowoleni z pewnego rodzaju przybliżeń. A potem okazuje się, że problem pokrycia wierzchołków ma unikalne właściwości, które nie są współdzielone z problemem niezależnego zestawu. Mój ulubiony przykład pochodzi z przetwarzania rozproszonego: małe osłony wierzchołków nie wymagają łamania symetrii, wymagają tego duże niezależne zestawy.

— Jukka Suomela,

13

Niektóre problemy w dziedzinie biologii obliczeniowej wydają się odpowiednie do praktycznych zastosowań, które nie są sztuczne - a przynajmniej nie są tak sztuczne, jak problemy wymienione przez Jukkę Suomela.

Na przykład ludzie często wspominają pracę F. Abu-Khzama, R. Collinsa, M. Fellowsa, M. Langstona, W. Sutersa C. Symonsa, Kernelization Algorytmy for the Vertex Cover Problem: Theory and Experiments , Proceedings of the 6. Warsztaty nt. Inżynierii algorytmów i eksperymentów (ALENEX), ACM / SIAM, Proc. Applied Mathematics 115, 2004.

Jak twierdzą autorzy: „Jedna z aplikacji, do których zastosowaliśmy nasze metody, polega na znalezieniu drzew filogenetycznych na podstawie informacji o domenie białkowej, ...” (sekcja 8 powyższej pracy).

Część autorów ma podobne artykuły na ten temat, patrz np. Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag i Christopher T. Symons, Skalowalne równoległe algorytmy dla problemów FPT , Algorytmica, Tom 45, Numer 3 , 269–284.

Nie jestem pewien, czy instancje użyte w eksperymentach były instancjami z prawdziwego świata, czy sztuczne, ale mam nadzieję, że te dwa odniesienia stanowią dobry punkt wyjścia.

— Alexander Langer
źródło

4

„przynajmniej nie tak sztuczne, jak problemy wspomniane przez Jukkę Suomelę” - i starałem się uważać, aby nie wspominać tutaj o żadnych problemach!

— Jukka Suomela

9

Przykładem może być to, że krawędzie wykresu reprezentują drogi, a wierzchołki reprezentują skrzyżowanie. Zadaniem jest umieszczenie kamer bezpieczeństwa na rozdrożu w sposób, który pozwoli zobaczyć całe miasto, ale pożądane jest używanie jak najmniejszej liczby kamer, aby zaoszczędzić pieniądze.

— galbarm
źródło

21

Problem z przykładami takimi jak ten polega na tym, że są to najczęściej zabawki. Można ich użyć do zilustrowania definicji, ale nie sądzę, że można znaleźć odniesienia do rzeczywistych przykładów, w których ludzie wybrali lokalizacje kamer bezpieczeństwa, znajdując minimalną osłonę wierzchołków. Takie problemy w świecie rzeczywistym mają zwykle dodatkowe ograniczenia, z których wiele nie jest nawet dobrze zdefiniowanych, a rozwiązania są chciwe i przyrostowe (najpierw zainstaluj kilka kamer bezpieczeństwa w najbardziej krytycznych lokalizacjach, a następnie dodaj więcej kiedy otrzymamy więcej funduszy).

— Jukka Suomela,

Odepchnęłam trochę od zarzutu Jukki. Przydaje się destylacja problemu do głównej części, która jest trudna obliczeniowo lub koncepcyjnie. Mimo wszystkich dodatkowych ograniczeń w świecie rzeczywistym myślę, że podstawową trudnością obliczeniową przy wyborze kamer do pokrycia przestrzeni w świecie rzeczywistym jest zasadniczo problem z pokrywą wierzchołków. Oczywiście w tym przypadku algorytm aproksymacyjny jest całkowicie w porządku; znalezienie najlepszej osłony wierzchołków nie jest konieczne. W tym przypadku wykresy będą dość proste, na przykład być może płaskie.

— 6005

8

Możesz także zajrzeć na stronę http://www.dharwadker.org/pirzada/applications/ . Chodzi o zastosowania teorii wykresów. Podaje także niektóre zastosowania do pokrywania wierzchołków, na przykład w biochemii i rozwiązywaniu problemu montażu SNP lub problemu bezpieczeństwa sieci komputerowej.

— saeedn
źródło

1

Dla mnie było nieco zaskakujące, że minimalna pokrywa wierzchołków jest podproblemem węgierskiego algorytmu , mianowicie przy określaniu minimalnego zestawu linii poziomych lub pionowych, które pokrywają wszystkie zera, które zostały wygenerowane przez odjęcie minimów wierszy i kolumn.

Sprowadza się to do znalezienia minimalnego pokrycia wierzchołka na dwuczęściowym grafie, który również, co zaskakujące, można rozwiązać w czasie wielomianowym, dobrze opisanym tutaj

— Manfred Weis
źródło

0

Okładka wierzchołków (a raczej jej różne obliczenia / przybliżenia) była głównym silnikiem algorytmicznym w naszym artykule na temat klasyfikacji najbliższych sąsiadów: http://ieeexplore.ieee.org/document/6867374/

— Aryeh
źródło