Optimal Allocation for Rank-Consistent Grouping Services

In this paper, we investigate a fundamental assignment problem for a type of constrained group service. A group is considered successfully formed only if the number of assigned patrons falls within the specified lower and upper-bound constraints. We introduce the concept of rank-consistent to characterize a useful subset of the assignment problem. Although the problem is still NP-hard, we introduce the technique of allocation vectors to handle the complexity. This technique not only allows us to exploit several characteristics for performance optimization but also enables us to design a generic procedure to obtain the optimal physical assignment under a given allocation vector. We lay the foundation of a 1/2 approximation algorithm and a branch and bound algorithm for seeking the optimal solution. The branch and bound algorithm employs a specific pattern of optimal allocation vector and several newly proposed pruning techniques, especially the one that utilizes the dominance relations between allocation vectors. Extensive experiments demonstrate that our algorithm is much more effective than a set of heuristic greedy algorithms.