There are products on the market, which can be divided by our products (the products from our company) and competitors’ products. The products can be ranked by scores from a scoring function over the attribute values. The customers tend to buy top-ranked products called top-k products. If our products are not in the top-k products, we can upgrade our products to be top-k products to attract more customers. Upgrading a product needs an upgrading cost for gaining an upgrading benefit. In this thesis, we develop algorithms to upgrade our products to be top-k products on the market with the maximal profit. The upgrading profit is obtained by subtracting the upgrading cost from the upgrading benefit. The na?ve method requires a lot of computations. We propose an optimal solution named Consecutive Upgrading Filtering (CUF) and two greedy approaches named Sorting-Based Upgrading (SBU) and Greedy Attributes Upgrading (GAU). By reducing our problems to Fractional Knapsack Problem, we prove that these two greedy approaches also produce the optimal solution. The experiments are done with different numbers of our products, attributes, products to be upgraded, and the value of k. The execution time of SBU is much faster than the na?ve method and CUF. The GAU is used to reduce the number of attribute combinations. It is used with the na?ve method, CUF, and SBU. The best performance is when we do the upgrading by using SBU with GAU.
