Jakiś szybki algorytm problemu z ustawieniem łuku zwrotnego przy minimalnych kosztach?

Na ukierunkowanym wykresie , , jeśli jest DAG (ukierunkowany wykres acykliczny), nazywa się zestawem łuku zwrotnego. $G=(V,E)$ $F\subset E$ $G\setminus F$ $F$

Jeżeli każda krawędź jest powiązana z wagą , problem z zestawem łukowym sprzężenia zwrotnego przy minimalnym koszcie polega na znalezieniu takiej, że jest minimalna. $w$ $F$ $W(F)$

Powszechnie wiadomo, że problem z ustawieniem łuku minimalnego sprzężenia zwrotnego jest trudny dla NP, podobnie jak problem z zestawem łuku minimalnego sprzężenia zwrotnego. Zastanawiam się, czy ktoś zna jakiś przybliżony algorytm, który działa dobrze, i wszelkie właściwości funkcji wagi, które mogą dać szybki solver.

ds.data-structures graph-theory np-hardness approximation-algorithms miao
źródło

Wydaje mi się, że zdajesz sobie sprawę z Even, Naor, Schieber, Sudan (1998): „Przybliżanie minimalnych zestawów sprzężeń zwrotnych i multiemisów na wykresach kierowanych” - dx.doi.org/10.1007/PL00009191 ?

Jukka Suomela,

Było kilka niezależnych odkryć aproksymacji polilogarytmicznych dla ogólnego zestawu łuku zwrotnego. W zależności od tego, czego dokładnie szukasz, możesz na nie spojrzeć. Patrz artykuły Leighton i Rao 1999; Seymour 1995; Even i in. 2000; Even i in. 1998 cytowany w moim cs.brown.edu/~ws/papers/fast_journal.pdf .

Warren Schudy,

Chciałem tylko wyjaśnić - czy to prawda, że tylko ukierunkowany problem jest trudny NP, a problem dla grafów niekierowanych można rozwiązać w czasie wielomianowym, patrz np. Dyskusja o przepełnieniu stosu „Jak znaleźć zbocze sprzężenia ustawione w grafie niekierowanym”. Czy to prawda, że problem można rozwiązać w czasie wielomianowym dla grafu bezkierunkowego?

TomR

@TomR Krawędź sprzężenia zwrotnego masy minimalnej ustawiona na niekierowanym wykresie ma drzewo rozpinające wagę maksymalną jako uzupełnienie, które można znaleźć w czasie polytime.

G. Bach,

Może to pomoże: arxiv.org/pdf/1702.07612.pdf okrzyki i powodzenia

user44477

Odpowiedzi:

Daniel Apon powiązał z konferencyjną wersją mojego referatu. Zamiast tego sugeruję wersję roboczą czasopisma: http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf .
Na wykresach turniejowych niektóre prace eksperymentalne sugerują, że lokalne wyszukiwanie działa całkiem dobrze. Zobacz najnowszy dokument ALENEX Anke van Zuylen i Fransa Schalekampfa: http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf .
Jeśli wagi spełniają albo „ograniczenia prawdopodobieństwa”, albo „nierówności trójkąta”, istnieje algorytm aproksymacji o stałym współczynniku oparty na Quicksort. Zobacz najnowszy artykuł JACM Ailona, Charikara i Newmana.
Czy możesz nam powiedzieć coś więcej o tym, jakie rodzaje przypadków masz na myśli i czy szukasz czegoś, co dobrze sprawdzi się w praktyce czy w teorii?

Warren Schudy
źródło

Twój link do Zuylen i Schalekampf ma teraz 404; informatik.uni-trier.de/~ley/pers/hd/s/Schalekamp:Frans

nodakai

Zobacz artykuł „Jak oceniać z kilkoma błędami: PTAS dla ważonego sprzężenia zwrotnego w turniejach” Claire Kenyon-Mathieu i Warren Schudy (STOC 2007, wersja czasopisma na stronie Schudy), który przedstawia schemat aproksymacji czasu wielomianowego dla szczególny przypadek, w którym kierowany wykres jest turniejem.

DS
źródło

Oba artykuły są bardzo interesujące. Poza tym, czy istnieje jakieś podejście oparte na funkcjach podmodularnych?

miao

Proszę podać linki.

Emil

@Emil, skopiuj / wklej nazwę papieru do Google daje PDF w pierwszym hitem: PDF .

Daniel Apon,

Sugerowałem jedynie sposób na poprawienie odpowiedzi.

Emil,