藉由客戶偏好和成本限制搜尋天際線

Finding Skyline with Customer Preferences and Cost Constraints

天際線和優控關係的分析在商業的應用上越來越受到重視。在商業應用的情境中，資料空間中的一個點，就代表了一個廠商的產品。若廠商的產品為一個skylinepoint，那代表本產品是一個具有競爭力的產品。更精確地說，代表了這個產品在市場上，並沒有競爭對手。在本論文中，我們提出了「藉由客戶偏好和成本限制搜尋天際線」的問題。在本問題中，我們探討了以廠商的角度來看，資料處理的技術如何幫助廠商找出資料空間中具有足夠利潤，有競爭力，並且能對使用者有足夠足引力的產品。給一個客戶偏好的集合和成本限制，我們提出了一系列的演算法，幫助廠商尋找產品空間中符合成本限制（如此一來才有利潤），以及能吸引最多使用者的skyline產品。在論文中，我們詳細地定義了此一問題，提出了設計演算法的原理、pruning的技巧，以及相關的理論。此外，我們也證明了演算法以及相關輔助定理的正確性。最後，我們做了完整的實驗評估而且展示了演算法的效能。

The importance of skyline and dominance relationship analysis has been well recognized in multicriteria decision-making applications. In this paper, we propose the problem of 'Finding Skyline with Customer Preferences and Cost Constraints', which utilizes the concept of dominance for business analysis from a microeconomic perspective. Our problem aims to discoverdiscover the dominance relationship between products and potential customers. Given a set of customer preferences, we want to help the company to design set of competitive products so that the products can satisfy as many customer requirements as possible and the cost of producing the products is within a specified threshold. By 'competitive products' we mean that the products cannot be dominated by other products in the market. We formally define the problem and discuss the difficulty of the problem. We also present the foundation and the intuition of our pruning methods. Then we proposed three efficient algorithms that utilize our pruning methods to address the problem. In addition, we also prove the correctness of our proposed algorithms. Finally, we conduct a thorough experimental evaluation that demonstrates the efficiency of our proposed algorithms.