%0 Journal Article
%T Pricing Mechanism of TSP Solving Service in Cloud Computing<br>云计算中TSP问题求解服务的定价机制
%A 曾栩鸿
%A 曾国荪
%J 计算机科学
%D 2011
%I 
%X The traveling salesman problem(TSP) is a typical path optimization problem which has similar problems and applications in urban transportation planning, logistic transport and communication network settings. However, TSP is a NP hard problem When problem scale is very large, large scale parallel computing environment such as cloud computing platform is needed. In this paper, we illustrated cloud service pricing mechanism with TSP. Uenerally, pricing mechanism should be fair, flexible, dynamic and flexible. To be fair and reasonable, there arc two main aspects to be considered when pricing a service. One is the difficulty of solving the problem including time complexity, space complexity and quantity of data the application input and output. The other is the quality of service including precision of the result, response time and whether the service is provided in peak time or not which can be served for Service Level Agreement between service provider and customer. Next, we proposed principles of pricing the service and pricing formula. Finally,a case study aiming at pricing solving TSP service was given, which has a reference value for pricing NP hard problem in cloud computing environment.
%K Cloud computing
%K TSP problem
%K Solving service
%K Pricing mechanism
%K SLA<br>云计算，TSP问题，求解服务，定价机制，服务等级协定
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=17DDCED190714E7931C96776399D0880&yid=9377ED8094509821&vid=16D8618C6164A3ED&iid=59906B3B2830C2C5&sid=5D9D6A8FC2C66FD8&eid=FCD27DC5E1F2EEE7&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=0