Ringkasan Hasil Perkiraan dan Kekerasan Terbaik untuk masalah optimasi NP

26

Apakah Anda tahu wiki terbaru yang didedikasikan untuk masalah optimasi NP dengan hasil pendekatan dan kekerasan terbaiknya?

Berdasarkan umpan balik, tampaknya aman untuk mengasumsikan tidak ada sumber daya seperti itu (lihat bagian akhir dari pertanyaan ini untuk dua opsi tutup). - ditambahkan pada 8 Februari.

Karena ada sejumlah besar hasil dan masalah yang diperkenalkan dalam dua dekade terakhir, keberadaan wiki khusus dapat menjadi bantuan besar bagi siswa dan profesional yang bekerja pada subjek algoritme aproksimasi dan kekerasan aproksimasi.

Saya disarankan untuk memulai wiki baru. Saya suka idenya, tetapi saya perlu umpan balik sebelum memulai:
Apakah Anda tertarik dengan wiki yang ditujukan untuk subjek di atas dan apakah Anda akan berkontribusi sesuatu? Apa format pilihan Anda untuk wiki ini (lihat format pilihan saya di komentar)? Haruskah kita menggunakan wiki farm atau mesin wiki? Dalam kasus terakhir, apa saran Anda untuk mesin wiki? MediaWiki?

Dua opsi terdekat yang saya ketahui, adalah:
1- "Ringkasan masalah optimasi NP," diedit oleh Pierluigi Crescenzi dan Viggo Kann: Kompendium ini tampaknya sudah ketinggalan zaman. Saya pikir volume hasil saat ini tidak dapat dikelola oleh beberapa orang dan jika kami ingin daftar terbaru, kami harus memiliki wiki.
2- Wikipedia: Wiki ini untuk khalayak umum dan Anda tidak dapat memiliki halaman pendek hanya termasuk deskripsi masalah, dan hasil perkiraan dan kekerasan terbaik.

ds.algorithms reference-request approximation-algorithms approximation-hardness Babak Behsaz
sumber
1
Saya percaya kita dapat menyimpulkan dengan aman bahwa tidak ada sumber daya seperti itu.
Jukka Suomela
3
@Suresh Saya sedang memikirkan sebuah halaman pendek yang hanya berisi deskripsi masalah (contoh, solusi, dan fungsi tujuan) dan hasil pendekatan dan kekerasan terbaik dengan asumsi masing-masing dan tidak mengandung riwayat, motivasi, deskripsi algoritma, dll. Halaman dengan format ini lebih mudah dibuat dan Anda dapat menemukan hasil terbaru lebih cepat daripada halaman wikipedia. Kompendium yang diedit oleh Crescenzi dan Kann cocok dengan profil ini, tetapi ini bukan wiki dan karena itu sudah ketinggalan zaman.
Babak Behsaz
8
Anda perlu sesuatu seperti kompleksitas kebun binatang itu. mungkin Anda harus memulai dan meminta sukarelawan dari sini untuk membantu mengisinya.
Suresh Venkat
2
Wiki akan bermanfaat. Namun, saya akan berpikir bahwa itu harus lebih dari sekadar masalah dan hasil yang paling diketahui. Masalah dengan pendekatan ini adalah bahwa hal itu akan sangat berguna untuk teori orang sementara halaman dengan informasi lebih banyak kemungkinan akan berguna bagi para praktisi; orang dapat berbicara tentang kasus khusus yang diketahui dan hasil terkait dll. Mengapa tidak memanfaatkan tautan, komentar, referensi dll?
Chandra Chekuri
2
Apa pun yang Anda lakukan, saya sangat menyarankan Anda mencoba membuat tautan di antara hasil seperti kompleksitas kebun binatang. Sangat berguna untuk mengetahui bahwa peningkatan perkiraan untuk masalah X menyiratkan sesuatu untuk Y, dan seterusnya .. Juga, hierarki asumsi kekerasan Johnson Johnson (dalam kolom baru-baru ini) adalah sesuatu yang harus ada di sana juga.
Suresh Venkat

Jawaban:

9

Saat Anda merujuk pada ringkasan Crescenzi-Kann, saya tidak yakin apakah Anda merujuk pada buku atau situs web . Buku ini kedaluwarsa tetapi penulis mencoba untuk terus memperbarui situs web. Tampaknya titik awal yang logis adalah mendekati Crescenzi dan Kann dengan proposal Anda.

