The Clever Shopper Problem

9 décembre 19

Lundi 9 déembre 2019, 14h, en salle P521

Anthony Labarre (LIGM, Université Paris-Est Marne-la-Vallée)

Abstract :

We investigate a variant of the so-called INTERNET SHOPPING problem introduced

by Blazewicz et al. in 2010, where a customer wants to buy a list of products at the

lowest possible total cost from shops which offer discounts when purchases exceed

a certain threshold. Although the problem is NP-hard, we provide exact algorithms

for several cases, e.g. when each shop sells only two items, and an FPT algorithm

for the number of items, or for the number of shops when all prices are equal. We

complement each result with hardness proofs in order to draw a tight boundary

between tractable and intractable cases. Finally, we give an approximation algorithm

and hardness results for the problem of maximising the sum of discounts.