Given　a　ground　set　U　with　a　non　-negative　weight　wi　for　each　i　E　U,　a　positive　integer　k　and　a　collection　of　sets　8,　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　Q　E　We　first　present　an　approximation　algorithm　with　a　factor　1　a　and　an　exponential　time　via　randomized　linear　programming　rounding　technique.　Then　we　improve　the　time　complexity　of　the　algorithm　to　0((m　+　n)3.5L　+　k3.5q7L)　for　ISM　=　m,　IU　I　=　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　0　((m　+n)3.5L　+1(81.5L)　and　a　slightly　increased　approximation　ratio　1　ei-1　mainly　based　on　the　idea　of　partition,　where　iS　＞　2　is　a　parameter　tuning　which　can　balance　the　time　complexity　and　the　ratio.　(C)　2019　Elsevier　B.V.　All　rights　reserved.