Internet shopping optimization problem

• Autorzy: Błażewicz J. , Kovalyov M. Y. , Musiał J. , Urbański A. P. , Wojciechowski A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

algorithm; computational complexity; combinatorial algorithms; optimization; Internet shopping

PL

algorytm; złożoność obliczeniowa; algorytm kombinatoryczny; optymalizacja; zakupy internetowe

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2010
• Tom: Vol. 20, no 2
• Strony: 385--390
• Opis fizyczny: Bibliogr. 14 poz., tab.

Twórcy

autor

Błażewicz J.

• Institute of Computing Science, Poznań University of Technology, ul. Piotrowo 2, 60-965 Poznań, Poland; Institute of Bioorganic Chemistry Polish Academy of Sciences, Z. Noskowskiego 12/14, 61-704 Poznan, Poland

autor

Kovalyov M. Y.

• United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, Belarus

autor

Musiał J.

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznań, Poland

autor

Urbański A. P.

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznań, Poland

autor

Wojciechowski A.

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznań, Poland

• Institute of Computing Science Poznań University of Technology, ul. Piotrowo 2, 60-965 Poznań, Poland,

Bibliografia

• [1] Crescenzi, P. and Kann, V. (2008). A compendium of NP optimization problems, http://www.nada.kth.se/~viggo/wwwcompendium/.
• [2] Garey, M. and Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, NY.
• [3] Gemius, S. (2008). E-commerce in Poland, http: //gemius.pl/pl/raporty/2008-06/03.
• [4] Horrigan, J. (2008), On-line Shopping, Pew Research Center, http://www.pewinternet.org/~/media//Files/Reports/2008/PIP_Onlinepping.pdf.pdf.
• [5] 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.
• [6] 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.
• [7] Lee, H. (1998). Do electronic marketplaces lower the prices of goods?, Communications of the ACM 41(1): 73-80.
• [8] Lesk, M. (1997). Practical Digital Libraries: Books, Bytes and Bucks, Morgan Kaufmann Publishers, San Francisco, CA.
• [9] 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.
• [10] Musiał, J. and Wojciechowski, A. (2009). A customer assistance system: Optimizing basket cost, Foundations of Computing and Decision Sciences 34(1): 59-69.
• [11] 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.
• [12] Satzger, B. , Endres,M. and Kielssing,W. (2006). A preference based 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.
• [13] 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.
• [14] Vulkan, N. (2003). The Economics of E-Commerce. A Strategic Guide to Understanding and Designing the On-line Marketplace, Princeton University Press, Princeton, NJ.