Algoritma pendekatan untuk masalah dalam P

Orang biasanya berpikir tentang solusi yang mendekati (dengan jaminan) untuk masalah NP-hard. Apakah ada penelitian yang terjadi dalam memperkirakan masalah yang sudah diketahui ada di P? Ini mungkin ide yang bagus karena beberapa alasan. Dari atas kepala saya, algoritma perkiraan dapat berjalan dengan kompleksitas yang jauh lebih rendah (atau bahkan konstanta yang jauh lebih kecil), mungkin menggunakan lebih sedikit ruang atau mungkin lebih baik diparalelkan.

Juga, skema yang menyediakan pengorbanan waktu / akurasi (FPTAS dan PTAS) mungkin sangat menarik untuk masalah dalam P dengan batas bawah yang tidak dapat diterima pada input besar.

Tiga pertanyaan: apakah ada sesuatu yang saya lewatkan yang membuat ini jelas merupakan ide yang buruk? Apakah ada penelitian yang terjadi dalam mengembangkan teori algoritma ini? Jika tidak, paling tidak, adakah yang akrab dengan contoh individual dari algoritma tersebut?

Seperti yang ditunjukkan Jukka, geometri komputasi adalah sumber masalah yang kaya yang dapat dipecahkan dalam waktu polinomial, tetapi kami ingin mendapatkan perkiraan cepat. Hasil klasik "ideal" adalah "LTAS" (skema perkiraan waktu linier) yang waktu operasinya berupa - biasanya diperoleh dengan mengekstraksi konstanta (poly ( )) mengukur kernel dari data, dan menjalankan algoritma yang mahal pada kernel tersebut, dengan jaminan bahwa solusi tepat pada kernel adalah solusi perkiraan pada seluruh input.1 /$O(n + \text{poly}(1/\epsilon))$$1/\epsilon$

Ada sejumlah trik, pengurangan dan prinsip, dan buku baru Sariel Har-Peled penuh dengan ini. Saya tidak berpikir ada teori kompleksitas yang kaya seperti itu.

Daftar makalah terbaru yang tidak lengkap yang menemukan solusi perkiraan untuk masalah di$P$

1) Ada sejumlah besar pekerjaan pada solusi perkiraan untuk persamaan linear (dominan diagonal simetris) dalam waktu yang hampir linier$\mathcal{O}(n\cdot\text{polylog}(n))$

(daftar makalah) http://cs-www.cs.yale.edu/homes/spielman/precon/precon.html

(Secara umum sebagian besar pemecah iteratif untuk persamaan linier memiliki prinsip -mengukur solusi yang sebenarnya. Hal yang sama berlaku untuk metode iteratif yang memecahkan masalah yang lebih umum (misalnya, beberapa program cembung / linier)).$\epsilon$

2) solusi Perkiraan untuk min / max pemotongan / mengalir http://people.csail.mit.edu/madry/docs/maxflow.pdf$s-t$

3) Menemukan pendekatan yang jarang dari transformasi Fourier dari sinyal dalam waktu sublinear http://arxiv.org/pdf/1201.2501v1.pdf

4) Menemukan perkiraan komponen utama dari sebuah matriks http://www.stanford.edu/~montanar/RESEARCH/FILEPAP/GossipPCA.pdf

Saya tidak mengetahui teori umum yang dikembangkan pada algoritma aproksimasi untuk masalah dalam P. Namun, saya tahu masalah tertentu, yang disebut perkiraan jarak oracle:

Diberikan grafik tidak berarah tertimbang dengannode dantepi, query point-to-point meminta jarak antara dua node .n = | V | m = | E | s , t ∈ $G = (V, E)$$n = |V|$$m = |E|$$s, t \in V$

