-2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ By deleting the original question the answer no longer makes any sense for new readers. Either delete the post or restore the question. $\endgroup$ – STanja Dec 3 '20 at 20:38
  • $\begingroup$ 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. $\endgroup$ – D.W. Dec 3 '20 at 20:57
  • $\begingroup$ Please credit the source of all copied material, as required by our policy on referencing material written by others: cs.stackexchange.com/help/referencing $\endgroup$ – D.W. Dec 3 '20 at 20:57
0
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ Your greedy algorithm should output a feasible solution, that is, a set of at most $k$ vertices. $\endgroup$ – Yuval Filmus Nov 28 '20 at 15:29
  • $\begingroup$ Are you aware of submodular maximization? $\endgroup$ – Yuval Filmus Nov 28 '20 at 15:30
  • 1
    $\begingroup$ The output is a set of vertices, not edges. $\endgroup$ – Yuval Filmus Nov 28 '20 at 15:48
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Nov 28 '20 at 15:56
  • 1
    $\begingroup$ This is an instance of submodular maximization. $\endgroup$ – Yuval Filmus Nov 28 '20 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.