Kompendium najlepszych wyników aproksymacji i twardości dla problemów optymalizacji NP

26

Czy znasz jakieś aktualne wiki poświęcone problemom z optymalizacją NP z najlepszym wynikiem przybliżenia i twardości?

Na podstawie informacji zwrotnych wydaje się, że można bezpiecznie założyć, że nie ma takiego zasobu (zobacz dwie odpowiedzi na końcu tego pytania). - dodano 8 lutego.

Ponieważ w ciągu ostatnich dwóch dziesięcioleci pojawiło się mnóstwo wyników i problemów, istnienie dedykowanej wiki mogłoby być wielką pomocą dla studentów i profesjonalistów pracujących na temat algorytmów aproksymacji i jej twardości.

Zaproponowano mi założenie nowej wiki. Podoba mi się ten pomysł, ale potrzebuję informacji zwrotnych przed rozpoczęciem:
Czy interesuje Cię wiki poświęcone powyższemu tematowi i czy zamierzasz coś wnieść? Jaki jest twój preferowany format dla tej wiki (zobacz mój preferowany format w komentarzach)? Czy powinniśmy używać farmy wiki lub silnika wiki? W tym drugim przypadku, jaka jest Twoja sugestia dla silnika wiki? MediaWiki?

Dwie najbliższe znane mi opcje to:
1- „Kompendium problemów z optymalizacją NP”, pod redakcją Pierluigi Crescenzi i Viggo Kann: Kompendium to wydaje się nieaktualne. Myślę, że kilka bieżących wyników nie może być zarządzanych przez kilka osób, a jeśli chcemy aktualnej listy, powinniśmy mieć wiki.
2-Wikipedia: Ta wiki jest dla ogółu odbiorców i nie możesz mieć krótkiej strony zawierającej opis problemu oraz najlepsze przybliżenie i twardość.

— Babak Behsaz
źródło

1

Uważam, że możemy bezpiecznie stwierdzić, że nie ma takich zasobów.

— Jukka Suomela,

3

@Suresh Myślałem o krótkiej stronie zawierającej tylko opis problemu (tj. Instancje, rozwiązania i funkcję celu) oraz najlepsze wyniki przybliżenia i twardości z ich odpowiednimi założeniami i nie zawierające historii, motywacji, opisu algorytmu itp. Strona z ten format jest łatwiejszy do utworzenia i możesz znaleźć najnowsze wyniki szybciej niż strona wikipedia. Kompendium edytowane przez Crescenzi i Kann pasuje do tego profilu, ale nie jest to wiki, a więc jest nieaktualne.

— Babak Behsaz

8

potrzebujesz wtedy czegoś w rodzaju złożonego zoo. może powinieneś założyć jednego z nich i poprosić o pomoc ochotników, aby go wypełnić.

— Suresh Venkat

2

Przydałaby się wiki. Sądzę jednak, że powinien to być nie tylko problem i najlepiej znany wynik. Problem z tym podejściem polega na tym, że przydaje się głównie do teorii ludzi, podczas gdy strona z większą ilością informacji może być przydatna dla praktyków; można mówić o znanych specjalnych przypadkach i powiązanych wynikach itp. Dlaczego nie wykorzystać w pełni linków, komentarzy, referencji itp.?

— Chandra Chekuri

2

Bez względu na to, co ostatecznie skończysz, zdecydowanie zalecam próbę nawiązania połączeń między wynikami, takimi jak zoo złożoności. Warto wiedzieć, że poprawa aproksymacji dla problemu X implikuje coś dla Y i tak dalej. Również hierarchia założeń twardości Davida Johnsona (w ostatniej kolumnie) również powinna tam być.

— Suresh Venkat

9

Kiedy odwołujesz się do kompendium Crescenzi-Kann, nie jestem pewien, czy masz na myśli książkę lub stronę internetową . Książka jest nieaktualna, ale autorzy starają się na bieżąco aktualizować witrynę. Wydaje się, że logicznym punktem wyjścia jest podejście do Crescenzi i Kanna z twoją propozycją.

— Timothy Chow
źródło

Warto wiedzieć, że autorzy są skłonni do ciągłego aktualizowania strony internetowej. Miałem wrażenie, że przestały się aktualizować w marcu 2000 r., Ponieważ większość stron twierdzi, że zostały ostatnio zaktualizowane w dniu 2000-03-20.

— Tsuyoshi Ito,

3

Mam na myśli stronę internetową. Nie jestem pewien, czy edytują go już aktywnie. Sam pamiętam, że zgłosiłem poprawę stosunku przybliżenia problemu, ale go nie zaktualizowali. W każdym razie zgadzam się, że logiczne jest skontaktowanie się z Crescenzi i Kannem w sprawie statusu ich kompendium i możliwości zmiany go na wiki.

