<p>Suppose we have a graph <span class="math-container">$G$</span> a root <span class="math-container">$r$</span> and each node <span class="math-container">$v$</span> has some amount of <span class="math-container">$c_{v,i}$</span> of each resource <span class="math-container">$i$</span>.
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.</p>
<p>Has this problem been studied?</p>

CC BY-SA 4.0
2024-04-14T01:41:38.523Z
@NealYoung Isn't just Steiner tree NP-complete?
Hao S
CC BY-SA 4.0
2024-04-14T19:04:54.453Z
@NealYoung  approximation algorithms mostly
Hao S
CC BY-SA 4.0
2024-04-14T19:59:39.787Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/152616/discussion-between-neal-young-and-hao-s).
Neal Young
CC BY-SA 4.0
2024-04-14T20:12:29.097Z
@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.
Hao S
<graph-theory><co.combinatorics><optimization><tree>
Has multiobjective prize collecting steiner tree or TSP been studied?
Hao S
# Has multiobjective prize collecting steiner tree or TSP been studied?

(Asked by: username_0 on 2024-04-13)

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?

**Tags:** graph-theory, co.combinatorics, optimization, tree
> **Comments:**
> **username_0**: @NealYoung Isn't just Steiner tree NP-complete?  
> **username_0**: @NealYoung  approximation algorithms mostly  
> **username_1**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/152616/discussion-between-neal-young-and-hao-s).  
> **username_0**: @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.  

---

## 0 answers

