Aplikasi kombinatorik aditif dalam desain algoritma

12

Saya membaca survei oleh Trevisan dan Lovett tentang aplikasi kombinatorik aditif di TCS. Sebagian besar aplikasi ini berada di bawah kompleksitas komputasi , misalnya batas bawah. Saya ingin tahu apakah kombinatorik aditif telah menemukan aplikasi dalam desain algoritma juga.

Motivasi untuk pertanyaan saya adalah sebagai berikut: sementara hubungan antara aditif kombinatorik dan kompleksitas tampaknya agak alami, saya ingin tahu bagaimana struktur aljabar yang ditemukan oleh kombinatorik aditif dapat dieksploitasi dalam merancang algoritma yang efisien, jika ada. Pointer ke literatur akan dihargai.

ds.algorithms reference-request co.combinatorics pengguna32373
sumber

Saya pikir 'penerimaan' untuk jenis pertanyaan ini tidak ada gunanya, karena tujuannya adalah menyusun daftar petunjuk yang relevan. Tapi, saya menerima Ryan karena hasil yang direferensikan jelas merupakan jenis koneksi yang saya cari: penggunaan kombinatorik aditif eksplisit dalam desain algoritma, dan resolusi yang menarik dalam mengapa BSG gagal memecahkan 3SUM yang terkenal.

user32373

17

Timothy Chan dan Moshe Lewenstein memiliki makalah tentang 3SUM dan masalah terkait dalam STOC mendatang, yang menerapkan versi efektif teorema BSG dari kombinatorik aditif untuk menyelesaikan varian 3SUM lebih cepat daripada n ^ 2 kali.

Lihat tautan ini ke surat kabar Chan .

Ryan Williams
sumber

3 S A T

$3SAT$

1

3 S A T

$3SAT$

3 S A T

$3SAT$

{1.308}^{n}

$1.308^n$

8

The algoritma DC3 untuk menghitung array akhiran mengambil keuntungan dari kombinatorika aditif. Menggunakan perbedaan penutup di bagian kunci dari algoritma. Ide-idenya sangat keren dan mudah diakses. Algoritma ini juga memiliki kinerja yang sangat baik dalam praktik, dan diajarkan secara luas.

$G$ $S$ $g \in G$ $s,t \in S$ $g=s-t$ $G$ $n$

Berikut kutipannya:

Juha Kärkkäinen, Peter Sanders, Stefan Burkhardt. Konstruksi Lini Sufiks Pekerjaan Linier . Jurnal ACM, 2006.

DW
sumber

8

$B$ $n$ $O(2^{0.3399n}B^4)$

Lihat Austrin, P., Kaski, P., Koivisto, M., & Nederlof, J. (2015, Februari). Subset Jumlah dalam Absennya Konsentrasi. Dalam EW Mayr, & N. Ollinger (Eds.), Simposium Internasional ke-32 tentang Aspek Teoritis Ilmu Komputer (STACS 2015) (Vol. 30, hlm. 48-61).

Juho
sumber

5

Jika Anda memasukkan pengujian dalam desain algoritma, Samorodnitsky menggunakan kombinatorik aditif untuk menunjukkan bahwa transformasi linear dapat diuji secara efisien [di sini] .

Manu
sumber

3

Contoh lain adalah karya klasik Coppersmith dan Winorgrad dari tahun 1990 tentang perkalian matriks, yang didasarkan pada kombinatorik aditif

http://www.sciencedirect.com/science/article/pii/S0747717108800132

Shachar Lovett
sumber

Aplikasi kombinatorik aditif dalam desain algoritma

Jawaban: