Approximation algorithms for multi-parameter graph optimization problems Original Research Article

Given a graph with k⩾2 different nonnegative weights associated with each edge e and a cost function c : Rk→R+, consider the problem of finding a minimum-cost edge subset possessing a certain property P. We prove that this problem is weakly NP-hard for a wide class of properties P and costs c, including paths, spanning trees, cuts, joins, etc. We suggest a simple approximation algorithm for this problem and find its performance guarantee.