کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
5777339 1413658 2018 7 صفحه PDF ندارد دانلود کنید
عنوان انگلیسی مقاله
Approximating set multi-covers
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Approximating set multi-covers
چکیده انگلیسی

Johnson and Lovász and Stein proved independently that any hypergraph satisfies τ≤(1+lnΔ)τ∗, where τ is the transversal number, τ∗ is its fractional version, and Δ denotes the maximum degree. We prove τf≤3.153τ∗max{lnΔ,f} for the f-fold transversal number τf. Similarly to Johnson, Lovász and Stein, we also show that this bound can be achieved non-probabilistically, using a greedy algorithm.As a combinatorial application, we prove an estimate on how fast τf∕f converges to τ∗. As a geometric application, we obtain an upper bound on the minimal density of an f-fold covering of the d-dimensional Euclidean space by translates of any convex body.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 67, January 2018, Pages 174-180
نویسندگان
, ,