Internet shopping; Computational Complexity; Optimization
Abstract :
[en] A customer would like to buy a given set of products in a given set of Internet shops. For each Internet shop, standard prices for the products are known as well as a concave increasing discounting function of total standard and delivery price. The problem is to buy all the required products at the minimum total discounted price. Computational complexity of various special cases is established. Properties of optimal solutions are proved and polynomial time and exponential time solution algorithms based on these properties are designed. Two heuristic algorithms are suggested and computationally tested.
Disciplines :
Computer science
Author, co-author :
Blazewicz, Jacek; Institut Polytechnique de Poznan
BOUVRY, Pascal ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Kovalyov, Mikhael; National Academy of Sciences of Belarus
MUSIAL, Jedrzej ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
