Full Citation

Title: Dominance Relationship Analysis with Budget Constraints

Citation Type: Miscellaneous

Publication Year: 2011

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

Abstract: Customers typically buy products after comparing their features, thus several market analysis tasks(e.g., skyline computation) perform dominance analysis between products. In this paper, we study an interesting problem in this class, which has not received enough attention by past research. An important decision problem by a company is how to design a new product, which dominates all its competitors. Designing the perfect product, however, 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 (DRA) 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 of 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 tradeoff between computation cost and quality of result.

User Submitted?: No

Authors: Mamoulis, Nikos; Ge, Shen; Cheung, David W.L.; U, Leong Hou

Publisher: University of Hong Kong

Data Collections: IPUMS USA

Topics: Methodology and Data Collection, Other

Countries: