This is not the document you are looking for? Use the search form below to find more!

Report home > Education

ALGORITHMS FOR MARKETING-MIX OPTIMIZATION

0.00 (0 votes)
Document Description
Algorithms for determining quality/cost/price tradeoffs in saturated markets are consid- 3 ered. A product is modeled by d real-valued qualities whose sum determines the unit cost of producing 4 the product. This leads to the following optimization problem: given a set of n customers, each of 5 whom has certain minimum quality requirements and a maximum price they are willing to pay, design 6 a new product and select a price for that product in order to maximize the resulting profit
File Details
  • Added: August, 08th 2010
  • Reads: 191
  • Downloads: 5
  • File size: 196.47kb
  • Pages: 12
  • Tags: algorithms, optimization, mix
  • content preview
Submitter
  • Username: monkey
  • Name: monkey
  • Documents: 474
Embed Code:

Add New Comment




Related Documents

Creating the right marketing mix: Motorola Case Study Summary

by: bizmana, 1 pages

Motorola is a company known around the world for mobile, wireless and broadband communications. Its vision is of 'seamless mobility', helping users to get and stay connected to the people, ...

Response Modeling with Non-Random Marketing Mix Variables

by: bizmana, 43 pages

Sales response models are widely used as the basis for optimizing the marketing mix or for allocation of the sales force. Response models condition on the observed marketing mix variables and focus ...

RELATIONSHIP BETWEEN MARKETING MIX STRATEGY AND CONSUMER MOTIVE: AN EMPIRICAL STUDY IN MAJOR TESCO STORES

by: samanta, 16 pages

This paper investigates the relationship between Marketing Mix Strategy and Consumer Motives at major TESCO stores in Malaysia. A quantitative approach was used and the survey was conducted at TESCO ...

EXAMINING MARKETING MIX FROM AN ETHICAL VIEW: A FIELD RESEARCH ON MARKETING EXECUTIVES

by: samanta, 22 pages

Marketing is the most significant function of enterprises in which unethical practices are experienced. Marketing executives’ decisions relating to product, price, place and promotion items ...

