Reference : Complexity of product positioning and ball intersection problems
Scientific journals : Article
Business & economic sciences : Quantitative methods in economics & management
Complexity of product positioning and ball intersection problems
Crama, Yves mailto [Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production >]
Hansen, Pierre []
Jaumard, Brigitte []
Mathematics of Operations Research
Institute for Operations Research (INFORMS)
Yes (verified by ORBi)
[en] product positioning ; location theory ; ball intersection ; intersection graph
[en] The product positioning problem consists in choosing the attributes of a new product in such a way as to maximize its market share, i.e., to attract a maximum number of customers. Mathematically, the problem can be formulated as follows: given a set of balls (with respect to some norm) and a weight associated to each ball, find a point which maximizes the sum of the weights of the balls containing it. The complexity of this problem is investigated in the case of the L∞ and of the Euclidean norms. In both cases, the problem is proved to be NP-hard, but to be polynomially solvable when the dimension of the space is fixed.

File(s) associated to this reference

Fulltext file(s):

Restricted access
ProductPositioningMOR.pdfPublisher postprint478.19 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.