Internet shopping optimization problem

Jacek Błażewicz; Mikhail Y. Kovalyov; Jędrzej Musiał; Andrzej P. Urbański; Adam Wojciechowski

International Journal of Applied Mathematics and Computer Science (2010)

  • Volume: 20, Issue: 2, page 385-390
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Jacek Błażewicz, et al. "Internet shopping optimization problem." International Journal of Applied Mathematics and Computer Science 20.2 (2010): 385-390. <http://eudml.org/doc/207994>.

@article{JacekBłażewicz2010,
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.},
author = {Jacek Błażewicz, Mikhail Y. Kovalyov, Jędrzej Musiał, Andrzej P. Urbański, Adam Wojciechowski},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {algorithms; computational complexity; combinatorial algorithms; optimization; Internet shopping; internet shopping},
language = {eng},
number = {2},
pages = {385-390},
title = {Internet shopping optimization problem},
url = {http://eudml.org/doc/207994},
volume = {20},
year = {2010},
}

TY - JOUR
AU - Jacek Błażewicz
AU - Mikhail Y. Kovalyov
AU - Jędrzej Musiał
AU - Andrzej P. Urbański
AU - Adam Wojciechowski
TI - Internet shopping optimization problem
JO - International Journal of Applied Mathematics and Computer Science
PY - 2010
VL - 20
IS - 2
SP - 385
EP - 390
AB - 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.
LA - eng
KW - algorithms; computational complexity; combinatorial algorithms; optimization; Internet shopping; internet shopping
UR - http://eudml.org/doc/207994
ER -

References

top
  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. Zbl0411.68039
  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. Zbl0963.68175
  12. 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. 
  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. 

NotesEmbed ?

top

You must be logged in to post comments.