Suppose we have a graph $G$ a root $r$ and each node $v$ has some amount of $c_{v,i}$ of each resource $i$. I connect a set of nodes to the root that maximizes the minimum amount of any resource using at most a given number of edges.

Has this problem been studied?

  • $\begingroup$ @NealYoung Isn't just Steiner tree NP-complete? $\endgroup$
    – Hao S
    Apr 14 at 1:41
  • $\begingroup$ @NealYoung approximation algorithms mostly $\endgroup$
    – Hao S
    Apr 14 at 19:04
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – Neal Young
    Apr 14 at 19:59
  • $\begingroup$ @NealYoung Yes I mean find a connected subgraph containing the root with $k$ edges maximizing the minimum, over all resources $i$, of the sum of $c_{vi}$. I don't assume the graph is a tree but in my case I'm assuming edges are positive so I would not ever select noncut edges. $\endgroup$
    – Hao S
    Apr 14 at 20:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.