A high number of Internet shops makes it difficult for a customer to review manually all the available offers and select optimal outlets for shopping. A partial solution to the problem is brought by price comparators which produce price rankings from collected offers. However, their possibilities are limited to a comparison of offers for a single product requested by the customer. The issue we investigate in this paper is a multiple-item multiple-shop optimization problem, in which total expenses of a customer to buy a given set of items should be minimized over all available offers. In this paper, the Internet Shopping Optimization Problem (ISOP) is defined in a formal way and a proof of its strong NP-hardness is provided. We also describe polynomial time algorithms for special cases of the problem.
@article{bwmeta1.element.bwnjournal-article-amcv20i2p385bwm,
author = {Jacek B\l a\.zewicz and Mikhail Y. Kovalyov and J\k edrzej Musia\l\ and Andrzej P. Urba\'nski and Adam Wojciechowski},
title = {Internet shopping optimization problem},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {20},
year = {2010},
pages = {385-390},
zbl = {1230.90207},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv20i2p385bwm}
}
Jacek Błażewicz; Mikhail Y. Kovalyov; Jędrzej Musiał; Andrzej P. Urbański; Adam Wojciechowski. Internet shopping optimization problem. International Journal of Applied Mathematics and Computer Science, Tome 20 (2010) pp. 385-390. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv20i2p385bwm/
[000] Crescenzi, P. and Kann, V. (2008). A compendium of NP optimization problems, http://www.nada.kth.se/~viggo/wwwcompendium/.
[001] Garey, M. and Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, NY. | Zbl 0411.68039
[002] Gemius, S. (2008). E-commerce in Poland, http://gemius.pl/pl/raporty/2008-06/03.
[003] Horrigan, J. (2008), On-line Shopping, Pew Research Center, http://www.pewinternet.org/~/media//Files/Reports/2008/PIP_Onlinepping.pdf.pdf.
[004] Klein, S. (2000). The emergence of auctions on the world wide web, in M. Shaw, R. Blanning, T. Strader and A. Whinston (Eds.), Handbook on Electronic Commerce, Springer-Verlag, Berlin/Heidelberg, pp. 627-645.
[005] Langdon, C., Roghe, F. and Shaw, M. (2000). Consumer mass market on-line payment solutions, in M. Shaw, R. Blanning, T. Strader and A. Whinston (Eds.), Handbook on Electronic Commerce, Springer-Verlag, Berlin/Heidelberg, pp. 273-288.
[006] Lee, H. (1998). Do electronic marketplaces lower the prices of goods?, Communications of the ACM 41(1): 73-80.
[007] Lesk, M. (1997). Practical Digital Libraries: Books, Bytes and Bucks, Morgan Kaufmann Publishers, San Francisco, CA.
[008] Liang, T. and Huang, J. (1998). An empirical study on consumer acceptance of products in electronic markets: A transactional cost model, Decision Support Systems 21(1): 29-43.
[009] Musiał, J. and Wojciechowski, A. (2009). A customer assistance system: Optimizing basket cost, Foundations of Computing and Decision Sciences 34(1): 59-69.
[010] Raz, R. and Safra, S. (1997). A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP, 29th Annual ACM Symposium on Theory of Computing, El Paso, TX, USA, pp. 475-484. | Zbl 0963.68175
[011] Satzger, B., Endres, M. and Kielssing, W. (2006). A preferencebased recommender system, in K. Bauknecht, B. Pröll and H. Werthner (Eds.), E-Commerce and Web Technologies, Lecture Notes in Computer Science, Vol. 4082, Springer-Verlag, Berlin/Heidelberg, pp. 31-40.
[012] Tolle, K. and Chen, H. (2000). Intelligent software agents for electronic commerce, in M. Shaw, R. Blanning, T. Strader and A. Whinston (Eds.), Handbook on Electronic Commerce, Springer-Verlag, Berlin/Heidelberg, pp. 265-382.
[013] Vulkan, N. (2003). The Economics of E-Commerce. A Strategic Guide to Understanding and Designing the On-line Marketplace, Princeton University Press, Princeton, NJ.