The Clever Shopper Problem
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F20%3A00337774" target="_blank" >RIV/68407700:21240/20:00337774 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1007/s00224-019-09917-z" target="_blank" >https://doi.org/10.1007/s00224-019-09917-z</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00224-019-09917-z" target="_blank" >10.1007/s00224-019-09917-z</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
The Clever Shopper Problem
Popis výsledku v původním jazyce
We investigate a variant of the so-called Internet Shopping problem introduced by Blazewicz et al. (Appl. Math. Comput. Sci. 20, 385–390, 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.
Název v anglickém jazyce
The Clever Shopper Problem
Popis výsledku anglicky
We investigate a variant of the so-called Internet Shopping problem introduced by Blazewicz et al. (Appl. Math. Comput. Sci. 20, 385–390, 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.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2020
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Theory of Computing Systems
ISSN
1432-4350
e-ISSN
1433-0490
Svazek periodika
64
Číslo periodika v rámci svazku
1
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
18
Strana od-do
17-34
Kód UT WoS článku
000511677200003
EID výsledku v databázi Scopus
2-s2.0-85064730286