Finding Optimal Skyline Product Combination Under Price Promotive

Description

Nowadays, with the development of e-commerce, a growing number of customers choose to go shopping online. To find out attractive products from online shopping marketplaces, the skyline query is a useful tool which offers more interesting and preferable choices for customers. The skyline query and its variants have been extensively investigated. However, to the best of our knowledge, they have not taken into account the requirements of customers in certain practical application scenarios. Recently, online shopping marketplaces usually hold some price promotion campaigns to attract customers and increase their purchase intention. Considering the requirements of customers in this practical application scenario, we are concerned about product selection under price promotion. We formulate a constrained optimal product combination problem. It aims to find out the skyline product combinations which both meet a customer’s willingness to pay and bring the maximum discount rate. The COPC problem is significant to offer powerful decision support for customers under price promotion, which is certified by a customer study. To process the COPC problem effectively, we first propose a two list exact algorithm. The COPC problem is proven to be NP-hard, and the TLE algorithm is not scalable because it needs to process an exponential number of product combinations. Additionally, we design a lower bound approximate algorithm that has guarantee about the accuracy of the results and an incremental greedy algorithm that has good performance. The experiment results demonstrate the efficiency and effectiveness of our proposed algorithms.