title: Algorithms and Time Complexity of the Request-Service Problem.
abstract: Given a number of users each of which provides a set of services with a cost for each service and has a set of requests to be satisfied, the goal of the request-service problem is to find a feasible solution that satisfies all requests of each user with minimum cost. In addition, a feasible solution must satisfy an additional constraint. Specifically, if user A provides a service to user B, B should provide a service back to A either directly or indirectly through other users. In this paper, we studied the complexity of this problem. We show that there exists a polynomial time algorithm that can compute a feasible solution with minimum cost if such a solution exists. However, if a feasible solution does not exist, the problem of maximizing the number of satisfied users (i.e., all requests of the users are satisfied) is NP-hard.
authors.affiliation: Department of Systems and Computer Science, Howard University, Washington, DC 20059, USA.
authors.forename: Chunmei
authors.initials: C
authors.lastname: Liu
authors.forename: Legand
authors.initials: L
authors.lastname: Burge
authors.forename: Ajoni
authors.initials: A
authors.lastname: Blake