Abstract
While many works have been devoted to service matchmaking and modeling nonfunctional properties, the problem of matching service requests to offers in an optimal way has not yet been extensively studied. In this paper we formalize three kinds of optimal service selection problems, based on different criteria. Then we study their complexity and implement solutions. We prove that one-time costs make the optimal selection problem computationally hard; in the absence of these costs the problem can be solved in polynomial time. We designed and implemented both exact and heuristic (suboptimal) algorithms for the hard case, and carried out a preliminary experimental evaluation with interesting results.

URL:
http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2005-73

BibTeX:

@inproceedings{REWERSE-RP-2005-73,
	author = {Piero A. Bonatti and Paola Festa},
	title = {On optimal service selection},
	booktitle = {Proceedings of 14th Intl. World Wide Web Conference, Chiba, Japan (10th--14th May 2005)},
	year = {2005},
	organization = {W3C},
	pages = {530--538},
	url = {http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2005-73}
}