Back

G-91-45

Complexity of Product Positioning and Ball Intersection Problems

, , and

BibTeX reference

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

This cahier was revised in June 1994