Последствия нижних оценок для сетей в приближении

Многие здесь, вероятно, знают о недавних суперлинейных нижних оценках Алона для сетей в естественной геометрической обстановке [PDF] . Я хотел бы знать, что, во всяком случае, такая нижняя граница подразумевает в отношении аппроксимируемости связанных задач Set Cover / Hitting Set. $\epsilon$

Чтобы быть более конкретным, рассмотрим семейство пространств диапазонов, например, семейство:

$\big\{(X,\mathcal{R})$ : - конечное плоское точечное множество, содержит все пересечения с прямымиR X $X$$\mathcal{R}$$X$$\big\}$

Если для некоторой функции которая является линейной или суперлинейной, семейство содержит пространство диапазонов, которое не допускает -net размера , что, во всяком случае, подразумевает минимальное попадание Установить проблему, ограниченную этим семейством пространств диапазонов?ϵ f ( 1 $f$$\epsilon$$f(1/\epsilon)$

Если пространство диапазона имеет размер -net размера , то разрыв интегральности набора дробных ударов (или покрытия набора) равен . См. Работу Филипа Лонга ( здесь [Even etal. Работа позже, чем эта работа, и заново открыть некоторые из его вещей]). Смотрите также слайды 13-16 здесь .f ( 1 / ϵ ) f ( 1 $\epsilon$$f(1/\epsilon)$$f(1/\epsilon)/(1/\epsilon)$

Короче говоря, наличие нелинейных -nets указывает на то, что аппроксимация соответствующей проблемы покрытия наборов / наборов в пределах лучшего, чем постоянный коэффициент будет очень сложной задачей.$\epsilon$

Я не уверен, что это подразумевает что-либо. Основные результаты протекают в другом направлении, то есть с помощью конструкций Броннимана / Гудрича или Эвена / Равица / Шахара , сеть линейного размера подразумевает приближение постоянного множителя для множества ударов (для ограниченной размерности ВК),