Approximation algorithms for multi-parameter graph optimization problems (Q1602708)

A multi-parameter graph optimization problem (MPGO) is defined by a graph \(G=(V,E)\), a \(k\)-dimensional non-negative weight \(w(e)\) for each edge \(e\) in \(E\), and a cost function assigning to each subset \(S \subseteq E\) of the edge set a cost \(c(S):=c(w(S)):=c(\sum w(e))\). The goal of MPGO is to find a minimum cost subset of \(E\) satisfying a given property \(P\). In the case, where \(c(S)=\max_{1\leq i\leq k}w_i(S)\), MPGO is very similar to constrained graph optimization problems which have attracted a lot of attention due to their large potential in applications. The authors prove that MPGO is weakly NP-hard for a large class of properties \(P\) and cost functions \(c\), including paths, spanning trees, cuts, joins, etc. The authors develop a simple approximation algorithm for the general problem and prove performance guarantee results.