Ada trade-off tiga arah antara ruang, waktu kueri, dan perkiraan dalam masalah oracle jarak. Seseorang dapat dengan mudah menjawab setiap permintaan tepat (perkiraan = ) dalam waktu dengan menyimpan matriks jarak semua-pasangan; atau dalam waktu dengan menjalankan algoritma jalur terpendek. Untuk grafik besar, kedua solusi ini mungkin membutuhkan ruang yang sangat besar (untuk menyimpan matriks) atau waktu kueri (untuk menjalankan algoritma jalur terpendek). Karenanya, kami mengizinkan perkiraan.O ( 1 ) O ( m + n log n $1$$O(1)$$O(m + n\log n)$

Untuk grafik umum, state-of-the-art adalah jarak oracle dari Thorup dan Zwick , yang untuk setiap perkiraan , membutuhkan ruang yang optimal. Ini juga memberi Anda trade-off ruang-perkiraan yang bagus.$k$

Untuk grafik sparse, trade-off ruang-perkiraan waktu yang lebih umum dapat ditampilkan .

Kami sering mencari solusi perkiraan untuk masalah sederhana seperti menemukan jalur terpendek dalam grafik, menemukan jumlah elemen unik dalam satu set. Kendala di sini adalah inputnya besar dan kami ingin menyelesaikan masalah dengan menggunakan satu akses data. Ada beberapa algoritma "streaming" yang dirancang untuk mencapai solusi perkiraan dalam waktu linier / hampir linear.

$O(nm)$$n$$m$

Algoritma perkiraan cepat untuk pencocokan maksimum diketahui. Setidaknya satu yang terlintas di pikiran saya segera adalah http://arxiv.org/pdf/1112.0790v1.pdf .

$P$

Saya pikir bahwa seluruh area streaming data dan algoritma sub-linear adalah upaya dalam arah ini. Dalam streaming data, fokusnya adalah pada penyelesaian masalah dalam ruang o (n) dan idealnya O (polylog (n)) sedangkan dalam algoritma sub-linier Anda mencoba mendapatkan algoritme dengan waktu berjalan o (n). Dalam kedua kasus tersebut, seseorang seringkali perlu berkompromi dengan memiliki algoritma aproksimasi acak.

Anda bisa mulai dengan materi di halaman ini dan ini .

$\epsilon$$\epsilon$. Ada sejumlah makalah tentang penyelesaian kasus-kasus khusus masalah pemrograman linier seperti arus multikomoditas (dan lebih umum pengepakan dan mencakup piringan hitam) sekitar. Tidak ada teori aproksimasi terpisah untuk masalah dalam P vs masalah yang ada di NP (kita tidak tahu apakah P sama dengan NP atau tidak). Seseorang dapat berbicara tentang teknik tertentu yang berlaku untuk kelas masalah tertentu. Misalnya ada teknik umum yang dikenal untuk memecahkan masalah pengemasan dan mencakup program linier dan beberapa varian.

Dimitris menyebutkan pendekatan transformasi fourier. ada banyak penggunaan ini dalam kompresi gambar misalnya dalam algoritma JPEG. [1] meskipun saya belum melihat makalah yang menekankan ini, tampaknya dalam beberapa hal kompresi lossy [2] (dengan batas yang dapat diturunkan) juga dapat diambil sebagai algoritma pendekatan P-time. aspek aproksimasi sangat dikembangkan dan finetuned / khusus dalam arti mereka dioptimalkan sehingga mereka tidak dapat dirasakan oleh penglihatan manusia, yaitu persepsi manusia terhadap artefak enkode (secara kasar didefinisikan sebagai perbedaan antara aproksimasi dan kompresi lossless) diminimalkan.

ini terkait dengan teori tentang bagaimana mata manusia memandang atau dirinya sendiri sebenarnya "mendekati" pengkodean warna melalui beberapa proses seperti algoritmik. dengan kata lain skema / algoritma aproksimasi teoritis sebenarnya sengaja dirancang untuk mencocokkan skema / algoritma aproksimasi fisik / biologis (dikodekan oleh pemrosesan info biologis yaitu neuron dalam sistem visual manusia).

jadi, kompresi erat dengan perkiraan. dalam JPEG transformasi fourier didekati oleh DCT, diskrit cosinus transform [3]. prinsip yang sama diterapkan pada banyak bingkai untuk standar kompresi video MPEG. [4]

[1] kompresi jpeg, wikipedia

[2] kompresi lossy, wikipedia

[3] DCT, transformasi kosinus diskrit, wikipedia

[4] MPEG, wikipedia

Mungkin ini bukan jawaban tepat pertanyaan Anda, karena saat ini saya hanya bisa mengingat beberapa heuristik, tapi saya yakin ada beberapa perkiraan, karena saya pernah melihatnya sebelumnya.

$O(f(k)*|G|^\alpha)$$f(k)$ masalah dan perkiraannya / heuristik (google sederhana menunjukkan hasil pada 2010, 2011), atau algoritma untuk menemukan pohon dekomposisi grafik.

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

adalah tautan ke artikel "Algoritma perkiraan sederhana untuk masalah pencocokan tertimbang" oleh Doratha Drake dan Stefan Hougardy yang membahas masalah pencocokan tertimbang.