Given　a　ground　set　U　with　a　non-negative　weight　wi　for　each　i∈U,　a　positive　integer　k　and　a　collection　of　sets　S,　which　is　partitioned　into　a　family　of　disjoint　groups　G,　the　goal　of　the　Maximum　Coverage　problem　with　Group　budget　constraints　(MCG)　is　to　select　k　sets　from　S,　such　that　the　total　weight　of　the　union　of　the　k　sets　is　maximized　and　at　most　one　set　is　selected　from　each　group　G∈G.　We　first　present　an　approximation　algorithm　with　a　factor　[Formula　presented]　and　an　exponential　time　via　randomized　linear　programming　rounding　technique.　Then　we　improve　the　time　complexity　of　the　algorithm　to　O((m+n)3.5L+k3.5q7L)　for　|S|=m,　|U|=n,　and　L　being　the　length　of　the　input,　by　the　key　idea　of　modeling　the　selection　of　groups　as　computing　a　constrained　flow　in　a　corresponding　auxiliary　graph.　The　algorithm　is　later　shown　can　be　extended　to　solve　two　generalizations　of　MCG.　Last　but　not　the　least,　we　present　another　algorithm　with　a　time　complexity　O((m+n)3.5L+kδ10.5L)　and　a　slightly　increased　approximation　ratio　[Formula　presented]　mainly　based　on　the　idea　of　partition,　where　δ≥2　is　a　parameter　tuning　which　can　balance　the　time　complexity　and　the　ratio.　©　2019　Elsevier　B.V.