The Clever Shopper Problem
Laurent Bulteau1 , Danny Hermelin2 , Anthony Labarre1 , and Stéphane
Vialette1

arXiv:1802.07944v1 [] 22 Feb 2018

1

2

Université Paris-Est, LIGM (UMR 8049), CNRS, ENPC, ESIEE Paris, UPEM,
F-77454, Marne-la-Vallée, France
{laurent.bulteau,anthony.labarre,stephane.vialette}@u-pem.fr
Department of Industrial Engineering and Management, Ben-Gurion University of
the Negev, Israel
hermelin@bgu.ac.il

Abstract. We investigate a variant of the so-called Internet Shopping problem introduced by Blazewicz et al. (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.

1

Introduction

Blazewicz et al. [3] introduced and described the Internet Shopping problem
as follows: given a set of shops offering products at various prices and the delivery
costs for each set of items bought from each shop, find where to buy each product
from a shopping list at a minimum total cost. The problem is known to be NPhard in the strong sense even when all products are free and all delivery costs
are equal to one, and admits no polynomial (c ln n)-approximation algorithm
(for any 0 < c < 1) unless P = NP.
A more realistic variant takes into account discounts offered by shops in some
cases. These could be offered, for instance, when the shopper’s purchases exceed
a certain amount, or in the case of special promotions where buying several items
together costs less than buying them separately. Blazewicz et al. [4] investigated
such a variant, which features a concave increasing discount function on the
products’ prices. They showed that the problem is NP-complete in the strong
sense even if each product appears in at most three shops and each shop sells
exactly three products, as well as in the case where each product is available
at three different prices and each shop has all products but sells exactly three
of them at the same value. A variant where two separate discount functions
are taken into account (one for the deliveries, the other for the prices) was also
recently introduced and studied by Blazewicz et al. [5].

In this work, we investigate the case where a shopper aims to buy n books
from m shops with free shipping; additionally, each shop offers a discount when
purchases exceed a certain threshold (discounts and thresholds are specific to
each shop). We show that the associated decision problem, which we call the
Clever Shopper problem, is already NP-complete when only two shops are
available, or when all books are available from two shops and each shop sells
exactly three books. We also obtain parameterised hardness results: namely,
that Clever Shopper is W[1]-hard when the parameter is m or the number of
shops in a solution, and that it admits no polynomial-size kernel. On the positive
side, we give a polynomial-time algorithm for the case where every shop sells at
most two books, an XP algorithm for the case where few shops sell books at
small prices, an FPT algorithm with parameter n, and another FPT algorithm
with parameter m.
Let us now formally define Clever Shopper. For n ∈ N, let [n] = {1,
2, . . ., n}. Let B be a set of books to buy, S be a set of shops, E ⊆ B × S
encodes the availability of the books in the shops, and w : E → N encodes
the prices. Choosing a shop in which to buy each book is encoded as a subset
E 0 ⊆ E, such that each book is covered exactly once (i.e., any b ∈ B has degree
1 in E 0 ). A discount ds ∈ R+ is associated to each shop s and offered when
a threshold ts ∈ R+ is reached, which is formally defined using the following
threshold function:
P

ds if
0
(b,s)∈E 0 w(e) ≥ ts ,
δ(s, E , ds , ts ) =
0 otherwise.
We refer to the function D that maps each shop s to the pair (ds , ts ) as the
discount function. The problem we study is formally stated below, and generalises well-studied problems such as bin covering [1] and H-index manipulation [13].
Clever Shopper
Input:
an edge-weighted bipartite graph G = (B ∪ S, E, w); a discount function D; a bound K ∈ N.
0
Question: is there a subset
P E ⊆ E thatPcovers each element of B exactly once
and such that e∈E 0 w(e) − s∈S δ(s, E 0 , ds , ts ) ≤ K?

2

Hardness Results

We prove in this section several hardness results under various restrictions, both
with regards to classical complexity theory and parameterised complexity theory.
We show that Clever Shopper is NP-complete even if there are only two
shops to choose from. For this first hardness result we need book prices to be
encoded in binary (i.e. they can be exponentially high compared to input size).
Proposition 1. Clever Shopper is NP-complete in the weak sense ( i.e., prices are encoded in binary), even when |S| = 2.
2

Proof (reduction from Partition). Recall the well-known NP-complete Partition problem [12]: given a finite set A and a size ω(a) ∈ N forPeach element
0
in
a∈A0 ω(a) =
P A, decide whether there exists a subset A ⊆ A such that
ω(a).
0
a∈A\A
P
Let I = (A, ω) be an instance of Partition, and T = a∈A ω(a). We obtain
an instance I 0 of Clever Shopper as follows: introduce two shops s1 and s2
with (ds1 , ts1 ) = (ds2 , ts2 ) = (1, T /2). Each item a ∈ A is a book that shops s1
and s2 sell for the same price
It is now clear that there exists
P — namely, ω(a).
P
a subset A0 ⊆ A such that a∈A0 ω(a) = a∈A\A0 ω(a) if and only if all books
can be purchased for a total cost of T − 2.
t
u
This NP-hardness result allows arbitrarily high prices (the reduction from
Partition requires prices of the order of 2|B| ). In a more realistic setting, we
might assume a polynomial bound on prices, i.e., they can be encoded in unary.
As we show below, the problem remains hard for a few shops in the sense of W[1]hardness. We complement this result with an XP algorithm in Proposition 7.
Proposition 2. Clever Shopper is W[1]-hard for m = |S| in the strong sense
( i.e., even when prices are encoded in unary).
Proof (reduction from Bin Packing). Recall the well-known Bin Packing
problem: given n items with weights w1 , w2 , . . . , wn and m bins with the same
given capacity W , decide whether each item can be assigned to a bin so that
the total weight of the items in any bin does not exceed W . Bin Packing is
NP-complete
in the strong sense and W[1]-hard for parameter m, even when
Pn
w
=
mW
and all weights are encoded in unary [11].
i=1 i
We build an instance I of Clever Shopper from an instance of Bin Packing with the aforementioned restrictions as follows. Create m identical shops,
each with ts = W and ds = 1. Create n books, where book i is available in
every shop at price wi . The budget is m(W − 1). In other words, any solution
requires to obtain the discount from every shop, which is only possible if purchases amount to a total of exactly W per shop before discount. Therefore, the
solutions to I correspond exactly to the solutions of the original instance of Bin
Packing.
t
u
We can obtain another hardness result under the assumption that all books
are sold at a unit price. Here we cannot bound the total number of shops (we give
an FPT algorithm for parameter m in Proposition 8 in this setting), but only
the number of chosen shops (i.e., shops where at least one book is purchased).
Proposition 3. Clever Shopper with unit prices is W[1]-hard for the parameter “ number of chosen shops”.
Proof (reduction from Perfect Code). Given a graph G = (V, E) and a positive integer k, Perfect Code asks for a size-k subset V 0 ⊆ V such that for
each vertex u ∈ V there is precisely one vertex in N [v] ∩ V 0 (where N [v] is the
closed neighbourhood of v, i.e., v and its adjacent vertices, as opposed to the
3

b2

1

s2

1

1

u2
u1

1

s1

u4
u5

1

1

1
1

b1

1

u3

1

b4

1

1

1

1
s4

s5

1

b5

1
s3 1 b3

Fig. 1. Reducing Perfect Code to Clever Shopper. Left: The input graph with
a size-2 perfect code (bold). Right: The corresponding bipartite graph and a solution
with total cost 5 − 2 = 3 (bold).

open neighbourhood N (v) = N [v]\{v}). This problem is known to be W[1]-hard
for parameter k [7].
Let I = (G = (V, E), k) be an instance of Perfect Code. Write V =
{u1 , u2 , . . . , un }. We obtain an instance I 0 of Clever Shopper as follows. Let
us first define a bipartite graph G0 = (B ∪ S, E 0 ) where B = {bi : ui ∈ V },
S = {si : ui ∈ V } and E 0 = {{bj , si } : uj ∈ NG [ui ]}. All shops sell books
at a unit price. As for the discount function, for each shop si ∈ S we have
D(si ) = (dG (ui ) + 1, 1) (i.e., a unit discount will be applied from dG (ui ) + 1 of
purchase). Figure 1 illustrates the construction.
We claim that there exists a size-k perfect code for G if and only if all books
can be bought for a total cost of n − k.
⇒ Let V 0 ⊆ V be a size-k perfect code in G. For every ui ∈ V , let upc(i) be the
unique vertex in N [v] ∩ V 0 (pc is well-defined since V 0 is a perfect code). Then
buying each book bi ∈ B at shop bpc(i) yields a solution for I 0 , and it is simple
to check that its cost is n − k.
⇐ Suppose that all books can be bought for a total cost of n − k. Since n
books must be bought at unit price and shops only offer a unit discount, k
shops must be chosen in the solution. Let S 0 ⊆ S denote these k shops. Since
D(si ) = (1, dG (ui ) + 1) for each shop si ∈ S, we conclude that for each book
bi ∈ B there is precisely one shop in N [bi ] ∩ S 0 . Then {ui : si ∈ S 0 } is a size-k
perfect code in G.
Note that the number of visited shops corresponds exactly to the total discount received (i.e. to parameter k in the reduction).
t
u
We now prove3 the non-existence of polynomial kernels (under standard complexity assumptions) for Clever Shopper parameterised by the number of
books. To this end, we use the or-composition technique [6]: given a problem
P and a parameterised problem Q, an or-composition is a reduction taking t
3

See Appendix A for the proof.

4

G0

G
p(b1 )=12

12

b1

s1

b2

9

11

2

10
p(b2 )=9

s2

s2

1
1

4

b3

s1

2

b2

7
p(b3 )=4

3

b1

s3

b3

s4

b4

s5

b5

s3

5
2

p(b5 )=7

b5

8

−1

b4

s4

8

p(b4 )=8

7

s5

Fig. 2. Each shop offers a discount of 3 on a purchase of value ≥ 10. Bold edges
indicate how to obtain optimal discounts: buy book b1 from shop s1 , book b2 from
shop s3 , and books b3 and b4 from shop s4 . The remaining books are bought at their
cheapest available price (so here we buy b5 from s5 ). Our clever customer used the
discounts to buy all books for 6 less than if she had bought each book at its lowest
price: 3 for b1 , 1 for b2 , 2 for b3 and b4 together.

instances (I1 , . . . , It ) of P, and building an instance (J, k) of Q, with k bounded
by a polynomial on maxt0 ≤t |It0 | + log t, such that (J, k) is a yes-instance if and
only if there exists t0 ≤ t such that It0 is a yes-instance. If P is NP-hard, then
Q does not admit a polynomial kernel unless NP ⊆ coNP/poly [6].
Proposition 4. Clever Shopper admits no polynomial kernel unless NP ⊆
coNP/poly.

3

Positive Results

We now give exact algorithms for Clever Shopper: a polynomial-time algorithm for the case where every shop sells at most two books, and three parameterised algorithms based respectively on the number of books, the number of
shops, and a bound on the prices.
We give a polynomial time algorithm for the case where each shop sells at
most two books. As we shall see in Section 4, this bound is best possible. Its
running time is dominated by the time required to find a maximum matching in
a graph with |B ∪ S| vertices.
Proposition 5. Clever Shopper is in P if every shop sells at most two books.
Proof. Let I be an instance of Clever Shopper given by an edge-weighted
bipartite graph G = (B ∪ S, E, w) and a pair (ds , ts ) for each s ∈ S, where
5

ds , ts ∈ R+ . Vertices in S (resp. in B) have degree at most 2 (resp. at least
1). Note that vertices in S can be made to have degree exactly 2, by adding
dummy edges with arbitrarily high costs, with no impact on the solution. For
b ∈ B, let p(b) be the cheapest available price for book b (discount excluded),
i.e., p(b) = min{w({b, s}) | s ∈ S}.
Construct a new (non-bipartite) graph G0 = (B ∪ S, E 0 , w0 ), as follows: for
every shop s ∈ S, let {b1 , b2 } = NG (s) (i.e., the two books available at shop s).
– For each i ∈ {1, 2}, if w({bi , s}) ≥ ts , then add an edge {bi , s} to E 0 with
weight w0 ({bi , s}) = ds + p(bi ) − w({bi , s}).
– If w({b1 , s}) + w({b2 , s}) ≥ ts , add an edge {b1 , b2 } to E 0 with weight
w0 ({b1 , b2 }) = ds + p(b1 ) − w({b1 , s}) + p(b2 ) − w({b2 , s}). If edge {b1 , b2 }
existed already, keep only the one with maximum weight.
Note that edges with negative weights may remain: they may be safely ignored,
but we keep them to avoid case distinctions in the rest of this proof. Figure 2
illustrates the construction. Since a maximum weight matching for G0 can be
found in polynomial time [8], it is now enough to prove the following claim: G0
admits a matching of weight at least W if and only
P if instance I of Clever
Shopper admits a solution of total cost at most b∈B p(b) − W . P
⇐ Assume that instance I admits a solution E ∗ ⊆ E of total cost b∈B p(b) −
W . Note that W ≥ 0 (the sum of the minimum prices of the books is an upper
bound of the optimal solution). We build a matching M of G0 as follows. Let
s ∈ S be any discount shop, i.e., a shop whose discount is claimed, and let b1
and b2 be its neighbours. Then at least one of them has to be bought from s to
get the discount.
– If {b1 , s} ∈ E ∗ and {b2 , s} ∈
/ E ∗ , add {b1 , s} to M . The amount spent at this
shop is w({b1 , s}) − ds = p(b1 ) − w0 ({b1 , s}).
– Similarly, if {b2 , s} ∈ E ∗ and {b1 , s} ∈
/ E ∗ , add {b2 , s} to M . The amount
spent at this shop is w({b2 , s}) − ds = p(b2 ) − w0 ({b2 , s}).
– Finally, if {b1 , s} ∈ E ∗ and {b2 , s} ∈ E ∗ , then add {b1 , b2 } to M . The amount
spent at this shop is w({b1 , s})+w({b2 , s})−ds ≥ p(b1 )+p(b2 )−w0 ({b1 , b2 }).
Note that edges added to M are indeed present in E 0 , since in order to obtain the
discount from s, the book prices must satisfy the same condition as for creating
the corresponding edges. Note also that M is a matching, since each book can be
bought from at most one shop. Let B ∗ be the set of books bought from discount
∗
shops. Summing
over all
P
P these 0shops, the total price paid for the books in B is
at least b∈B ∗ p(b) − e∈M w (e).
The books in B \PB ∗ do not yield any discount, so the total price paid
for them is at least
Overall, the cost of the books is at least
b∈B\B ∗ p(b).
P
P
P
0
0
(e),
therefore
p
−
w
b∈B b
e∈M
e∈M w (e) ≥ W .
⇒ Let M be a maximum weight matching of G0 of weight W . For each edge
e ∈ M , let se be the shop for which e was introduced. For an edge e = {b, se } ∈
M , buy book b from shop se . The price is sufficient to reach the threshold for the
discount, so we pay w({b, se }) − de = p(b) − w0 (e). For an edge e = {b1 , b2 } ∈ M ,
6

buy books b1 and b2 together from shop se . We again get the discount, and pay
w({b1 , se }) + w({b2 , se }) − de = p(b1 ) + p(b2 ) − w0 (e). Note that for e 6= f ∈ M ,
se 6= sf , so we never count the same discount twice. For every other book, buy
them at the cheapest possible price
to get any discount.
P p(b), without
P expecting P
The total price paid is at most b∈B p(b) − e∈M w0 (e) = b∈B p(b) − W . t
u
We now give a dynamic programming FPT algorithm with the number of
books as parameter.
Proposition 6. Clever Shopper admits an FPT algorithm for parameter n
with running time O(m3n ).
Proof. Given j ∈ [m] and B 0 ⊆ B, let pj (B 0 ) be the price for buying all books
in B 0 together from shop sj (discount included), and p≤j (B 0 ) be the lowest
price that can be obtained when purchasing all books in B 0 from a subset of
{s1 , . . . , sj }. Our goal is to compute p≤m (B).
For j = 1, clearly p≤1 (B 0 ) = p1 (B 0 ) for every B 0 . For any other j, consider
an optimal way of buying the books in B 0 from shops s1 , . . . , sj . This way the
customer buys some (possibly empty) subset B 00 of books in sj , and the rest,
i.e., B 0 \ B 00 , at the lowest price from shops s1 , . . . , sj−1 . Therefore:

pj (B 0 )
if j = 1,
p≤j (B 0 ) =
minB 00 ⊆B 0 {pj (B 00 ) + p≤j−1 (B 0 \ B 00 )} otherwise.
The values of pj (B 0 ) for all j and B 0 can be computed in O(m2n ) time. Then
the dynamic programming table requires to enumerate, for all j, all subsets B 0
and B 00 such that B 00 ⊆ B 0 ⊆ B. Any such pair B 00 , B 0 can be interpreted as a
vector v ∈ {0, 1, 2}n , where i ∈ B 00 ⇔ vi = 2 and i ∈ B 0 ⇔ vi ≥ 1. Therefore,
filling the dynamic table takes m3n steps, each requiring constant time.
t
u
As usual with dynamic programming, this algorithm yields the optimal price
that can be obtained. One gets the actual solution (i.e., where to buy each book)
with classic backtracing techniques.
The NP-hardness of Clever Shopper for two shops (using large prices,
encoded in binary) and its W[1]-hardness when the parameter is the number of
shops leave a very small opening for positive results: we can only consider small
prices (encoded in unary) for a constant number of shops. The following result
proves the tractability of this case.
Proposition 7. Clever Shopper admits an XP algorithm running in time
O(nmW m ), where W is the sum of all the prices of the instance, n is the number
of books, and m is the number of shops.
Proof. We propose the following dynamic programming algorithm, which generalises the classical pseudo-polynomial algorithm for Partition. Let i ∈ [n] and
ps ∈ [W] for s ∈ S. Define T [i, ps1 , . . . , psm ] as 1 if it is possible to buy books
1 to i by paying exactly ps (discount excluded) in shop s; and 0 otherwise. For
7

i = 0, T [0, ps1 , . . . , psm ] = 1 if and only if ps = 0 for all s ∈ S. The following
formula allows to fill the table recursively for i ≥ 1:

ps − w(e) if s ∈ e,
T [i, ps1 , . . . , psm ] = max T [i−1, p0s1 , . . . , p0sm ] where p0s =
ps
otherwise.
e∈E,i∈e
It remains to check whether there exists a valid solution within the table.
To this end, we need to take the discounts into account. Clearly, an entry
T [n, ps1 , . . . , psm ] = 1 leads to a solution if the following holds:
X
X
ds ≤ K.
ps −
s∈S

s∈S,ps ≥ts

The running time corresponds exactly to the time needed to fill the table:
any of the nW m cells requires at most m look-ups, which yields the claimed
running time.
t
u
Proposition 8. Clever Shopper admits an FPTalgorithm for parameter m
when all prices are equal.
Proof. We assume without loss of generality that all prices are equal to 1. Let
S 0 ⊆ S. We write fS 0 : B ∪ S → N for the following function:
fS 0 (b) = 1 for b ∈ B,
fS 0 (s) = ts for s ∈ S 0 ,
fS 0 (s) = 0 for s ∈
/ S0.
P
P
0
We write dS 0 =
s∈S 0 ds and tS =
s∈S 0 ts . An f -star subgraph of G =
(B ∪ S, E) is a subgraph G0 such that the degree of each vertex u ∈ B ∪ S is at
most f (u) in G0 , and every connected component of G0 is isomorphic to K1,p for
some integer p.
Let I = (B ∪S, E, w, D, K) be an instance of Clever Shopper with w(e) =
1 for all e ∈ E. We show that I is a yes-instance if and only if there exists S 0 ⊆ S
with |B| − dS 0 ≤ K such that (B ∪ S, E) admits an fS 0 -star subgraph with tS 0
edges. An FPT algorithm follows easily from this characterisation: enumerate all
subsets S 0 of S in time 2|S| , and for each subset, compute a maximum fS 0 -star
subgraph in time O(|E| log |B ∪ S|) [9].
⇒ Let E 0 ⊆ E be a solution and S 0 be the set of shops whose threshold ts is
reached. Since the total price is |B| − dS 0 , we have |B| − dS 0 ≤ K. Since every
weight equals 1, all vertices of S 0 have degree at most ts in E 0 . Let E 00 ⊆ E 0 be a
subset obtained by keeping exactly ts edges incident to each s ∈ S 0 and no edge
incident to s ∈
/ S. Then E 00 is an fS 0 -star subgraph of size tS 0 .
0
⇐ Let G = (B ∪ S, E 0 ) be an fS 0 -star factor of G of size tS 0 with S 0 ⊆ S, and
|B| − dS 0 ≤ K. The degree and size constraints force all vertices in S 0 to have
degree exactly ts in G0 . We build a solution as follows: for each book b ∈ B, if
E 0 contains an edge (b, s) incident to b, then buy b from shop s, otherwise buy b
from any other shop. Overall, at least ts books are purchased from a shop s ∈ S 0 ,
so the total price is at most |B| − dS 0 .
t
u
8

4

Approximations

Since variants of Clever Shopper are, by and large, hard to solve exactly, it
is natural to look for approximation algorithms. However, our hardness proofs
can be modified to imply the NP-hardness of deciding whether the total price
(including discounts) is 0 or more. For instance, in Proposition 1, we can set the
discounts to T /2 instead of 1, so the Partition instance reduces to checking
whether the optimal solution has cost 0. Therefore, we start with the following
bad news:
Corollary 1. Clever Shopper admits no approximation unless P = NP.
Since this result seems resilient to most natural restrictions on the input
structure (bounded prices, bounded degree, etc.), our proposed angle is to maximise the total discount rather than minimise the total cost. However, maximising the total discount is only relevant when the base price of the books is the
same in all solutions (otherwise the optimal solution might not be the one with
maximum discount), i.e., each book b has a fixed price wb , and w({b, s}) = wb
for every {b, s} ∈ E. We call this variant Max-Discount Clever Shopper.
This “fixed price” constraint is not strong (all reductions from Section 2 satisfy
it). In this setting, Proposition 1 shows that it is NP-hard to decide whether the
optimal discount is 1 or 2. This yields the following corollary:
Corollary 2. Max-Discount Clever Shopper is APX-hard: it does not admit a (2 − )-approximation unless P = NP.
Whether or not Max-Discount Clever Shopper admits a fixed-ratio approximation remains open.
Proposition 9. Max-Discount Clever Shopper is APX-hard even when
each shop sells at most 3 books, and each book is available in at most 2 shops.
Proof. We reduce from Max 3-Sat (the problem of satisfying the maximum
number of clauses in a 3-sat instance), known to be APX-hard when each literal
occurs exactly twice [2]. Let ϕ = C1 ∧ C2 ∧ · · · ∧ Cm be such a 3-CNF formula
over a set X = {x1 , x2 , . . . , xn } of boolean variables. For every 1 ≤ i ≤ m and
1 ≤ j ≤ 3, let `i,j be the j-th literal of clause Ci . We obtain an instance I of MaxDiscount Clever Shopper by first building a bipartite graph G = (B ∪ S, E)
as follows (for ease of presentation, Ci , xi and `i,j will be used both to denote
respectively clauses, variables and literals in 3-CNF formula context, and the
corresponding vertices in G):
B = {`i,j : 1 ≤ i ≤ m and 1 ≤ j ≤ 3} ∪ {xi : 1 ≤ i ≤ n}
S = {Ci : 1 ≤ i ≤ m} ∪ {ti , fi : 1 ≤ i ≤ n}
E = E1 ∪ E2,p ∪ E2,n ∪ E3
9

where
E1 = {{`i,j , Ci } : 1 ≤ i ≤ m and 1 ≤ j ≤ 3}
E2,p = {{`i,j , ti } : 1 ≤ i ≤ m and `i,j is the positive literal xi }
E2,n = {{`i,j , fi } : 1 ≤ i ≤ m and `i,j is the negative literal xi }
E3 = {{xi , ti }, {xi , fi } : 1 ≤ i ≤ n}.
Observe that each shop sells exactly 3 books and that each book is sold in exactly
2 shops. We now turn to defining the prices, the thresholds and the discounts.
All shops sell books at a unit price. For the shops Ci , 1 ≤ i ≤ m, a purchase
of value 1 yields a discount of 1. For the shops ti and fi , 1 ≤ i ≤ n, a purchase
of value 3 yields a discount of 2. This discount policy implies that, for every
1 ≤ i ≤ n, a customer cannot obtain a 2 discount both in shop ti and in shop fi
(this follows from the fact that the book xi is sold by both shops ti and fi ).
First, it is easy to see that the largest discount that can be obtained is
2n + m (the upper bound is achieved by obtaining a discount in every shop Ci
for 1 ≤ i ≤ m, and in either the shop ti or the shop fi for 1 ≤ i ≤ n). On
the other side, for any truth assignment τ for ϕ satisfying k clauses, a 2n + k
discount can be obtained as follows.
– For any variable xi , 1 ≤ i ≤ n, if τ (xi ) = false, then buy 3 books from
shop ti , and if τ (xi ) = true then buy 3 books from shop fi . Intuitively,
if a variable is true, then all negative literals are “removed” by fi , and all
positive literals remain available for the corresponding clauses.
– For any clause Ci = `i,1 ∨ `i,2 ∨ `i,3 satisfied by the truth assignment τ , buy
book `i,j from shop Ci , where `i,j is a literal satisfying the clause Ci .
Then it follows that
opt(I) = 2n + opt(ϕ) = 3m/2 + opt(ϕ)
≤ 3 opt(ϕ) + opt(ϕ)

(since 4n = 3m)
(since 2 opt(ϕ) ≥ m)

≤ 4 opt(ϕ).
Suppose now that we buy all books in B for a total discount of k 0 . First, we
may clearly assume that k 0 ≥ 2n since a total 2n discount can always be achieved
by buying 3 books either from shop ti or from shop fi , for every 1 ≤ i ≤ n.
Second, we may also assume that, for every 1 ≤ i ≤ n, we buy either exactly 3
books from shop ti or exactly 3 books from shop fi . Indeed, if there exists an
index 1 ≤ i ≤ n for which this is false, then buying either exactly 3 books from
shop ti or exactly 3 books from shop fi instead results in a total k 00 discount
with k 00 ≥ k 0 (this follows from the fact that we can get a 2 discount from ti or
fi but only a 1 discount from any shop Cj , 1 ≤ j ≤ m). We now obtain a truth
assignment τ for ϕ as follows: for any variable xi , 1 ≤ i ≤ n, set τ (xi ) = false
if we buy 3 books from shop ti , and set τ (xi ) = true if we buy 3 books from
shop fi (the truth assignment τ is well-defined since, for 1 ≤ i ≤ n, we cannot
simultaneously buy 3 books from shop ti and 3 books from shop fi because of
10

book xi ). Therefore, a clause Ci is satisfied by τ if and only if the corresponding
shop Ci contains at least one book li,j which is not bought from some other shop
ti or fi . If we let k stand for the number of clauses satisfied by τ , then we obtain
k ≥ k 0 − 2n. It then follows that
opt(ϕ) − k = opt(I) − 2n − k ≤ opt(I) − 2n − k 0 + 2n = opt(I) − k 0 .
Therefore, our reduction is an L-reduction (i.e., opt(I) ≤ α1 opt(ϕ) and opt(ϕ)−
k ≤ α2 (opt(I) − k 0 )) with α1 = 4 and α2 = 1.
t
u
Proposition 10. Max-Discount Clever Shopper where each shop sells at
most k books admits a k-approximation.
Proof. Let Bs be the set of books sold by shop s. Our approximation algorithm
proceeds as follows: start with a set of selected shops S 0 = ∅, a set of available
books B 0 = B and sort the shops by decreasing value of ds . Then forPeach shop s,
let Bs0 = Bs ∩B 0 . If the books in Bs0 are enough to get the discount ( b∈B 0 ≥ ts ),
s
then assign all books of Bs0 to shop s, add s to S 0 and set B 0 = B 0 \ Bs0 . Finally,
assign the remaining books to arbitrary shops that sell them.
We now prove the approximation ratio. For any b ∈ B, if b ∈ Bs0 for some
0
s ∈ S 0 then
P let δ(b) = d1s ,Pand δ(b) = 0 otherwise. Thus, for any shop s ∈ S ,
1
ds = |B 0 | b∈B 0 δ(b) ≥ k b∈B 0 δ(b) due to the degree-k constraint. Note that
s
s
s
for each shop of S 0 , the amount spent
P at s is at least
P ts , so the total discount
obtained with this algorithm is D ≥ s∈S 0 ds ≥ k1 b∈B δ(b)
We now compare the result of the algorithm with any optimal solution. For
such a solution, let D∗ be its total discount, S ∗ be the set of shops where purchases reach the threshold, and, for any s ∈ S ∗P
, let Bs∗ be the (non-empty) set
∗
of books purchased in shop s. Note that D = s∈S ∗ ds .
Consider a shop s ∈ S ∗ . We show that there exists a book b∗ (s) ∈ Bs∗ with
∗
δ(b (s)) ≥ ds . If s ∈ S ∗ ∩ S 0 , then we take b∗ (s) to be any book in Bs∗ . Either
b∗ (s) ∈ Bs0 , in which case δ(b∗ (s)) = ds , or b∗ (s) ∈
/ Bs0 , in which case b∗ (s) was
assigned by the algorithm to a shop with a larger discount, i.e., δ(b∗ (s)) ≥ ds . If
s ∈ S ∗ \ S 0 , since s ∈
/ S 0 , at least one book in Bs∗ is not available at the time the
algorithm considers shop s; let b∗ (s) be such a book. Since it is not available, it
has been selected as part of Bs0 0 for some earlier shop s0 (i.e., ds ≤ ds0 ). Therefore,
∗
b∗ (s) ∈ Bs∗ ∩ Bs0 0 and δ(b
Since the sets Bs∗ are pairwise disjoint
P (s)) = ∗ds0 ≥ ds .P
∗
for s ∈ S , we have s∈S ∗ δ(b (s)) ≤
b∈B δ(b). Putting it all together, we
obtain:
X
X
X
D∗ =
ds ≤
δ(b∗ (s)) ≤
δ(b) ≤ kD.
s∈S ∗

s∈S ∗

b∈B

t
u

5

Conclusion

We introduced the Clever Shopper problem, a variant of Internet Shopping with free deliveries and shop-specific discounts based on shop-specific thresholds. We proved a number of hardness results, both in the classical complexity
11

setting and from a parameterised complexity point of view. We also gave efficient
algorithms for particular cases where restrictions apply to the number of books,
the number of shops, or the nature of prices.
An interesting angle for future work is that of designing efficient exact algorithms for the general cases in which our FPT algorithms are not sufficient.
Furthermore, it would be of interest to determine whether the Clever Shopper
problem is FPT for parameter maximum price + number of shops.

Bibliography
[1] S. Assmann, D. Johnson, D. Kleitman, and J.-T. Leung, On a dual version of the one-dimensional bin packing problem, J. Algorithms, 5 (1984),
pp. 502–525.
[2] P. Berman, M. Karpinski, and A. D. Scott, Approximation hardness of short
symmetric instances of MAX-3SAT, Electronic Colloquium on Computational Complexity (ECCC), (2003).
[3] J. Blazewicz, M. Y. Kovalyov, J. Musial, A. P. Urbanski, and A. Wojciechowski, Internet shopping optimization problem, Applied Mathematics
and Computer Science, 20 (2010), pp. 385–390.
[4] J. Blazewicz, P. Bouvry, M. Y. Kovalyov, and J. Musial, Internet shopping
with price sensitive discounts, 4OR, 12 (2014), pp. 35–48.
[5] J. Blazewicz, N. Cheriere, P.-F. Dutot, J. Musial, and D. Trystram, Novel
dual discounting functions for the internet shopping optimization problem:
new algorithms, J. Sched., 19 (2016), pp. 245–255.
[6] H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch, Kernelization lower
bounds by cross-composition, SIAM J. Discrete Math., 28 (2014), pp. 277–
305.
[7] M. Cesati, Perfect code is W[1]-complete, Inf. Process. Lett., 81 (2002),
pp. 163–168.
[8] J. Edmonds, Paths, trees and flowers, Canad. J. Math, (1965), pp. 449–467.
[9] H. N. Gabow, A note on degree-constrained star subgraphs of bipartite
graphs, Inf. Process. Lett., 5 (1976), pp. 165–167.
[10] T. F. Gonzalez, Clustering to minimize the maximum intercluster distance,
Theor. Comput. Sci., 38 (1985), pp. 293–306.
[11] K. Jansen, S. Kratsch, D. Marx, and I. Schlotter, Bin packing with fixed
number of bins revisited, J. Comput. Syst. Sci., 79 (2013), pp. 39–49.
[12] R. M. Karp, Reducibility among combinatorial problems, in Proceedings of
a symposium on the Complexity of Computer Computations, R. E. Miller
and J. W. Thatcher, eds., The IBM Research Symposia Series, Yorktown
Heights, New York, Mar. 1972, Plenum Press, pp. 85–103.
[13] R. van Bevern, C. Komusiewicz, R. Niedermeier, M. Sorge, and T. Walsh,
H-index manipulation by merging articles: Models, theory, and experiments,
Artificial Intelligence, 240 (2016), pp. 19 – 35.

12

A

Proof of Proposition 4

The following classical NP-complete problem [12] will be useful in that regard.
Exact Cover By 3-Sets (X3C)
Input:
a set X = {x1 , x2 , . . . , x3m } of items, a collection C of 3-sets of X.
Question: is there a subset C 0 of C that covers each item of X exactly once?
X3C remains NP-complete when each xi appears in exactly 3 sets of C [10].
Proof. We build an or-composition using Exact Cover By 3-Sets. Consider t instances of X3C over the same number n of items. They are represented
as bipartite graphs (Sh ∪[n], Eh ) for h ∈ [t], where the 3-sets of [n] are represented
as degree-3 vertices u ∈ Sh .
We first define some “shop identifiers”. Write J = {0, 1} × [dlog te]. For each
integer h ∈ [t], let Keyh be the size-dlog te subset of J containing (b, j) if the jth
digit in the binary representation of h is equal to b. Note that for 1 ≤ h < h0 ≤ t,
we have Keyh 6= Keyh0 . We now build a new instance (B ∪ S, E, w, D, K) as
follows:
– Create shops
S σj for all j ∈ J. Let Σ = {σj | j ∈ J}. The global set of shops
is S = Σ ∪ h∈[t] Sh . Note that |S| = t + 2 log t.
– Create books xij for all i ∈ [n] and j ∈ J. The global set of books is B =
{xij | i ∈ [n], j ∈ J} ∪ [n]. Let n0 = |B| = n(2 log t + 1).
– For each edge e = {s, i} ∈ Eh , where h ∈ [t], s ∈ Sh , i ∈ [n], add edges {s, i}
and {s, xij } for all j ∈ Keyh . Add also edges {σj , xij } for all i ∈ [n] and j ∈ J.
The overall set of edges is denoted E.
– Let all costs be equal to T + 1 where T is any non-negative integer (say,
T = 42).
– Let shop s ∈ S have ts = k(T + 1) and ds = k where k is the degree of s. In
other words, all shops give a discount of 1 per book only the buyer buys all
books available from the shop.
– The budget is K = T n0 .
Note that due to the pricing and discount functions, the average cost of a
book in a shop is between T and T + 1, and it reaches T if and only if all books
in this shop have been purchased. Since the shopper needs to buy n0 books with
a budget of T n0 , she must either buy all books from the shops she visits, or
none at all. Thus she is faced with the problem of finding a set of shops whose
available books correspond exactly to the set of books she needs.
The intuitive idea behind our construction is the following. We first build a
set of shops behaving exactly like the union of all the sets in the instances of
X3C. This is achieved directly by selling the original books in the corresponding
shops: the fact that each book must be taken exactly once directly gives an exact
cover. The rest of the shops (Σ) and books (xij ) ensure that shops are used from
a single set Sh . More precisely, half of the books xij are purchased together with
book i, and they correspond to an identifier of the shops, while the other half
must be purchased in shops from Σ, and enforce that the identifiers are the same
13

for all books. That is, all books are purchased in shops from the same set Sh ,
which yields a solution to the hth instance of X3C.
We now formally prove that there is a solution to this instance of Clever
Shopper if and only if some instance (Sh ∪[n], Eh ) of Exact Cover By 3-Sets
for h ∈ [t], is a yes-instance, which completes the or-composition.
⇐ Let h ∈ [t] be such that (Sh ∪ [n], Eh ) is a yes-instance. Let Sh0 be the
solution (that is, a subset of Sh such that all vertices in [n] have exactly one
neighbour in Sh0 ). Let Σ 0 = {σj | j ∈ J \ Keyh }. We show that buying all books
in all shops of S 0 = Sh0 ∪ Σ 0 gives a valid solution. Pick i ∈ [n]. Since Sh0 is
a solution to the X3C instance, then there exists a single s ∈ Sh0 such that
(s, i) ∈ E. Books i and xij for j ∈ Keyh are thus sold by shop s, but not by
any other shop in S 0 (in particular, not by any shop in Σ 0 since j ∈
/ Keyh ).
Consider now a book xij with i ∈ [n] and j ∈ J \ Keyh . Then xij is sold by shop
σj ∈ Σ 0 ⊂ S 0 , and by no other shop in S 0 . Overall, each book is sold by exactly
one shop in S 0 , so the shopper buys all books from those shops, for a base price
of n0 (T + 1) and with a discount of n0 .
⇒ As it has been remarked already, in any solution, the set of shops S 0 ⊆ S
must contain each book exactly once. Consider first book 1: it is sold by a shop
s1 ∈ S 0 ∩ Sh1 for some h1 ∈ [t] (since no shop in Σ sells books in [n]). Consider
/ S0.
now books x1j , with j ∈ J. If j ∈ Keyh1 , then x1j is sold by s1 , and thus σj ∈
1
0
If j ∈ J \ Keyh1 , then xj is not sold by s1 , nor by any other shop in S \ Σ
(such a shop would also sell book 1, which is already taken from shop s1 ). Thus
x1j must be sold by some shop from Σ, which can only be σj by construction.
Hence {σj | J \ Keyh } ⊆ S 0 . Consider now any index h2 6= h1 . There exists some
j ∈ Keyh2 \ Keyh1 . If there exists some shop s ∈ Sh2 ∩ S 0 , then s sells book
xij for some i ∈ [n]. However, this book is already taken at shop σj ∈ S 0 (since
j ∈ J \ Keyh1 ), hence there is no such shop s. Overall, S 0 \ Σ ⊆ Sh1 , that is, the
shopper uses only shops from the same set Sh1 as well as some shops from Σ 0 .
We can now prove that Sh0 1 = S 0 ∩ Sh1 = S 0 \ Σ is a solution to the instance
(Sh1 ∪ [n], Eh1 ) of Exact Cover By 3-Sets. Indeed, consider any i ∈ [n], then
it is sold by a single shop in s ∈ S 0 , which cannot be in Σ, hence s ∈ Sh0 1 . In
other words, there is exactly one s ∈ Sh0 1 such that (s, i) ∈ Eh1 , so Sh0 1 is a valid
cover of [n].
t
u

14

S1

S2

S3

St

Σ

...

1

2

3

...

4

n

x10,1

x11,1

x20,1

x21,1

x30,1

x31,1

x40,1

x41,1

xn
0,1

xn
1,1

x10,2

x11,2

x20,2

x21,2

x30,2

x31,2

x40,2

x41,2

xn
0,2

xn
1,2

x10,3

x11,3

x20,3

x21,3

x30,3

x31,3

x40,3

x41,3

xn
0,3

xn
1,3

x10,4

x11,4

x20,4

x21,4

x30,4

x31,4

x40,4

x41,4

xn
0,4

xn
1,4

Fig. 3. Illustration of the reduction from Exact Cover By 3-sets. The instances
are drawn in the top part, as bipartite graphs between Sh and books [n] (for better
readability, most edges are ommited, but in fact all vertices in sets Sh have degree 3).
The reduction introduces shops in Σ, and books xij . Books sold in one of the shops
from S2 are highlighted in green. They correspond to the books i to which this element
is connected in the corresponding instance of Exact Cover, as well as books xij where
j visits the elements of Key2 (the “identifier” of S2 ). Since 2 is written 0010 in binary,
the key contains positions (0, 1), (0, 2), (1, 3), (0, 4). Books sold by shop σ0,3 ∈ Σ are
highlighted in red. They are books xi0,3 for all i. Notice that those two shops have no
books in common, since (0, 3) ∈
/ Key2 .

15

