Konsekuensi batas bawah untuk -nets pada pendekatan

Banyak di sini mungkin menyadari batas bawah super-linear baru-baru ini Alon untuk $\epsilon$ jaring dalam pengaturan geometris alami [PDF] . Saya ingin tahu apa, jika ada, seperti batas bawah yang menyiratkan tentang perkiraan masalah Set Cover / Hitting Set yang terkait.

Untuk sedikit lebih spesifik, pertimbangkan keluarga ruang jangkauan, misalnya, keluarga:

$\big\{(X,\mathcal{R})$ : $X$ adalah set titik planar hingga, $\mathcal{R}$ berisi semua persimpangan $X$ dengan garis $\big\}$

Jika, untuk beberapa fungsi $f$ yang linier atau super-linear, keluarga berisi ruang rentang yang tidak menerima $\epsilon$ jaring ukuran $f(1/\epsilon)$ , apa, jika ada, apakah ini menyiratkan tentang Hit Minimum Tetapkan masalah terbatas pada keluarga ruang jangkauan ini?

Jika ruang rentang memiliki -net dengan ukuran , maka celah integral dari hitting set fraksional (atau set penutup) adalah . Lihat karya Philip Long (di sini [Karya etal. Yang lebih lambat dari pekerjaan ini, dan menemukan kembali beberapa barangnya]). Lihat juga slide 13-16 di sini .$\epsilon$$f(1/\epsilon)$$f(1/\epsilon)/(1/\epsilon)$

Singkatnya, memiliki non-linear -nets, menunjukkan bahwa perkiraan masalah hitting-set / set cover yang relevan dalam lebih baik daripada faktor konstan akan sangat menantang.$\epsilon$

Saya tidak yakin itu menyiratkan apa pun. Hasil utama mengalir ke arah lain yaitu dengan konstruksi Bronnimann / Goodrich atau Even / Rawitz / Shahar , jaring berukuran linier menyiratkan pendekatan faktor konstan untuk hitting set (untuk dimensi VC terbatas),