Internet shopping optimization problem

B£A ZÿEWICZ, JACEK; Kovalyov, Mikhail; Musiał, Jędrzej; Urbanski, Andrzej; Wojciechowski, Adam

doi:10.2478/v10006-010-0028-0

Abstract

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.

References

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

Internet shopping optimization problem

Abstract

Paradigm

My account