Timothy Chow
sumber
Adalah baik untuk mengetahui bahwa penulis bersedia untuk terus memperbarui situs web. Saya mendapat kesan bahwa mereka berhenti memperbarui pada Maret 2000 karena sebagian besar halaman mengatakan bahwa mereka terakhir diperbarui pada 2000-03-20.
Tsuyoshi Ito
3
Saya merujuk ke situs web. Saya tidak yakin apakah mereka mengeditnya secara aktif lagi. Saya sendiri ingat melaporkan peningkatan pada perkiraan rasio masalah, tetapi mereka tidak memperbaruinya. Ngomong-ngomong, aku setuju kalau menghubungi Crescenzi dan Kann logis tentang status ringkasan mereka dan kemungkinan mengubahnya ke wiki.
Babak Behsaz
1
@Suresh @Anthony @Florent @Tsuyoshi @Jukka @Gianluca: Saya tidak dapat menemukan informasi kontak (Dr.?) Pierluigi Crescenzi. Jadi, saya mengirim email ke profesor Kann pada 9 Februari dan tidak menerima jawaban. Pada 16 Februari, saya meneruskan email saya sebelumnya ke subeditor dari kompendium Profesor Karpinski dan Woeginger, tetapi sekali lagi saya tidak menerima jawaban. Saya mengirim kedua email dengan alamat email akademis saya, jadi saya kira mereka belum berakhir di folder spam mereka. Apa saran Anda sekarang?
Babak Behsaz
Saya kira kemudian wiki baru dapat dimulai. Jika pada beberapa titik penulis ringkasan asli mengeluhkannya, solusi akan mudah ditemukan (misalnya menggabungkan dua sumber daya yang ada)
Florent Foucaud
@Babak: Jika Anda masih tertarik, Anda dapat menemukan email Prof. Crescenzi di sini
Gianluca Della Vedova
7

Complexity Garden adalah wiki yang dikhususkan untuk masalah komputasi dan hubungannya dengan kelas kompleksitas. Seperti yang disarankan di sini, saya berencana untuk memulai wiki baru untuk hasil algoritmik, tetapi saya pikir ketika ada satu wiki untuk masalah komputasi, kita dapat memiliki semua informasi di satu tempat. Jadi, saya menghubungi orang-orang Kebun Binatang dan dengan izin mereka, mengubah ruang lingkup Taman untuk memasukkan hasil algoritmik juga.

Sekarang, saya perlu sekelompok kecil orang untuk membantu saya mengisi wiki ke ukuran yang kita dapat mengumumkannya secara publik dan menarik lebih banyak kontributor. Karena wiki ini menggunakan sistem yang sama dengan wikipedia, dibutuhkan rata-rata 15-25 menit untuk menambahkan masalah. Jadi, bahkan dengan sekelompok 5 orang yang berkontribusi hanya 3 masalah lemah (yaitu sekitar 1 jam per lemah), kita dapat menambahkan 60 masalah dalam sebulan dan memiliki total 100 masalah di Complexity Garden.

Babak Behsaz
sumber
1
Apa status inisiatif Anda?
Florent Foucaud
Saya tidak melihat tambahan di halaman itu setelah 25 Agustus, jadi saya menganggap Babak berkecil hati karena kurangnya peserta. Saya ketinggalan pengumuman ini, dan akan mencoba berkontribusi secepatnya.
Anthony Labarre
1

Apakah Anda tertarik pada wiki yang ditujukan untuk subjek di atas

Ya, dan saya pasti akan beriklan untuk itu!

dan apakah Anda akan berkontribusi sesuatu?

Saya akan berkontribusi sebanyak mungkin, tetapi jangan berharap saya menjadi salah satu penyedia konten utama. Seperti yang ditunjukkan oleh Tsuyoshi Ito, ini bisa menghabiskan waktu, dan saya tidak melihat diri saya sebagai orang yang paling berpengetahuan luas di area ini (di situs web ini atau di tempat lain).

Tetapi konten pada akhirnya akan tumbuh dengan basis pengguna, jadi saya rasa Anda tidak perlu terlalu khawatir tentang komitmen orang untuk berkontribusi, misalnya 10 halaman setiap hari.

Apa format pilihan Anda untuk wiki ini (lihat format pilihan saya di komentar)?

Ada pertanyaan tentang berapa banyak konten yang ingin Anda berikan dan audiens mana yang Anda targetkan. Jika saya ingin mengetahui apakah masalah saya sulit, seperti yang saya tulis di atas, ada baiknya untuk melihat sekilas apa yang tampak seperti daftar di mana item akan menjadi:ith

Masalahi

  • Contoh: ...
  • Pertanyaan: ...
  • Referensi: Untuk kekerasan, lihat [i1], untuk tidak dapat diperkirakan, lihat [i2], ...

Itulah yang digunakan Garey & Johnson's dan Kann & Crescenzi. Masalah juga dapat ditandai menggunakan kategori sesuai keinginan kita, sehingga daftar masalah berdasarkan kategori dapat dengan mudah dihasilkan (seperti pada lezat: klik tag "teori-teori", dan lihat daftar setiap masalah sulit dalam grafik teori di situs web).

Informasi lebih rinci dapat diberikan dengan mengklik nama masalah dalam daftar, yang akan berisi misalnya daftar kasus "mudah", masalah terbuka (mis. "Perkiraan terbaik adalah 3/2, bisakah kita melakukan yang lebih baik?") tautan ke Wikipedia atau orang lain untuk audiens yang lebih luas, perangkat lunak khusus, ...

