Dominance relationship analysis with budget constraints

摘要

Creating a new product that dominates all its competitors is one of the main objectives in marketing. Nevertheless, this might not be feasible since in practice the development process is confined by some constraints, e.g., limited funding or low target selling price. We model these constraints by a constraint function, which determines the feasible characteristics of a new product. Given such a budget, our task is to decide the best possible features of the new product that maximize its profitability. In general, a product is marketable if it dominates a large set of existing products, while it is not dominated by many. Based on this, we define dominance relationship analysis and use it to measure the profitability of the new product. The decision problem is then modeled as a budget constrained optimization query (BOQ). Computing BOQ is challenging due to the exponential increase in the search space with dimensionality. We propose a divide-and-conquer based framework, which outperforms a baseline approach in terms of not only execution time but also space complexity. Based on the proposed framework, we further study an approximation solution, which provides a good trade-off between computation cost and quality of result.