A note on the subadditive network design problem

0.00 Avg rating—0 Votes

Article ID:	iaor20102994
Volume:	37
Issue:	5
Start Page Number:	339
End Page Number:	344
Publication Date:	Sep 2009
Journal:	Operations Research Letters
Authors:	Bateni M, Hajiaghayi M

Abstract:

We study approximation algorithms for generalized network design where the cost of an edge depends on the identities of the demands using it (as a monotone subadditive function). Our main result is that even a very special case of this problem cannot be approximated to within a factor $2 {log}^{1 - ε ∣ D ∣}$ equ1 if D is the set of demands.

Reviews

Required fields are marked *. Your email address will not be published.