Algorithms and time complexity of the request-service problem

作者：Liu Chunmei^*; Burge Legand; Blake Ajoni

来源：Journal of Combinatorial Optimization, 2010, 20(2): 180-193.

DOI：10.1007/s10878-008-9202-9

• Request-service
• Disjoint cycle cover
• MAX2SAT

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.

• 出版日期2010-8