### Abstract

In many commercial campaigns, we observe that there exists a trade-off between the number of customers satisfied by the company and the profit gained. Merely satisfying as many customers as possible or maximizing the profit is not desirable. To this end, in this paper, we propose a new problem called k-Satisfiability Assignment for Maximizing the Profit (k-SAMP) where k is a user parameter and a non-negative integer. Given a set P of products and a set O of customers, k-SAMP is to find an assignment between P and O such that at least k customers are satisfied in the assignment and the profit incurred by this assignment is maximized. Although we find that this problem is closely related to two classic computer science problems, namely maximum weight matching and maximum matching, the techniques developed for these classic problems cannot be adapted to our k-SAMP problem. In this work, we design a novel algorithm called Adjust for the k-SAMP problem. Given an assignment A, Adjust iteratively increases the profit of A by adjusting some appropriate matches in A while keeping at least k customers satisfied in A. We prove that Adjust returns a global optimum. Extensive experiments were conducted which verified the efficiency of Adjust.

Original language | English |
---|---|

Article number | 19 |

Journal | ACM Transactions on Knowledge Discovery from Data |

Volume | 12 |

Issue number | 2 |

Early online date | 01 Jan 2018 |

DOIs | |

Publication status | Early online date - 01 Jan 2018 |

## Fingerprint Dive into the research topics of 'Profit Maximization with Sufficient Customer Satisfactions'. Together they form a unique fingerprint.

## Cite this

Long, C., Wong, R. C-W., & Wei, V. J. (2018). Profit Maximization with Sufficient Customer Satisfactions.

*ACM Transactions on Knowledge Discovery from Data*,*12*(2), [19]. https://doi.org/10.1145/3110216