In　this　paper,　we　study　the　maximum　coverage　problem　with　group　budget　constraints　(MCG)　that　generalizes　the　maximum　coverage　problem.　Given　a　ground　set　U　in　which　i∈　U　has　a　non-negative　weight　wi,　a　positive　integer　k　and　a　collection　of　sets　S,　the　maximum　coverage　problem　is　to　pick　k　sets　of　S　to　maximize　the　total　weight　of　their　union.　In　MCG,　S　is　partitioned　into　groups　G1,⋯,Gq,　and　the　goal　is　to　pick　k　sets　from　S　to　maximize　the　total　weight　of　their　union,　with　at　most　nl∈ℤ0　+　sets　being　picked　from　group　Gl.　For　MCG　with　nl=　1,　∀　l,　we　first　present　a　factor　1-1/e　approximation　algorithm　which　runs　in　exponential　time.　Then　we　improve　the　runtime　of　the　algorithm　to　O((m+　n+　q)3.5L+　k3.5q7L)　where　|S|　=　m,　|U|　=　n,　q　is　the　number　of　groups,　and　L　is　the　length　of　the　input.　The　key　idea　of　the　improvement　is　to　model　selecting　groups　for　MCG　as　computing　a　constrained　flow　in　a　corresponding　auxiliary　graph.　It　is　also　shown　that　the　algorithm　can　be　extended　to　solve　MCG　with　general　nl.　Later,　based　on　the　main　idea　of　partition　we　further　improve　the　runtime　of　the　algorithm　to　O((m+　n+　q)3.5L+　kδ10.5L),　while　compromise　the　approximation　ratio　to　1-e1δ-1,　where　δ≥　2　is　any　fixed　integer.　Consequently,　we　can　balance　approximation　ratio　and　runtime　of　the　algorithm　by　setting　the　value　of　δ.　This　improves　the　previous　best　ratio　of　0.5　on　MCG　due　to　Chekuri　and　Kumar　[4].　©　Springer　International　Publishing　AG　2017.