Internet shopping optimization problem

• Autorzy: Jacek Błażewicz , Mikhail Y. Kovalyov , Jędrzej Musiał , Andrzej P. Urbański , Adam Wojciechowski
• 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

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

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2010
• Tom: 20
• Numer: 2
• Strony: 385-390

Daty

wydano

2010

otrzymano

2009-06-19

poprawiono

2009-10-24

Twórcy

autor

Jacek Błażewicz

• 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 Poznań, Poland

autor

Mikhail Y. Kovalyov

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

autor

Jędrzej Musiał

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

autor

Andrzej P. Urbański

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

autor

Adam Wojciechowski

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

Bibliografia

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

Identyfikatory

DOI

10.2478/v10006-010-0028-0