<p>For instance has min max spanning/steiner/prize-collecting tree been studied. i.e.  each edge <span class="math-container">$e$</span> has costs <span class="math-container">$c_{v,e}$</span> of each resource <span class="math-container">$i$</span>.
And we wish to find a spanning tree minimizing the maximum amount of any resource used.
Is this NP hard for fixed number of resources and if so I'm looking for approximation algorithms.</p>

CC BY-SA 4.0
2024-04-14T20:19:43.890Z
The problem is NP-complete even for the special case of finding a spanning tree, with just two resources . See e.g. https://doi.org/10.1007/BF02032304 .
Neal Young
CC BY-SA 4.0
2024-04-14T21:43:43.707Z
@NealYoung  My previous post aimed at multiobjective single cost, now I'm inquiring what if the cost contains multiple resources.
Hao S
CC BY-SA 4.0
2024-04-14T21:57:30.173Z
This paper on robust s-t path is relevant and has pointers to some other problems. https://arxiv.org/abs/2305.16439
Chandra Chekuri
<graph-theory><co.combinatorics><optimization><tree>
What work on min max connectivity problems has there been?
Hao S
# What work on min max connectivity problems has there been?

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

For instance has min max spanning/steiner/prize-collecting tree been studied. i.e. each edge $e$ has costs $c\_{v,e}$ of each resource $i$.
And we wish to find a spanning tree minimizing the maximum amount of any resource used.
Is this NP hard for fixed number of resources and if so I'm looking for approximation algorithms.

**Tags:** graph-theory, co.combinatorics, optimization, tree
> **Comments:**
> **username_1**: The problem is NP-complete even for the special case of finding a spanning tree, with just two resources . See e.g. https://doi.org/10.1007/BF02032304 .  
> **username_0**: @NealYoung  My previous post aimed at multiobjective single cost, now I'm inquiring what if the cost contains multiple resources.  
> **username_2**: This paper on robust s-t path is relevant and has pointers to some other problems. https://arxiv.org/abs/2305.16439  

---

## 0 answers

