In the provisioning of Web services, service providers cannot accept all requests for their services early; to do so would exhaust their capacities early, missing the chance to accept more profitable requests later. Conversely, service providers cannot be too conservative and reject all requests for their services. The focus of this paper is on the problem of the algorithmic complexity of request selection and pricing for Web service providers, when user requests arrive over time. Web services are considered to be pay-per-view functionalities that are invoked over the Internet.
A theoretical analysis is done to determine which variants of this problem are algorithmically nondeterministic polynomial time (NP) complete. From a practical point of view, many of the assumptions made in this paper do not hold: first, the service level agreements, billing bundles, and the service provider’s control over provisioning delays restrict the complexity. On the other hand, peering, needed transmission capacity adaptation, and content updates all add to the complexity.
The paper considers uniform and dynamic pricing. For uniform pricing, it is stated that there exists no online algorithm with a constant competitive ratio. For dynamic pricing, in its general form, it is stated that there does not exist any known online algorithm with a constant competitive ratio. For the complexity determination, the online version of dynamic pricing is compared with the dynamic (online) knapsack problem, where items arrive according to a Poisson process in time. This assumption is quite surprising, as it is almost absent from Internet traffic. A third analysis deals with a randomized, threat-based, online algorithm that tries to maintain a certain level of competitiveness in comparison to the maximum possible profit.
The paper offers an attempt to determine the algorithmic complexity of some theoretical instance-based pricing schemes, under some assumptions not found in real Web services (whether broadband or wireless). The consequences of the result are not spelled out.
