<abstract xml:lang="en" xmlns="http://www.w3.org/1999/xhtml"><p>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.</p></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.

Internet shopping optimization problem

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

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

Institute of Bioorganic Chemistry, Polish Academy of Sciences, Z. Noskowskiego 12/14, 61-704 Poznań, Poland

International Journal of Applied Mathematics and Computer Science

{"article-title":"Internet shopping optimization problem"}

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

Internet shopping optimization problem

Data publikacji: 02 lip 2010

Zakres stron: 385 - 390

DOI: https://doi.org/10.2478/v10006-010-0028-0

Słowa kluczowe
algorithms, computational complexity, combinatorial algorithms, optimization, Internet shopping

This content is open access.

Internet shopping optimization problem

Data publikacji: 02 lip 2010

Zakres stron: 385 - 390

DOI: https://doi.org/10.2478/v10006-010-0028-0

Słowa kluczowealgorithms, computational complexity, combinatorial algorithms, optimization, Internet shopping

This content is open access.

Słowa kluczowe
algorithms, computational complexity, combinatorial algorithms, optimization, Internet shopping