document: On optimal service selection 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 .
doc_bio_tags: O O O O O O O O O O O B I O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O