Bagaimana intrinsik adalah

Sebuah -net untuk ruang rentang adalah bagian dari sehingga tidak kosong untuk semua sehingga.( X , R ) N X N ∩ R R ∈ R | X ∩ R | ≥ ε | X $\varepsilon$$(X,\mathcal{R})$$N$$X$$N\cap R$$R\in \mathcal{R}$$|X\cap R| \ge \varepsilon |X|$

Diberi jarak ruang dari dimensi VC , sebuah -net ukuran dapat dihitung dalam waktu(lihat [1], Thm 4.6).d ε O ( $(X,R)$$d$$\varepsilon$O(d)3d($O\left(\frac{d}{\varepsilon}\log\left(\frac{d}{\varepsilon}\right)\right)$$O(d)^{3d}\left(\frac{1}{\varepsilon^2}\log\left(\frac{d}{\varepsilon}\right)\right)^d|X|$

Sejauh mana istilah intrinsik untuk masalah ini? Secara khusus, dapatkah ditingkatkan menjadi ? Apakah ada batas bawah yang diketahui? 2 O ( d $O(d)^{3d}$$2^{O(d)}$

Pertanyaan terkait: apakah ada kondisi umum tentang yang diketahui ada peningkatan seperti itu?$(X,R)$

[1] Bernard Chazelle. Metode Perbedaan. 2000

Jika Anda setuju dengan algoritma acak, maka Anda dapat mengambil sampel secara acak , dan ini akan menjadi -net dengan probabilitas setidaknya . ϵ 1 - $O((d/\epsilon) \log (d/\epsilon \delta))$$\epsilon$$1-\delta$

Untuk algoritma deterministik, saya percaya istilah berasal dari alasan berikut. Anda pertama-tama mempartisi set lengkap Anda ke dalam himpunan bagian ukuran tentang mana adalah ukuran dari -net yang Anda harapkan pada akhirnya. Kemudian Anda menggabungkan dua himpunan bagian seperti itu dan mengurangi menjadi setengah ukuran itu. (Pada dasarnya, ini diulang sampai satu set tersisa.) Langkah reduksi pada dasarnya mempertimbangkan semua rentang menarik dari himpunan ukuran gabungan . Dengan batas VC ada sekitar rentang, dan Anda perlu "memeriksa" masing-masing untuk melihat apakah telah terkena. The memiliki di dalamnya. The s = O ( ( d / ϵ ) log ( d / ϵ ) ) s ϵ 2 s O ( ( 2 s ) d ) s d d O ( d ) d s $d^{O(d)}$$s = O((d/\epsilon) \log (d/\epsilon))$$s$$\epsilon$$2s$$O((2s)^d)$$s^d$$d^{O(d)}$$d$di jangka diperlukan. Jadi untuk mengurangi batasan ini, menggunakan kerangka kerja deterministik ini, Anda entah bagaimana harus secara implisit "memeriksa" semua rentang tanpa menyebutkannya secara eksplisit. Ini tampaknya sulit dilakukan secara deterministik, tetapi saya tidak yakin saya tahu batas bawah eksplisit - sebagian besar pekerjaan di arena ini mengasumsikan konstan dan menyalahgunakan ini dengan berat. $s$$d$