# Greedy algorithm for problem asking for solution of size *at most* $k$

Given an integer $$k$$ and a complete weighted bipartite graph with sides $$A,B$$ in which the weight of the edge $$(i,j)$$ is $$c_{ij} \geq 0$$, we want to find a set $$S$$ of at most $$k$$ edges that maximizes $$\sum_{j \in B} \max_{i \in S} c_{ij}.$$ Describe a greedy algorithm with approximation ratio $$1 - \frac{1}{e}$$.

Must the greedy algorithm select $$k$$ edges? If so, can we say that choosing $$k$$ vertices is an optimal strategy?

• By deleting the original question the answer no longer makes any sense for new readers. Either delete the post or restore the question. – STanja Dec 3 '20 at 20:38
• Do not edit your post to delete its content. This is considered impolite. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to you but also to others, and answerers might be answering on that basis. Deleting or defacing an already-answered question is at odds with that goal. – D.W. Dec 3 '20 at 20:57
• Please credit the source of all copied material, as required by our policy on referencing material written by others: cs.stackexchange.com/help/referencing – D.W. Dec 3 '20 at 20:57

Denote the objective function by $$f(S)$$. It is not hard to check that $$f$$ is monotone, that is, if $$S \subseteq T$$ then $$f(S) \leq f(T)$$. For this reason, there is always an optimal solution with exactly $$k$$ vertices (the optimal solution need not be unique – for example, when all weights are the same, all solutions have the same objective value). Therefore the greedy algorithm might as well just choose $$k$$ vertices.
• Your greedy algorithm should output a feasible solution, that is, a set of at most $k$ vertices. – Yuval Filmus Nov 28 '20 at 15:29
• The objective function $\sum_{j \in B} \max_{i \in S} c_{ij}$ only makes sense if $S$ is a set of vertices. This is since $c_{ij}$ is only defined for vertices $i,j$. – Yuval Filmus Nov 28 '20 at 15:56