Geodesic
Internet shopping optimization problem
International Journal of Applied Mathematics and Computer Science, Tome 20 (2010) no. 2, pp. 385-390.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: algorithm, computational complexity, combinatorial algorithms, optimization, Internet shopping
Mots-clés : algorytm, złożoność obliczeniowa, algorytm kombinatoryczny, optymalizacja, zakupy internetowe 
@article{IJAMCS_2010_20_2_a12,
     author = {B{\l}a\.zewicz, J. and Kovalyov, M. Y. and Musia{\l}, J. and Urba\'nski, A. P. and Wojciechowski, A.},
     title = {Internet shopping optimization problem},
     journal = {International Journal of Applied Mathematics and Computer Science},
     pages = {385--390},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IJAMCS_2010_20_2_a12/}
}
TY  - JOUR
AU  - Błażewicz, J.
AU  - Kovalyov, M. Y.
AU  - Musiał, J.
AU  - Urbański, A. P.
AU  - Wojciechowski, A.
TI  - Internet shopping optimization problem
JO  - International Journal of Applied Mathematics and Computer Science
PY  - 2010
SP  - 385
EP  - 390
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IJAMCS_2010_20_2_a12/
LA  - en
ID  - IJAMCS_2010_20_2_a12
ER  - 
%0 Journal Article
%A Błażewicz, J.
%A Kovalyov, M. Y.
%A Musiał, J.
%A Urbański, A. P.
%A Wojciechowski, A.
%T Internet shopping optimization problem
%J International Journal of Applied Mathematics and Computer Science
%D 2010
%P 385-390
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IJAMCS_2010_20_2_a12/
%G en
%F IJAMCS_2010_20_2_a12
Błażewicz, J.; Kovalyov, M. Y.; Musiał, J.; Urbański, A. P.; Wojciechowski, A. Internet shopping optimization problem. International Journal of Applied Mathematics and Computer Science, Tome 20 (2010) no. 2, pp. 385-390. http://geodesic.mathdoc.fr/item/IJAMCS_2010_20_2_a12/

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