Previous | [1] | [2] | [3] | 4 | [5] | [6] | [7] | [8] |

On the Performance Guarantees of the

Minimum Multisets Binding (MMB) Problem

**Yuan-Long Jeang, Jhing-Fa Wang and Jau-Yien Lee**

National Cheng-Kung University

Tainan, Taiwan, R.O.C.

The decision version of the MINIMUM MULTISETS BINDING (MMB) problem was discussed and proved to be NP-complete in [1]. In this paper, we will prove that there is no polynomial time algorithm with constant difference guarantee, no fully polynomial approximation scheme and no polyllomial approximation scheme for the optimization version of the MMB problem unless P = NP. An approximation algorithm called SM which takes polynomial time is then provided to achieve the ahsolute performance ration for any instance I of the MMB problem, where n is the "length" of the instance I.

Keywords: performance guarantees, constant difference guarantees, (fully) polynomial approximation scheme, absolute performance ratio

Received June 1, 1990; revised December 30, 1990.

Communicated by Ferng-Ching Lin.
**REFERENCES**

- Jeang, Yuan-Long, Wang, Jhing-Fa and Lee, Jau-Yien, "The Minimum Multisets Binding Problem is Strongly NP-Complete," submitted to
*International Journal of Computer Mathematics*.