min uderzenie zestawu każdej podstawy matroidu

11

Dostajemy matroida. Naszym celem jest znalezienie zestawu elementów o minimalnym rozmiarze, który ma niepuste przecięcie z każdą podstawą matroidu. Czy problem był już badany? Czy to jest w P? Na przykład w matroidach drzew przestawnych minimalny zestaw uderzeń powinien być minimalnym cięciem. Dzięki.

co.combinatorics approximation-algorithms optimization

— Jian
źródło

3

Czy zajrzałeś do książki Schrijvera na temat optymalizacji kombinatorycznej?

— Chandra Chekuri

Sprawdziłem książkę Schrijvera, ale nie znalazłem nic bezpośrednio z nią związanego. Może to być prosty następstwo jakiegoś wyniku w książce. Jednak nie znalazłem tego :-(

— jian

11

Chciałem zostawić to jako komentarz, ale nie mam jeszcze takiej reputacji. To pytanie zostało poruszone w Mathoverflow, gdzie wspominam, że problem jest NP-zupełny.

Zobacz tutaj .

$U_{k,n}$ $k$ $n$ $(1/k, 1/k, \dots, 1/k)$ $c$ $n/k$ $U_{k,n}$ $n-k+1$

— Tony Huynh
źródło

Dzięki, to był mój błąd, myśląc, że pierwotność jest całką z powodu całkowitej podwójnej integralności, ale mam pomieszane znaki, jak się wydaje.

— Chandra Chekuri

Bez obaw; To się przydarza każdemu z nas. =)

— Tony Huynh

3

Aktualizacja : Jak wskazano, argument jest niepoprawny. Błąd jest w ostatnim wierszu, w którym myślałem, że można uzyskać całkowitą podwójną integralność, ale pierwotne obejmuje LP i nie działa.

$x(e)$ $e$ $\min \sum_e c(e) x(e)$ $\sum_{e \in B} x(e) \ge 1$ $B$ $x(e) \ge 0$ $e$ $c$ $c$ jest integralną podwójnością jest integralną. Oznacza to, że pierwotność jest całką.

— Chandra Chekuri
źródło

Dzięki, Chandra. Podwójność jest rzeczywiście złagodzeniem problemu pakowania podstawowego, co wydaje się także u P. Ale LP nie jest integralną częścią, jak powiedział Tony.

— jian

0

Tak długo, jak możesz, w czasie wielomianowym w liczbie elementów, sprawdź, czy zestaw H elementów jest zestawem uderzeń, a jeśli nie, znajdź jedną bazę, która nie jest trafiona, wtedy problem wchodzi w zakres problemów z niejawnym zestawem uderzeń. . Zobacz następujący artykuł dotyczący algorytmów i dyskusji.

— Danu
źródło