This paper focuses on the prospects of “profit maximization with sufficient customer satisfaction.” The authors present 11 lemmas, nine examples, six definitions, two challenges, two theorems and one algorithm, an appendix containing proofs of several lemmas and theorems, as well as the “k-satisfiability assignment for maximizing the profit (k-SAMP)” problem. The authors conducted experiments using CentOS Linux “on an IBM X3650 M3 server with 2x6-Core 2.66GHz and 48GB RAM,” and “all algorithms were implemented in C/C++.”

For the experimental setup, the authors use both real and synthetic datasets: Package and National Basketball Association (NBA), and preference queries, respectively. Package consists of 4936 trips with five attributes and cost, records mostly of hotels and flights from Priceline.com and Expedia. The NBA dataset contains technical statistics of 17247 players with 17 attributes, namely points, rebounds, and assists, and so on, collected from 1960 to 2001, whereas cost of a player corresponds to the sum of all of his attribute values. For preference-based queries, the authors use three types of distributions: anti-correlated, correlated, and independent, indicating good and poor, good and desirable, and random and independent attribute values, respectively. Further, they confirm the use of anti-correlated products by default where all attribute values fall in the range of zero and one.

The authors’ introduction to the k-SAMP problem, relating it to “two classic computer science problems, namely maximum weight matching and maximum matching,” makes the paper worth reading. They further relate maximum weight matching and maximum matching to profit maximization and customer satisfiability maximization, respectively.

The authors assert that the solutions of the maximum weight matching and maximum matching problems cannot be applied to their k-SAMP problem. Furthermore, they “formulate the k-SAMP problem as an integer linear programming (ILP) problem”; however, experiments demonstrate that solving the ILP problem is very expensive and not scalable. Thus, to overcome this, the authors propose their Adjust algorithm for their k-SAMP problem and discuss the COIN-OR branch-and-cut baseline algorithm.

This paper is an interesting read for researchers working in the area of profit maximization based on customer relations and product satisfaction.