— Babak Behsaz

1

@Suresh @Anthony @Florent @Tsuyoshi @Jukka @Gianluca: Nie mogłem znaleźć danych kontaktowych (Dr.?) Pierluigi Crescenzi. Wysłałem więc e-maila do profesora Kanna 9 lutego i nie otrzymałem odpowiedzi. 16 lutego przekazałem mój poprzedni e-mail subedytorom profesorów Karpińskiego i Woegingera, ale znowu nie otrzymałem odpowiedzi. Wysłałem oba e-maile z moim akademickim adresem e-mail, więc chyba nie trafiły do folderów spamu. Jaka jest teraz twoja sugestia?

— Babak Behsaz

Myślę, że wtedy mogłaby zostać uruchomiona nowa wiki. Jeśli w pewnym momencie autorzy oryginalnego kompendium narzekają na to, łatwo będzie znaleźć rozwiązanie (np. Połączenie dwóch istniejących zasobów)

— Florent Foucaud

@Babak: Jeśli nadal jesteś zainteresowany, możesz znaleźć e-mail prof. Crescenziego tutaj

— Gianluca Della Vedova

7

Complexity Garden to wiki poświęcona problemom obliczeniowym i ich relacjom z klasami złożoności. Jak zasugerowano tutaj, planowałem założyć nową wiki dla wyników algorytmicznych, ale pomyślałem, że kiedy jest jedna wiki dla problemów obliczeniowych, możemy mieć wszystkie informacje w jednym miejscu. Skontaktowałem się więc z ludźmi z Zoo i za ich zgodą zmieniłem zakres Ogrodu, aby uwzględnić również wyniki algorytmiczne.

Teraz potrzebuję małej grupy osób, które pomogłyby mi zapełnić wiki do rozmiarów, które możemy publicznie ogłosić i przyciągnąć więcej autorów. Ponieważ ta wiki korzysta z tego samego systemu co wikipedia, dodanie problemu zajmuje średnio 15–25 minut. Tak więc, nawet z grupą 5 osób, które przyczyniają się tylko 3 problemy do słabości (tj. Około 1 godziny na słabego), możemy dodać 60 problemów w ciągu miesiąca i mieć łącznie 100 problemów w Ogrodzie Złożoności.

— Babak Behsaz
źródło

1

Jaki jest status twojej inicjatywy?

— Florent Foucaud

Nie widzę żadnych dodatków na tej stronie po 25 sierpnia, więc zakładam, że Babak zniechęcił się z powodu braku uczestników. Spóźniłem się z tym ogłoszeniem i postaram się przekazać jak najszybciej.

— Anthony Labarre,

1

Czy interesuje Cię wiki poświęcone powyższemu tematowi

Tak, i zdecydowanie będę się za to reklamować!

i czy zamierzasz coś wnieść?

Przekażę jak najwięcej, ale nie oczekuj, że będę jednym z głównych dostawców treści. Jak zauważa Tsuyoshi Ito, może to zająć dużo czasu i nie uważam się za najbardziej kompetentną osobę w tym obszarze (na tej stronie internetowej lub w innym miejscu).

Ale zawartość z pewnością ostatecznie wzrośnie wraz z bazą użytkowników, więc nie sądzę, że powinieneś się zbytnio przejmować zaangażowaniem ludzi, np. 10 stron dziennie.

Jaki jest twój preferowany format dla tej wiki (zobacz mój preferowany format w komentarzach)?

Pojawia się pytanie, ile treści chcesz dostarczyć i do jakich odbiorców kierujesz reklamy. Jeśli chcę dowiedzieć się, czy mój problem jest trudny, jak napisałem powyżej, dobrze jest mieć szybki przegląd tego, co wygląda jak lista, w której powinien znajdować się element : $i^{th}$

Problem $i$

Instancja: ...
Pytanie: ...
Odniesienia: twardość, patrz [i1], brak aproksymacji, patrz [i2], ...

Tego używają Garey & Johnson's oraz Kann & Crescenzi. Problemy można również oznaczać za pomocą kategorii według własnego uznania, aby łatwo wygenerować listę problemów według kategorii (coś w rodzaju pysznego: kliknij znacznik „teoria wykresu” i zobacz listę wszystkich trudnych problemów na wykresie teoria na stronie internetowej).

Bardziej szczegółowe informacje można by następnie podać, klikając nazwę problemu na liście, która zawierałaby na przykład listę „łatwych” przypadków, otwartych problemów (np. „Najlepsze przybliżenie to 3/2, czy możemy to zrobić lepiej?”) linki do Wikipedii lub innych dla szerszego grona odbiorców, specjalistycznego oprogramowania, ...

