Approximation algorithms and relaxations for a service provision problem on a telecommunication network

Modern distributed networks have widely extended the possibilities of the telecommunication industry for offering a wide variety of services directly or indirectly by facilitating them for other service providers. These new opportunities require a shift of focus in research from traditional transportation of information to processing of information. This paper considers the problem of allocating applications for services (in the sense of software) to the computing nodes of the distributed network, so as to provide as much of the demand for the services as possible. The service provision problem is formulated as an integer linear programming model and is shown to be NP-hard. We exploit similarities to the well-known (multiple) knapsack problem in devising approximation algorithms and analysing their performance from a worst case point of view. Among others a fully polynomial time approximation scheme is presented for the case with one computing node. The other main results of the paper concern the derivation of lower bounds on the optimal solution via LP and Lagrangian relaxations. Keywords: distributed networks, telecommunication, service provision, internet, approximation algorithms, worst-case analysis, LP relaxation, Lagrangian relaxation, knapsack problem.