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