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ść.
Odpowiedzi:
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ą.
źródło
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.
źródło
Tak, i zdecydowanie będę się za to reklamować!
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.
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 :ith
Problemi
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ć.
źródło
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.
W pełni zgadzam się z formatem zaproponowanym w odpowiedzi Anthony'ego Labarre'a.
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.
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.
źródło