Anda juga dapat, seperti yang dilakukan G&J, memberikan informasi tentang bagaimana hasil diperoleh ("transformasi dari X3C"). Dan kemudian Anda mungkin bisa menghasilkan grafik yang menunjukkan pengurangan di antara masalah yang berbeda, yang akan membuat orang bertanya-tanya apakah ada lebih banyak bukti langsung, tapi yah ... Anda harus berhenti di suatu tempat ;-)

Saya akan melewatkan sub-pertanyaan terakhir karena saya tidak tahu bagaimana menjawabnya.

Anthony Labarre
sumber
Saya pikir memulai wiki tidak perlu terlalu banyak usaha. Anda hanya perlu mengkonfigurasi mesin wiki (seharusnya tidak terlalu sulit), menulis halaman utama, menulis halaman tentang format halaman wajib dan menulis halaman contoh (misalnya untuk masalah sampul yang ditetapkan). Sisanya dapat dilakukan dalam perjalanan waktu. Ini mungkin tampak sedikit sederhana, tetapi saya pikir jika ada minat yang cukup dari komunitas teori, masalah akan diselesaikan dalam perjalanan waktu dan wiki akan tumbuh.
Babak Behsaz
1
@ Bakak: Saya pikir Anda pasti membutuhkan konten asli untuk memulai. Konten nyata ini dapat menjadi salin dan rekat dari ringkasan jika penulis senang tentang hal itu. Sulit membayangkan bahwa kotak kosong hanya dengan sistem akan menarik pengguna.
Tsuyoshi Ito
@ Kalau saya pikir pada awalnya mayoritas pengguna akan menjadi orang-orang yang ingin berkontribusi pada wiki, belum tentu menggunakannya. Saya tidak yakin berapa banyak anggota komunitas suka berkontribusi dengan cara ini, tetapi saya sendiri akan melakukan ini jika ada wiki yang hampir kosong. Intinya adalah bahwa antara dua pilihan tidak memiliki wiki atau memiliki sistem kerja kosong, mana yang lebih baik. Saya pikir yang terakhir ini tidak berbahaya. Jika kita dapat menemukan beberapa orang yang ingin lebih berupaya di wiki (mis. Menyalin materi ringkasan dengan izin), maka itu bagus.
Babak Behsaz
Menyalin (dengan izin) isi ringkasan tidak boleh terlalu banyak usaha, dan akan cukup untuk titik awal. Sebenarnya mengapa tidak mengusulkan penulis untuk mengubah ringkasan yang ada menjadi wiki?
Florent Foucaud
2
@ Bakak: Saya setuju bahwa sistem kerja kosong tidak berbahaya. Saya hanya ingin memaksimalkan probabilitas keberhasilan. Untuk melakukannya, saya percaya bahwa konten yang sebenarnya adalah faktor kunci. Saya berharap bahwa penulis ringkasan saat ini bersedia mengubahnya menjadi wiki.
Tsuyoshi Ito
1

Apakah Anda tertarik pada wiki yang ditujukan untuk subjek di atas dan apakah Anda akan berkontribusi sesuatu?

Saya tertarik dan saya bersedia berkontribusi, setidaknya sedikit dalam bidang keahlian kecil saya. Saya tidak begitu mengerti mengapa Anda ingin membatasi perhatian Anda pada perkiraan. Misalnya ada juga Kompendium Masalah Parameter yang sudah usang yang dikhususkan untuk algoritma Parameter-tetap.

Juga, bagian terakhir dari G&J dapat dilihat sebagai ringkasan NP-hardness.

IMHO, Anda harus memikirkan Kompendium Masalah Komputasi di mana, untuk setiap masalah, Anda menyatakan hasil yang paling relevan (baik atau buruk).

Apa format pilihan Anda untuk wiki ini (lihat format pilihan saya di komentar)?

Saya sepenuhnya setuju dengan format yang diusulkan dalam jawaban Anthony Labarre.

Haruskah kita menggunakan wiki farm atau mesin wiki?

Saya memiliki sedikit preferensi untuk wiki yang di-host sendiri, tetapi wiki yang di-host akan baik-baik saja.

Satu-satunya saran saya adalah, jika Anda memilih pertanian wiki, pastikan Anda dapat mengekspor semua data. Anda tidak dapat memastikan bahwa pertanian akan ditutup suatu hari.

Dalam kasus terakhir, apa saran Anda untuk mesin wiki? MediaWiki?

Persyaratan IMHO adalah untuk memilih mesin yang mendukung format LaTeX. Mediawiki dan Dokuwiki adalah yang paling luas dan keduanya merupakan pilihan yang sangat baik.

Mediawiki sedikit lebih rumit untuk diinstal dan dikelola (saya akan mengatakan cukup kompleks) tetapi sintaksisnya sepertinya tidak asing bagi sebagian besar calon kontributor.

Dokuwiki lebih ringan (baik dalam sumber daya yang dibutuhkan dan upaya manajemen) tetapi sintaksisnya sebagian berbeda dari Mediawiki.

Gianluca Della Vedova
sumber