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.

  • 2
    $\begingroup$ The problem is NP-complete even for the special case of finding a spanning tree, with just two resources . See e.g. doi.org/10.1007/BF02032304 . $\endgroup$
    – Neal Young
    Apr 14 at 20:19
  • $\begingroup$ @NealYoung My previous post aimed at multiobjective single cost, now I'm inquiring what if the cost contains multiple resources. $\endgroup$
    – Hao S
    Apr 14 at 21:43
  • 2
    $\begingroup$ This paper on robust s-t path is relevant and has pointers to some other problems. arxiv.org/abs/2305.16439 $\endgroup$ Apr 14 at 21:57


Your Answer

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