Możesz także, podobnie jak G&J, dostarczyć informacji o sposobie uzyskania wyników („transformacja z X3C”). I wtedy prawdopodobnie mógłbyś wygenerować wykres pokazujący redukcje różnych problemów, co doprowadziłoby ludzi do zastanowienia się, czy istnieją bardziej bezpośrednie dowody, ale cóż ... musisz gdzieś się zatrzymać ;-)

Pominę ostatnie pytanie cząstkowe, ponieważ nie mam pojęcia, jak na nie odpowiedzieć.

— Anthony Labarre
źródło

Myślę, że założenie wiki nie wymaga zbyt dużego wysiłku. Musisz tylko skonfigurować silnik wiki (nie powinno to być takie trudne), napisać stronę główną, napisać stronę o obowiązkowym formacie stron i utworzyć stronę przykładową (np. Dla problemu z ustawioną okładką). Resztę można zrobić z czasem. Może się to wydawać trochę uproszczone, ale myślę, że jeśli zainteresowanie społeczności teoretycznej będzie wystarczające, problemy z czasem zostaną rozwiązane, a wiki się rozwinie.

— Babak Behsaz

1

@Babak: Myślę, że na pewno potrzebujesz prawdziwych treści, aby zacząć. Tę prawdziwą treść można skopiować i wkleić w kompendium, jeśli autorzy są z tego zadowoleni. Trudno sobie wyobrazić, że puste pudełko tylko z systemem przyciągnie użytkowników.

— Tsuyoshi Ito

@Ito Myślę, że na początku większość użytkowników będzie tymi, którzy chcą przyczynić się do wiki, niekoniecznie z niej korzystać. Nie jestem pewien, ilu członków społeczności lubi uczestniczyć w ten sposób, ale sam bym to zrobił, gdyby istniała prawie pusta wiki. Chodzi o to, że między dwiema opcjami nie posiadania wiki lub pustego działającego systemu, który jest lepszy. Myślę, że ten ostatni jest nieszkodliwy. Jeśli znajdziemy ludzi, którzy chcą włożyć więcej wysiłku w wiki (np. Kopiowanie materiałów kompendium za pozwoleniem), to świetnie.

— Babak Behsaz

Kopiowanie (za zgodą) treści kompendium nie powinno być zbyt wielkim wysiłkiem i wystarcza na początek. W rzeczywistości dlaczego nie zaproponować autorom przekształcenia istniejącego kompendium w wiki?

— Florent Foucaud,

2

@Babak: Zgadzam się, że pusty działający system jest nieszkodliwy. Chcę tylko zmaksymalizować prawdopodobieństwo sukcesu. W tym celu uważam, że prawdziwa treść jest kluczowym czynnikiem. Mam nadzieję, że autorzy obecnego kompendium są gotowi zmienić go na wiki.

— Tsuyoshi Ito

1

Czy interesuje Cię wiki poświęcone powyższemu tematowi i zamierzasz coś wnieść?

Jestem zainteresowany i jestem gotów przyczynić się, przynajmniej trochę w mojej małej dziedzinie wiedzy. Naprawdę nie rozumiem, dlaczego chcesz ograniczyć swoją uwagę do przybliżenia. Na przykład istnieje również przestarzałe Kompendium Sparametryzowanych Problemów poświęcone algorytmom o stałych parametrach.

Również ostatnia porcja G&J może być postrzegana jako kompendium twardości NP.

IMHO, powinieneś pomyśleć o Kompendium problemów obliczeniowych, w którym dla każdego problemu podajesz najbardziej istotne (dobre lub złe) wyniki.

Jaki jest twój preferowany format dla tej wiki (zobacz mój preferowany format w komentarzach)?

W pełni zgadzam się z formatem zaproponowanym w odpowiedzi Anthony'ego Labarre'a.

Czy powinniśmy używać farmy wiki lub silnika wiki?

Mam niewielką preferencję dla wiki hostowanego samodzielnie, ale hosting wiki byłby w porządku.

Moją jedyną sugestią jest to, że jeśli wybierzesz farmę wiki, pamiętaj, aby móc wyeksportować wszystkie dane. Nie możesz być pewien, że któregoś dnia farma zostanie zamknięta.

W tym drugim przypadku, jaka jest Twoja sugestia dla silnika wiki? MediaWiki?

IMHO wymaga wyboru silnika obsługującego format LaTeX. Mediawiki i Dokuwiki są najbardziej rozpowszechnione i oba stanowią doskonały wybór.

Mediawiki jest nieco bardziej skomplikowane w instalacji i zarządzaniu (powiedziałbym, że jest umiarkowanie skomplikowane), ale jego składnia prawdopodobnie będzie znana większości potencjalnych współpracowników.

Dokuwiki jest lżejsze (zarówno pod względem potrzebnych zasobów, jak i zarządzania), ale składnia jest częściowo inna niż w Mediawiki.

— Gianluca Della Vedova
źródło