Nonmetric Multicommodity Facility Location and K-Median Problem with Service Installation Costs

We studied the multicommodity facility location and a variant K-median problem as well. For the first problem, the pure combinatory strategies are presented. We give a subtle analysis for the nonmetric uncapacitated case and an approximation algorithm for the capacitated case. For the first time, the local search technique is exploited in the variant K-median problem with service installation and an 3+ epsiv-approximation ratio (epsi : 0 < epsi les 1) is achieved. Our results of the second problem is under the assumption that there is an ordering on the facilities. If i´ comes after i in this ordering, then for any commodity (also named service type) the initial service costs in i is not higher than the costs in i´.