Optimal product design using conjoint analysis: Computational complexity and algorithms
The problem of maximizing the share of a new product introduced in a competitive market is shown to be NP-hard. A directed graph representation of the problem is used to construct shortest path and dynamic programming heuristics. Both heuristics are shown to have arbitrarily bad worst-case bounds. Computational experience with real- sized problems is reported. Both heuristics identify near-optimal solutions for the simulated problems, the dynamic programming heuristic performing better than the shortest path heuristic.
scientific article; zbMATH DE number 4085409