On Generating Dominators of Customer Preferences

Manufacturing decisions on how to design new products have tremendous impact on the profitability of the manufacturer. This problem has recently attracted extensive research interests and motivated highly productive activities in developing the microeconomic framework for data mining and finding skyline objects in high-dimensional data. In this paper, we investigate a basic designing problem: designing products that satisfy the preferences of all customers. We formalize this problem as generating dominators (products) that dominate the preference dataset. The problem is naturally related to the microeconomic framework of data mining and the problem of finding skyline objects. The designing problem can be optimized from either the manufacturer's perspective or the customer's perspective. Our framework integrates these two perspectives and achieves optimization in a single effort. We show that this problem is NP-complete and study its computational properties. A deterministic greedy algorithm and a randomized greedy algorithm are developed. Extensive experimental evaluation on both real and simulated datasets demonstrates the effectiveness and efficiency of the proposed algorithms.