NDLI: An Efficient Algorithm for Strategy-Proof Service Composition

Content Provider	IEEE Xplore Digital Library
Author	Tanaka, M. Murakami, Y.
Copyright Year	2013
Description	Author affiliation: Nat. Inst. of Inf. & Commun. Technol. (NICT), Kyoto, Japan (Tanaka, M.; Murakami, Y.)
Abstract	One of the most typical models of service market is a reverse auction, where service providers offer their services at a certain price and a user selects a combination of the services. In the first price auction, however, a service which is cheaper and has better quality is not necessarily selected. This causes unstable outcomes which are undesirable both for a user and service providers. A possible solution to this is the VCG (Vickrey-Clarke-Groves) mechanism, where the dominant strategy for a service provider is to report true cost of his service. In spite of this desirable property, implementing the VCG mechanism for service composition suffers from its computational cost. Calculation of payments to service providers based on the VCG mechanism requires iterative service selection, although each service selection can be NP- hard. Approximation algorithms cannot be applied because approximate solutions do not assure the desirable property of the VCG mechanism. Thus, we propose a dynamic programming (DP) based algorithm for service selection and VCG payment calculation. The proposed algorithm solves service selection in quasi-polynomial time and gives an exact solution. Moreover, we extend the algorithm to reuse matrix which is built during DP. This largely improves the performance of VCG payment calculation. Our experiment shows that the proposed algorithm can solve practical scale service composition.
Starting Page	105
Ending Page	112
File Size	289486
Page Count	8
File Format	PDF
e-ISBN	9780769550268
DOI	10.1109/SCC.2013.100
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-06-28
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Clustering algorithms Concrete Abstracts Heuristic algorithms Aggregates Approximation algorithms Dynamic programming VCG mechanism service selection dynamic programming
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An Adaptive Heuristic Approach to Service Selection Problems in Dynamic Distributed Systems

Learning Efficient Compositions for QoS-Aware Service Provisioning

Reliable Web Services Selection Using a Heuristic Algorithm

An Efficient Search Strategy for Service Provider Selection in Complex Social Networks

Efficient Heuristic Approach with Improved Time Complexity for Qos-Aware Service Composition

An Adaptive Quality Level Selection Method for Efficient QoS-Aware Service Composition

A Dynamic Clustering-Based Algorithm for Wireless Sensor Networks

Reachability analysis of dynamic programming based controlled systems: An extended algorithm

LASA-HEU: Heuristic Approach for Service Selection in Composite Web Services

An Efficient Algorithm for Strategy-Proof Service Composition

Similar Documents

An Adaptive Heuristic Approach to Service Selection Problems in Dynamic Distributed Systems

Learning Efficient Compositions for QoS-Aware Service Provisioning

Reliable Web Services Selection Using a Heuristic Algorithm

An Efficient Search Strategy for Service Provider Selection in Complex Social Networks

Efficient Heuristic Approach with Improved Time Complexity for Qos-Aware Service Composition

An Adaptive Quality Level Selection Method for Efficient QoS-Aware Service Composition

A Dynamic Clustering-Based Algorithm for Wireless Sensor Networks

Reachability analysis of dynamic programming based controlled systems: An extended algorithm

LASA-HEU: Heuristic Approach for Service Selection in Composite Web Services

An Efficient Algorithm for Strategy-Proof Service Composition