Groupe d’études et de recherche en analyse des décisions

# Complexity of Product Positioning and Ball Intersection Problems

## Yves Crama, Pierre Hansen et Brigitte Jaumard

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 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.

, 20 pages

Ce cahier a été révisé en juin 1994