article · 2011
Rounding
Instructor Mohammad, T. Hajiaghayi, Scribe Rajesh Chitnis
Cited by 0Abstract and details only
Abstract
In this section we will see an f-approximation algorithm for the Set Cover problem where f is the maximum number of times any element of the universe appears in the sets. Set Cover Input: A universe U = {u1, u2,..., um}, a collection S = {S1, S2,..., Sn} of subsets of U and a cost function c: S → R + ∪ {0} Goal: To find a minimum cost S ′ ⊆ S such that U = ⋃ S∈S ′ S Consider the following integer program which solves the Set Cover problem. subject to n∑ min c(Sj)xj j=1 ∀ i ∈ [m], xj ≥ 1 ui∈Sj ∀ j ∈ [n], xj ∈ {0, 1}
Cite this paper
Mohammad, I., Hajiaghayi, T., & Chitnis, S. R. (2011). Rounding.
Mohammad, Instructor, et al. “Rounding.” 2011.
Mohammad, Instructor, T. Hajiaghayi, and Scribe Rajesh Chitnis. 2011. “Rounding.”
Mohammad, I., Hajiaghayi, T. and Chitnis, S.R. (2011) ‘Rounding’.
@article{mohammad2011rounding,
title = {{Rounding}},
author = {Mohammad, Instructor and Hajiaghayi, T. and Chitnis, Scribe Rajesh},
year = {2011}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.