Marketing: Product Positioning and the Marketing Mix (Product ...

by: eliasz, 0 pages

• Objectives: At the completion of this unit, students will be able to: 1. Define the concept of "position." 2. Define the elements of the marketing mix a. Product b. Price c. Place d. ...

10 Minute Guide Marketing Mix

by: williamstt, 5 pages

The Marketing Mix« is a term used to describe the combination of tactics used by a business to achieve its objectives by marketing its products or services effectively to a particular target ...

PRICING IN THE MARKETING MIX

by: bizmana, 9 pages

PRICING IN THE MARKETING MIX

DETERMINING THE WEIGHTS OF MARKETING MIX COMPONENTS USING ANALYTIC NETWORK PROCESS

by: samanta, 8 pages

Marketing Mix (4P); composed of Product, Price, Promotion and Place; is a set of tools that should be coherently designated to achieve a company's goals. In order to create brand equity and customer ...

AN HISTORICAL REVIEW AND MODERN ASSESSMENT OF THE MARKETING MIX CONCEPT

by: samanta, 12 pages

The history of the marketing mix construct is largely unknown to many people in marketing. This paper traces the history of the emergence of the marketing mix construct, known today as the 4Ps. ...

Twitter for Marketing and PR

by: marco, 53 pages

Twitter for Marketing and PR

Content Preview
1
ALGORITHMS FOR MARKETING-MIX OPTIMIZATION
2
Joachim Gudmundsson Pat Morin Michiel Smid
3
Abstract. Algorithms for determining quality/cost/price tradeoffs in saturated markets are consid-
4
ered. A product is modeled by d real-valued qualities whose sum determines the unit cost of producing
5
the product. This leads to the following optimization problem: given a set of n customers, each of
6
whom has certain minimum quality requirements and a maximum price they are willing to pay, design
7
a new product and select a price for that product in order to maximize the resulting profit.
8
An O(n log n) time algorithm is given for the case, d = 1, of products having a single quality,
9
and O(n(log n)d+1) time approximation algorithms are given for products with any constant number,
10
d, of qualities. To achieve the latter result, an O(nkd−1) bound on the complexity of an arrangement
11
of homothetic simplices in Rd is given, where k is the maximum number of simplices that all contain
12
a single points.
13
½
ÁÒØÖÓ
ÙØ
ÓÒ
14
Revealed preference theory [13] is a method of determining a course of business action through the
15
review of historical consumer behaviour. In particular, it is a method of inferring an individual’s or a
16
group’s preferences based on their past choices. The marketing mix [10] of a product consists of the 4
17
Ps: Product, price, place, and promotion. In the current paper, we present algorithms for optimizing
18
the first two of these by using data about consumers’ preferences. That is, we show how, given data on
19
consumer preferences, to efficiently choose a product and a price for that product in order to maximize
20
profit.
21
Refer to Figure 1. A product P = (p, q1, . . . , qd) is defined by a real-valued price, p, and
22
a number of real-valued orthogonal qualities, q1, . . . , qd. The market for a product is a collection
23
of customers C = {C1, . . . , Cn}, where Ci = (pi, qi,1, . . . , qi,d). A customer will purchase the least
24
expensive product that meets all her minimum quality requirements and whose price is below her
25
maximum price. That is, the customer Ci will consider the product P = (p, q1, . . . , qd) if p ≤ pi and
26
qj ≥ qi,j for all j ∈ {1, . . . , d}. The customer Ci will purchase the product if it has the minimum price
27
among all available products that Ci considers.
28
We consider markets that are saturated. That is, for every customer Ci there is an existing
29
product that satisfies Ci’s requirements and among all products that satisfy Ci’s requirements, Ci will
30
choose the least expensive product. From the point of view of a manufacturer introducing one or more
31
new products, this means that all customers are Pareto optimal, i.e., there are no two customers Ci
32
and Cj such that qi,k > qj,k for all k ∈ {1, . . . , d} and pi < pj. This is because no customer will
33
every purchase a product that is not Pareto optimal, since there is a lower-priced alternative that also
1

quality
q3 1
,
C3
q2 1
,
C2
q1 1
C
,
1
p1
p2
p3 price
Figure 1: A sample market with d = 1 and n = 3. A customer will consider any product that is in
their upper left quadrant.
34
satisfies all their minimum quality requirements. Therefore, every customer Ci can be replaced with
35
the (Pareto optimal) product that they purchase.
36
As an example, consider a market for computers in which an example customer Ci may be
37
looking for a computer with a minimum of 8 GB of RAM, a CPU benchmark score of at least 3000,
38
a GPU benchmark score of at least 2000, and be willing to pay at most $1500. In addition, there is
39
already a computer on the market which meets these requirements and retails for $1200. Thus, this
40
customer would be described by the vector (1200, 8, 3000, 2000). If a manufacturer introduces a new
41
product (1199, 8, 3500, 2000) (a computer with 8 GB of RAM, a CPU benchmark score of 3500 and a
42
GPU benchmark score of 2000 retailing for $1199) then this customer would select this new product
43
over their current choice.
44
By appropriately reparameterizing the axes, we can assume that the cost, cost(P ), of manufac-
45
turing a product P = (p, q1, . . . , qd) is equal to the sum of its qualities
d
46
cost(P ) =
qi .
i=1
47
The profit per unit sold of P is therefore
48
ppu(P ) = p − cost(P ) .
49
In this paper we consider algorithms that a manufacturer can use when planning a new product to
50
introduce into an existing saturated market with the goal being to maximize the profit obtained. More
51
precisely, given a Pareto-optimal market of customers M = {C1, . . . , Cn}, each having d qualities, the
52
ProductDesign(d) problem is to find a product P ∗ ∈ Rd+1 such that
53
profit(P ∗) = ppu(P ∗) × |{i : Ci purchases P ∗}|
54
is maximized.
55
The term marketing mix is probably the most famous phrase in marketing. Not surprisingly,
56
economists and market researchers have considered methods of optimizing the marketing mix in various
57
scenarios. As there are many different models of the problem, it is difficult to compare algorithms.
2

58
Most models of marketing-mix problems involve a constant number of real-valued input pa-
59
rameters. This sometimes leads to problems where the optimal solution is one of a constant number
60
of possible closed forms (see, e.g., Thomson and Teng’s optimal constant price model [12]). In other
61
cases, a closed form is not achievable, but a (sometimes approximate) solution can be obtained using
62
numerical optimization techniques (see, e.g., Balanchandran and Gensch [2], Thomson and Teng [12],
63
Naik et al. [11], Deal [6], Erickson [9]). In all cases, it is expected that the model parameters are derived
64
from real-world data, such as surveys or sales figures, and involves fitting of the model parameters to
65
the available data.
66
The work in the current paper is different from this previous work in several ways. For one, it
67
is one of the few works that deals primarily with the first two P’s, product and pricing. Most existing
68
literature focuses on the marketing P’s, namely place and promotion, and to a lesser extent, pricing
69
of an existing product. Secondly, it deals directly with data about individual consumers rather than
70
aggregating this data so that it fits a particular model of consumer behaviour.
71
We believe that this models very well what happens in online shopping for high cost products
72
such as computers, cameras, and televisions. In such markets, savvy consumers have good data available
73
about both the specifications and the cost of all available products so that marketing efforts are
74
(arguably) less important than the quality and prices of the products. On the other hand, online
75
sellers such as Amazon have large amounts of data about users’ past purchases and can use this data
76
as input to the problem. In particular, these sellers know the specifications qi,1, . . . , qi,d and prices pi
77
of huge quantities of items sold and can use this data to advise a manufacturer that is designing a new
78
product.
79
In the remainder of the paper we give an O(n log n) time algorithm for ProductDesign(1)
80
(Section 2), and O(n(log n)d+1) time approximation schemes for ProductDesign(d) (Section 3 and
81
Section 4). Section 5 summarizes our results and concludes with directions for future research.
82
¾
ÇÒ
¹
Ñ
Ò×
ÓÒ
Ð
Ô
ÖÓ
ÙØ×
83
In this section, we consider the simplest case, when a manufacturer wishes to introduce a new product
84
in which the quality of a product has only one dimension. Examples of such markets include, for
85
example, suppliers to the construction industry in which items (steel I-beams, finished lumber, logs)
86
must have a certain minimum length to be used for a particular application. An overly long piece can
87
be cut down to size, but using two short pieces instead of one long piece is not an option.
88
Throughout this section, since d = 1, we will use the shorthand P = (p, q) for the product
89
being designed and qi for qi,1. Thus, we have a set of customers M = {(p1, q1), . . . , (pn, qn)} and we
90
are searching for a point P ∗ = (p∗, q∗) that maximizes
91
profit(p∗, q∗) = (p∗ − q∗)|{i : p∗ ≤ pi and q∗ ≥ qi}| .
92
Our algorithm is an implementation of the plane-sweep paradigm [4]. The correctness of the
93
algorithm relies on two lemmas about the structure of the solution space. The first lemma is quite
94
easy:
95
Lemma 1. The value (p∗, q∗) that maximizes profit(p∗, q∗) is obtained when p∗ = pi and q∗ = qj for
96
some i, j ∈ {1, . . . , n}.
3

ppu = 0
quality (q)
(p′, q)
(p, q)
(p′, q′)
(p, q′)
price (p)
Figure 2: profit(p, q) ≤ profit(p, q′) implies that profit(p′, q) ≤ profit(p′, q′) for all p′ ≤ p.
97
Proof. First, observe the obvious bounds on p∗ and q∗:
98
min{pi : i ∈ {1, . . . , n}} ≤ p∗ ≤ max{pi : i ∈ {1, . . . , n}}
99
and
100
min{qi : i ∈ {1, . . . , n}} ≤ q∗ ≤ max{qi : i ∈ {1, . . . , n}} .
101
Consider the arrangement of lines obtained by drawing a horizontal and vertical line through each
102
customer (pi, qi) for i ∈ {1, . . . , n}. Within each cell of this arrangement, the function profit(p, q) is
103
a linear function of p and q and it is bounded. Therefore, within a particular cell, the function is
104
maximized at a vertex. Since each vertex is the intersection of a horizontal and vertical line through a
105
pair of customers, the lemma follows.
106
The following lemma, illustrated in Figure 2, is a little more subtle and illustrates a manufac-
107
turer’s preference for lower-quality products:
108
Lemma 2. Let q′ ≤ q and let p be such that 0 < profit(p, q) ≤ profit(p, q′). Then, for any p′ ≤ p,
109
profit(p′, q) ≤ profit(p′, q′).
110
Proof. By definition, profit(p, q) = a(p − q) and profit(p, q′) = a′(p − q′), where a and a′ are the number
111
of customers who would consider (p, q) and (p, q′), respectively. These customers are all taken from the
112
set M≥ = {(pi, qi) ∈ M : pi ≥ p}.
113
Now, consider the customers in the set M ′ = {(pi, qi) ∈ M : p′ ≤ pi < p}. By the assumption
114
that customers are Pareto optimal, any customer (pi, qi) in M′ has qi ≤ q′, so all of these customers
115
will consider either (p′, q′) or (p′, q) if either one is offered. Therefore,
profit(p′, q′) = (a′ + |M ′|)(p′ − q′)
= a′(p′ − q′) + |M ′|(p′ − q′)
≥ a′(p′ − q′) + |M ′|(p′ − q)
since q > q′
= a′(p − q′) + a′(p′ − p) + |M ′|(p′ − q)
116
≥ a′(p − q′) + a(p′ − p) + |M ′|(p′ − q)
since a ≥ a′ and (p′ − p) < 0
≥ a(p − q) + a(p′ − p) + |M ′|(p′ − q)
by assumption
= a(p′ − q) + |M ′|(p′ − q)
= profit(p′, q) ,
4

117
as required.
118
Lemma 2 allows us to apply the plane sweep paradigm with a sweep by decreasing price. It
119
tells us that, if a product (p, q′) gives better profit than the higher-quality product (p, q) at the current
120
price p, then it will always give a better profit for the remainder of the sweep. In particular, there will
121
never be a reason to consider a product with quality q for the remainder of the algorithm’s execution.
122
Let the customers be labelled (p1, q1), . . . , (pn, qn) in decreasing order of pi, so that pi+1 ≤ pi
123
for all i ∈ {1, . . . , n − 1}. At any point in the sweep algorithm, there is a current price p, which
124
starts at p = ∞ and decreases during the execution of the algorithm. At the start of the algorithm the
125
algorithm’s event queue Q, which is represented as a balanced binary search tree, is initialized to contain
126
the values pn, . . . , p1. At all times, the algorithm maintains a list L of qualities q∗1 > q∗2 > · · · > q∗m
127
such that profit(p, q∗1) > profit(p, q∗2) > · · · > profit(p, q∗m). The quality q∗1 is the optimal quality for
128
the current price, p. By the time the algorithm terminates, the quality of the globally-optimal solution
129
will have appeared as the first element in L. To complete the description of the algorithm, all that
130
remains is to show how L and Q are updated during the processing of events in the event queue.
131
There are two kinds of events in the event queue. Insertions occur at the values p1, . . . , pn.
132
Deletions, which we describe next, occur when the relative order of two adjacent items in L changes.
133
Consider a consecutive pair of the elements q∗i and q∗i+1 in L. When q∗i and q∗i+1 became adjacent in L,
134
it was at some price p = pt such that profit(pt, q∗i) > profit(pt, q∗i+1). Let ai and ai+1 be the number of
135
customers who would consider (pt, q∗i) and (pt, q∗i+1), respectively. Then,
136
profit(pt, q∗i) = (pt − q∗i)ai
137
and
138
profit(pt, q∗i+1) = (pt − q∗i+1)ai+1
139
Now, looking forward in time to a later step in the execution of the algorithm, when p = pt′, with
140
t′ > t, we find that
141
profit(pt′, q∗i) = (pt′ − q∗i)(ai + t′ − t)
142
and
143
profit(pt′, q∗i+1) = (pt′ − q∗i+1)(ai+1 + t′ − t) .
144
We are interested in identifying the price pt′ where the inequality profit(pt′, q∗i) > profit(pt′, q∗i+1)
145
changes to profit(pt′, q∗i) ≤ profit(pt′, q∗i+1). When this happens, q∗i can be safely discarded from L
146
since, by Lemma 2, profit(p, q∗i) will never again exceed profit(p, q∗i+1) for the remainder of the sweep.
147
The value pt′ is a deletion event.
148
Note that Lemma 2 also allows for binary search on the value pt′. In particular, the interval
149
[pj, pj+1] containing pt′ can be found in O(log n) time, after which the value of pt′ can be obtained by
150
solving the linear equation
151
(pt′ − q∗i)(ai + t′ − t) ≤ (pt′ − q∗i+1)(ai+1 + t′ − t) ,
152
for t′. (The equation is linear because the values ai and ai+1 are constant in the interval (pj, pj+1).)
153
Thus, whenever two new elements become adjacent in L, we can add the appropriate deletion event to
154
Q in O(log n) time.
155
When processing an insertion event pi, we remove from the tail of L all values q∗j such that
156
profit(pi, q∗j) ≤ profit(pi, qi) and then append qi onto L. While deleting the elements of L, we also
5

157
remove all the associated deletion events from Q. Appending qi to L causes at most one new pair of
158
elements in L to become adjacent, so we add the appropriate deletion event to Q as described above.
159
The time to process the event pi is there O((ki + 1) log n), where ki is the number of elements that are
160
deleted from L.
161
When processing a deletion event that deletes q∗i from L, we simply delete q∗i from L and its (at
162
most two) associated deletion events from Q. This may cause a new pair of elements, q∗i−1 and q∗i+1,
163
in L to become adjacent, so we add the appropriate deletion event to Q. In this way, a deletion event
164
can be processed in O(log n) time.
165
Note that, after all the processing associated with an event pt is complete, the first element, q∗1,
166
in L is the value that maximizes profit(pt, q∗1). Thus, the algorithm need only keep track, throughout
167
its execution, of the highest profit obtained from the first element of L, and output this value at the
168
end of its execution. This completes the description of the algorithm.
169
Theorem 1. There exists an O(n log n) time algorithm for ProductDesign(1).
170
Proof. The correctness of the algorithm described above follows from 2 facts: Lemma 1 ensures that
171
the optimal solution is of the form (pi, q∗) for some i ∈ {1, . . . , n}, and Lemma 2 ensures that the
172
optimal solution appears at some point as the first element of the list L.
173
The running time of the algorithm can be bounded as follows: The total number of deletion
174
events processed is at most n, since each such event removes some value qi from L for some i ∈
175
{1, . . . , n}. Thus, the cost of processing all deletion events is O(n log n). Similarly,
n
i=1 ki ≤ n since
176
ki is the number of elements deleted from L during the processing of pi. Thus, the time required to
177
handle all insertion events, and therefore the running time of the entire algorithm, is O(n log n)
178
The following theorem shows that a running time of Ω(n log n) is inherent in this problem, even
179
when considering approximation algorithms.
180
Theorem 2. Let M be an instance of ProductDesign(1) and (p∗, q∗) be a solution that maximizes
181
profit(p∗, q∗). In the algebraic decision tree model of computation, any algorithm that can find a solution
182
(p, q) such that 2 · profit(p, q) > profit(p∗, q∗) has Ω(n log n) running time in the worst-case.
183
Proof. We reduce from the integer Element-Uniqueness problem, which has an Ω(n log n) lower
184
bound in the algebraic decision tree model [14]: Given an array A = [x1, . . . , xn] containing n integers,
185
are all the elements of A unique?
186
We convert A into an instance of ProductDesign(1) in O(n) time as follows (refer to Figure 3).
187
For each xi, i ∈ {1, . . . , n} we introduce a customer (pi, qi) with pi = qi + 1/2 and qi = xi. If
188
there exists a value x in A that occurs 2 or more times, then the product (x + 1/2, x) gives a value
189
profit(x + 1/2, x) ≥ 1. On the other hand, if there is no such x, then
190
1. any product (p, q) with p − q > 1/2 can not be sold to any customers and
191
2. any product (p, q) with p − q > 0 can be sold to at most 1 customer.
6

ppu = 0
ppu = 1/2
x2
x1
q
x3
x5
x4
p
Figure 3: Reducing Element-Uniqueness to ProductDesign(1,1).
192
Therefore, if all the elements of A are unique, then profit(p∗, q∗) = 1/2, otherwise profit(p∗, q∗) ≥ 1.
193
The result follows.
194
¿
Ò
Ö¹Ð
Ò
Ö
ÔÔ
ÖÓ
Ü
Ñ
Ø
ÓÒ
Ð
Ó
Ö
Ø
Ñ
Ó
Ö
Ñ
Ò×
ÓÒ
Ð
Ô
ÖÓ
ÙØ×
195
In this section, we consider algorithms for ProductDesign(2), in which products have 2 qualities. As
196
a baseline, we first observe that, if we fix the value of q2, then the optimal solution of the form (p, q1, q2)
197
can be found using a single application of the algorithm in Theorem 1. Therefore, by successively solving
198
the problem for each q2 ∈ {q2,1, . . . , q2,n} and taking the best overall solution we obtain an O(n2 log n)
199
time algorithm for ProductDesign(2).
200
More generally, ProductDesign(d) can be solved using O(nd−1) applications of Theorem 1
201
resulting in an O(nd log n) time algorithm. Unfortunately, these are the best results known for d ≥ 2,
202
and, as discussed in Section 5, we suspect that an algorithm with running time o(nd) will be difficult
203
to achieve using existing techniques. Therefore, in this section we focus our efforts on obtaining a
204
near-linear approximation algorithm.
205
Fix some constant ǫ > 0. Given an instance M of ProductDesign(d), a point P ∈ Rd+1 is a
206
(1 − ǫ)-approximate solution for M if profit(P ) ≥ (1 − ǫ) profit(P ∗) for all P ∗ ∈ Rd+1. An algorithm
207
is a (high probability) Monte-Carlo (1 − ǫ)-approximation algorithm for ProductDesign(d) if, given
208
an instance M of size n, the algorithm outputs a (1 − ǫ)-approximate solution for M with probability
209
at least 1 − n−c for some constant c > 0.
210
Let r = max{ppu(Ci) : i ∈ {1, . . . , n}} and observe that r is the maximum profit per unit
211
that can be achieved in this market. Let E = 1/(1 − ǫ) and let ℓ = ⌈logE n⌉ and observe that
212
ℓ = O(ǫ−1 log n).1 For each i ∈ {0, 1, 2, . . . , ℓ}, define the plane Hi = {(p, q1, q2) : p−q1 −q2 = r(1−ǫ)i}.
213
The following lemma says that a search for an approximate solution can be restricted to be contained
214
in one of the planes Hi.
215
Lemma 3. For any product P ∗ = (p∗, q∗1, q∗2), there exists a product P = (p, q1, q2) such that P ∈ Hi
216
for some i ∈ {0, . . . , ℓ} and profit(P ) ≥ (1 − ǫ) profit(P ∗).
1 This can be seen by taking the limit limǫ→0+(ǫ/ log(E)) using one application of L’Hˆopital’s Rule.
7

q1
q1
q2
Hi
q2
∆i,2
C2
∆i,1
∆i,3
C1
C3
price
price
(a)
(b)
Figure 4: The intersection of Hi with customers’ quadrants is a set of homothetic equilateral triangles.
217
Proof. There are two cases to consider. If ppu(P ∗) ≤ r/n then profit(P ∗) ≤ r, in which case we set
218
P = Ci where ppu(Ci) = r, so that P ∈ H0 and profit(P ) = r ≥ profit(P ∗) ≥ (1 − ǫ) profit(P ∗), as
219
required.
220
Otherwise, r/n < ppu(P ∗) ≤ r. In this case, consider the plane Hi where i = ⌈logE(r/ ppu(P ∗))⌉.
221
Notice, that for any point P ∈ Hi, ppu(P ) ≥ (1 − ǫ) ppu(P ∗). More specifically, the orthogonal pro-
222
jection P = (p, q1, q2) of P ∗ onto Hi is a product with p ≤ p∗, q1 ≥ q∗1, and q2 ≥ q∗2. Therefore,
223
any customer who would consider P ∗ would also consider P , so profit(P ) ≥ (1 − ǫ) profit(P ∗), as
224
required.
225
Lemma 3 implies that the problem of finding an approximate solution to ProductDesign(2)
226
can be reduced to a sequence of problems on the planes H0, . . . , Hℓ. Refer to Figure 4. Each customer
227
Cj considers all products in a quadrant whose corner is Cj. The intersection of this quadrant with
228
Hi is a (possibly empty) equilateral triangle ∆i,j. The customer Cj will consider a product P in Hi
229
if and only P is in ∆i,j. Thus, the problem of solving ProductDesign(2) restricted to the plane Hi
230
is the problem of finding a point contained in the largest number of equilateral triangles from the set
231
∆i = {∆i,j : j ∈ {1, . . . , n}}.
232
Note that the elements in ∆i are homothets (translations and scalings) of an equilateral triangle,
233
so they form a collection of pseudodisks and we wish to find the deepest point in this collection of
234
pseudodisks. No algorithm with running time o(n2) is known for solving this problem exactly, but
235
Aronov and Har-Peled [1] have recently given a Monte-Carlo (1 − ǫ)-approximation algorithm for this
236
problem that runs in time O(ǫ−2n log n). By applying this algorithm to each of ∆i for i ∈ {1, . . . , ℓ},
237
we obtain the following result:
238
Theorem 3. For any ǫ > 0, there exists an O(ǫ−3n(log n)2) time high-probability Monte-Carlo (1 − ǫ)-
239
approximation algorithm for ProductDesign(2).
8

240
d
Ò
Ö¹Ð
Ò
Ö
ÔÔ
ÖÓ
Ü
Ñ
Ø
ÓÒ
Ð
Ó
Ö
Ø
Ñ
Ó
Ö
ÓÒ×Ø
ÒØ
241
In this section we extend the algorithm from the previous section to (approximately) solve ProductDesign(d)
242
for any constant value of d. The algorithm is more or less unchanged, except that the proof requires
243
some new results on the combinatorics of arrangements of homothets.
244
As before, let r = max{ppu(Ci) : i ∈ {1, . . . , n}} and let ℓ = ⌈logE n⌉. For each i ∈
245
{0, 1, 2, . . . , ℓ}, define the hyperplane Hi = {(p, q1, . . . , qd) : p −
d
i=1 qi = r(1 − ǫ)i}.
The follow-
246
ing lemma has exactly the same proof as Lemma 3.
247
Lemma 4. For any product P ∗ = (p∗, q∗1, . . . , q∗d), there exists a product P = (p, q1, . . . , qd) such that
248
P ∈ Hi for some i ∈ {0, . . . , ℓ} and profit(P ) ≥ (1 − ǫ) profit(P ∗).
249
Again, each customer Cj defines a regular simplex ∆i,j in Hi such that Cj will consider P ∈ Hi
250
if and only if P ∈ ∆i,j. In this way, we obtain a set ∆i = {∆i,1, . . . , ∆i,n} of homothets of a regular
251
simplex in Rd and we require an algorithm to find a ((1 − ǫ)-approximation to) the point that is
252
contained in the largest number of these simplices. The machinery of Aronov and Har-Peled [1] can be
253
used to help solve this problem, but not before we prove some preliminary results, the first of which is
254
a combinatorial geometry result.
255
Lemma 5. Let ∆ be a set of n homothets of a regular simplex in Rd, for d = O(1), and such that no
256
point in Rd is contained in more than k elements of ∆. Then, the total complexity of the arrangement,
257
A(∆), of the simplices in ∆ is O(nkd−1).
258
Proof. We first consider the simpler case in which the elements of ∆ are translates (without scaling) of
259
a regular simplex. Suppose that the total complexity of A(∆) is m. Then, by the pigeonhole principle,
260
there is some element T in ∆ whose surface is involved in m/n features of A(∆). (Note that this implies
261
that T intersects all the elements of a set ∆′ ⊆ ∆ with |∆′| = Ω((m/n)1/(d−1)), since otherwise there
262
are not enough elements in ∆′ to generate m/n features on the surface of ∆.)
263
Observe that, since the elements of ∆′ are all unit size and they all intersect T , that they are
264
all contained in a ball of radius O(1) centered at the center of T . Furthermore, since each element of
265
∆′ has volume Ω(1) this implies that some point must be contained in Ω((m/n)1/(d−1)) elements of ∆′.
266
Thus, we obtain the inequality k ≥ Ω((m/n)1/(d−1)), or, equivalently, m ≤ O(nkd−1), as required.
267
Now, for the case where the elements of ∆ are homothets (translations and scalings) of a regular
268
simplex, we proceed as follows. Suppose that |A(∆)| = rn. Our goal is to show that r = O(kd−1).
269
Label the elements of ∆ as T1, . . . , Tn in increasing order of size and consider the smallest element Ti
270
such that Ti contributes at least r features to A({Ti, . . . , Tn}). Such a Ti is guaranteed to exist, since
271
otherwise |A(∆)| ≤ rn.
272
Now, Ti intersects all the elements in some set ∆′ ⊆ {Ti+1, . . . , Tn} with |∆′| = Ω(r1/(d−1)).
273
Shrink each element T ′ in ∆′ so as to obtain an element T ′′ such that (a) the size of T ′′ is equal to
274
the size of Ti, (b) T ′′ ⊆ T ′, and (c) T ′′ intersects Ti. Call the resulting set of shrunken elements ∆′′.
275
Condition (a) and the packing argument above imply that there is a point p ∈ Rd that is contained in
276
Ω(r1/(d−1)) elements of ∆′′. Condition (b) implies that p is contained in Ω(r1/(d−1)) elements of ∆′ and
277
hence also ∆. Therefore, we conclude, as before, that r = O(kd−1), which completes the proof.
9

278
Lemma 5 is somewhat surprising, since the union of n homothets of a regular tetrahedron in,
Ê
Ñ
Ö
º
279
for example, R3 can easily have complexity Ω(n2). This fact makes it impossible to apply the “usual”
280
Clarkson-Shor technique [5] that relates the complexity of the first k levels to that of the boundary of
281
the union (the 0-level).
282
Lemma 6. Let ∆ be a set of n homothets of a regular simplex in Rd such that no point of Rd is
283
contained in more than k simplices of ∆. Then the arrangement A(∆) of ∆ can be computed in
284
O(n(kd−1 + (log n)d)) time.
285
Proof. Computing the arrangement A(∆) can be done in the following way. Sort the elements of ∆ by
286
decreasing size and construct A(∆) incrementally by inserting the elements one by one. When inserting
287
an element T , use a data structure (described below) to retrieve the elements of ∆ that intersect T and
288
discard the elements that are smaller than T . The proof of Lemma 5 implies that there will be at most
289
O(k) such elements. The intersection of the surfaces of these O(k) elements with the surface of T has
290
size O(kd−1) and can be computed in O(kd−1) time using d + 1 applications of the standard algorithm
291
for computing an arrangement of hyperplanes in Rd−1 [7, 8]. Thus, ignoring the cost of finding the
292
elements that intersect T , the overall running time of the algorithm is O(nkd−1).
293
All that remains is to describe a data structure for retrieving the elements that intersect a given
294
simplex T ∈ ∆. In the following we describe a data structure that can be constructed in O(n(log n)d)
295
time and can answer queries in O(x + (log n)d) time, where x is the size of the output. This data
296
structure will be constructed once and queried n times. The total size of the outputs over all n queries
297
will be the O(|A(∆)|) = O(nkd−1).
298
Refer to Figure 5. Suppose that every element T ∈ ∆ is a homothet of the regular simplex V
299
whose vertices are v1, . . . , vd+1 and let n1, . . . , nd+1 be the inner normals of the faces of V where ni
300
is the face opposite (not incident on) vertex vi. For any T ∈ ∆, let ti be the image of vi under the
301
homothetic transformation that takes V onto T . Observe that, if h is a halfspace of Rd with inner
302
normal ni, then h intersects T if and only if h contains ti. Furthermore, every simplex T ∈ ∆ is the
303
intersection of d halfspaces hT1 , . . . , hT
where the inner normal of ht
d+1
i is ni. Therefore, a simplex T ∈ ∆
304
intersects a simplex T ′ ∈ ∆ if and only if hTi contains t′i for all i ∈ {1, . . . , d + 1}.
305
This implies that the elements of ∆ can be stored in a (d + 1)-layer range tree [3]. The ith layer
306
of this tree, for i ∈ {1, . . . , d + 1}, stores elements of ∆ ordered by the projection of ti onto ni. In this
307
way, the range tree can return the set of all simplices in ∆ that intersect a query simplex T ∈ ∆. The
308
size of this range tree is O(n(log n)d) and it can answer queries in time O(x + n(log n)d) where x is the
309
size of the query result. Since each simplex in ∆ is passed as a query to this data structure exactly
310
once, the total sizes of outputs over all n queries is equal to the number of pairs T1, . . . , T2 ∈ ∆ such
311
that T1 ∩ T2 = ∅. But the number of such pairs is certainly a lower bound on |A(∆)| so it must be at
312
most O(nkd−1). This completes the proof.
313
Lemma 6 can be used as a subroutine in the algorithm of Aronov and Har-Peled [1, Theorem 3.3],
314
to obtain the following Corollary.
315
Corollary 1. Let ∆ be a set of n homothets of a regular simplex in Rd such that some point p ∈ Rd is
316
contained in δ elements of ∆. Then there exists an algorithm whose running time is O(ǫ−2dn(log n)d−1+
317
n(log n)d) and that, with high probability, returns a point p′ ∈ Rd contained in at least (1 − ǫ)δ elements
318
of ∆.
10

Document Outline

  • Introduction
  • One-dimensional products
  • A near-linear approximation algorithm for bidimensional products
  • A near-linear approximation algorithm for constant d
  • Conclusions

Download
ALGORITHMS FOR MARKETING-MIX OPTIMIZATION

 

 

Your download will begin in a moment.
If it doesn't, click here to try again.

Share ALGORITHMS FOR MARKETING-MIX OPTIMIZATION to:

Insert your wordpress URL:

example:

http://myblog.wordpress.com/
or
http://myblog.com/

Share ALGORITHMS FOR MARKETING-MIX OPTIMIZATION as:

From:

To:

Share ALGORITHMS FOR MARKETING-MIX OPTIMIZATION.

Enter two words as shown below. If you cannot read the words, click the refresh icon.

loading

Share ALGORITHMS FOR MARKETING-MIX OPTIMIZATION as:

Copy html code above and paste to your web page.

loading