Menghitung jarak dengan perkiraan kurang dari 2 dalam grafik umum?

Diberikan grafik tidak berarah tertimbang dengan tepi, saya ingin menghitung jarak perkiraan kurang dari 2 antara setiap pasangan simpul. Tentu saja, saya ingin menggunakan ruang subquadratic dan waktu permintaan sublinear. $m = o(n^2)$

Saya mengetahui hasil Zwick yang menggunakan perkalian matriks, tetapi saya ingin tahu apakah ada algoritma kombinatorial yang dikenal untuk masalah ini?

ds.algorithms graph-algorithms Siddhartha
sumber

Hai @Siddhartha, saya minta maaf jika ini adalah pertanyaan bodoh: hasil Zwick tampaknya menggunakan ruang kuadrat, apakah itu benar?

Hsien-Chih Chang 張顯之

Juga, apakah kesalahan aditif diizinkan?

Hsien-Chih Chang 張顯之

@ Hsien-ChihChang 張顯之 - Saya tertarik pada hasil hanya pada perkiraan multiplikatif. Kasus perkiraan aditif mungkin menarik dalam dirinya sendiri - lebih mudah untuk grafik yang padat, saya kira. Seseorang dapat menggunakan kunci pas dan mendapatkan perkiraan aditif untuk grafik yang cukup padat. Untuk grafik jarang, sejauh yang saya tahu, kunci pas tidak akan membantu.

Siddhartha

Apakah argumen berikut ini tidak berfungsi? Pertimbangkan grafik dengan simpul dan tepi . Pertimbangkan semua bobot tepi menjadi . oracle jarak apa pun yang dapat melakukan aproksimasi yang lebih baik dari , dapat digunakan untuk memutuskan untuk setiap sisi yang mungkin, apakah itu dalam grafik atau tidak. Tapi itu tentu saja menyiratkan bahwa oracle jarak seperti itu harus menggunakan bit . Tidak? (Argumennya adalah bit handwavy tetapi harus benar.) (Secara formal, jumlah bit adalah , di mana . Ini adalah .

G

$G$

n

$n$

m

$m$

1

$1$

2

$2$

Ω (m)

$\Omega(m)$

\log_{2} (\binom{N}{m})

$\log_2 \binom{N}{m}$

N = (\binom{n}{2})

$N=\binom{n}{2}$

\geq m \log_{2} (N / m)

$\geq m \log_2 (N/m)$

Sariel Har-Peled

Terima kasih Sariel - dimungkinkan untuk menurunkan lebih rendah tapi saya baik-baik saja dengan itu. Yang saya ingin miliki hanyalah ruang subquadratic dan waktu permintaan sublinear. Untuk grafik dengan tepi, batas bawah tidak mengatakan apa-apa untuk masalah - apakah itu benar?

Ω (m)

$\Omega(m)$

m = o (n^{2})

$m = o(n^2)$

Ω (m)

$\Omega(m)$

Siddhartha

Jawaban:

Sejauh yang saya tahu, tidak ada hasil yang dipublikasikan pada jarak komputasi perkiraan kurang dari 2 dalam ruang subquadratic dan waktu permintaan sublinear. Untuk mendapatkan perkiraan jarak dengan cepat, Anda mungkin ingin melihat hasil dan referensi dalam "Algoritma Lebih Cepat untuk Semua-Pasangan Perkiraan Jalur Terpendek" oleh Baswana dan Kavitha (versi jurnal dari makalah FOCS mereka memiliki tinjauan yang baik tentang pekerjaan terkait); tidak ada yang mencapai ruang subquadratic.

Untuk mendapatkan perkiraan jarak secara kompak, Anda mungkin ingin melihat hasil dan referensi di dua makalah di atas. [Sebagai tambahan untuk jawaban oleh Gabor, kata hati-hati: hati-hati tentang gagasan sparsity dalam makalah di atas - untuk perkiraan , grafik dikatakan jarang jika , karena Anda mungkin sudah tahu]. $2$ $m = o(n^2)$

Seperti Sariel tunjukkan dalam salah satu komentar di atas, batas bawah alami pada ruang untuk menghitung jarak perkiraan kurang dari adalah , yaitu linear dalam ukuran grafik. Jika waktu kueri tidak dibatasi, batas bawah ini tidak dapat ditingkatkan (sepele, seseorang dapat menggunakan algoritma jalur terpendek dengan hanya menyimpan grafik). Untuk waktu kueri konstan, saya tahu dua batas bawah. Pertama, Patrascu dan Roddity memiliki beberapa batas bawah bersyarat dalam makalah FOCS 2010 mereka yang berlaku untuk aproksimasi kurang dari . Kedua, Sommer et. Al. memiliki beberapa batas bawah untuk grafik yang sangat jarang. Saya tidak mengetahui adanya batas bawah (non-sepele) lainnya. $2$ $\Omega(m)$ $2$

Dalam hal batas atas, hasil dari makalah di atas tampaknya tidak menyamaratakan kurang dari . Kami baru saja membuat beberapa kemajuan dalam masalah ini. Makalah itu seharusnya ada di ArXiv segera, tetapi jika Anda suka, kirimi saya email dan saya akan dengan senang hati membagikan kertas itu. $2$

Semoga ini membantu.

~ Rachit Agarwal

Rachit
sumber

Anda mungkin tertarik dengan makalah INFOCOM 2011 Rachit Agarwal:

Rachit Agarwal, P. Brighten Godfrey, Sariel Har-Peled, Perkiraan Jarak Perkiraan dan Perutean Ringkas dalam Grafik Jarang, IEEE INFOCOM 2011

Dari abstrak:

[Untuk grafik] dengan derajat rata-rata , kasus khusus struktur data kami mengambil peregangan 2 jalur dengan ruang [...] dengan biaya waktu permintaan. $\Theta(\log n)$ $O(n^{3/2})$ $O(\sqrt{n})$

Perhatikan bahwa oracle jarak mereka hanya untuk grafik jarang, tetapi batas derajat logaritmik tampaknya masuk akal. Bonus tambahan, algoritma ini juga berfungsi untuk grafik tertimbang.

Gabor Retvari
sumber

Anda mungkin juga ingin melihatnya

Pătraşcu, Roditty, Oracle Jarak Di Luar Thorup - Zwick Bound , FOCS 2010

Mereka memiliki oracle jarak ukuran dengan stretch 2. Mendukung query dalam waktu yang konstan. $O(n^{5/3})$

zotachidil
sumber

Terima kasih! Makalah dari Agrawal dan Mihai tampaknya tidak mengatakan apa-apa tentang perkiraan "kurang dari" 2, kecuali saya melewatkan sesuatu.

Siddhartha

Memang tidak, tetapi mungkin memberi Anda ide tentang cara mendapatkan trade-off untuk meningkatkan peregangan.

zotachidil