A new approach for bicriteria partitioning problem

In this paper, we propose a new method to evaluate the performance of an algorithm for bicriteria optimization problems, specifically worst‐case boundary, which is more accurate than the original ones. We use a typical multicriteria partitioning problem to serve as an example to illustrate the strength and features of our method. We show the worst‐case boundary of the classical $LS$ algorithm, and make comparison on the efficiency between the new method and the former ones. The limitation of simultaneous optimization is also shown in our paper.