Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence
We consider the money distribution problem for a micro-payment scheme using a distributed server system; in particular, for an automatic charging scheme named PayPerClick that allows Internet users to view Web pages for which access charges are levied without tedious payment procedures. A major bottleneck in the scheme is the network traffic caused by the distribution of electronic money to many different servers. We propose a simple online algorithm for distributing electronic money to servers so that the network traffic is minimized. The algorithm achieves the optimal online competitive ratio. We also consider a weighted version, for which we give an asymptotically optimal online algorithm within a constant factor.
Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
A. Grill, B.S. Meyerson, et al.
Proceedings of SPIE 1989
Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences