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

Journal of Inforamtion Science and Engineering, Vol.7 No.2, pp.203-215 (June 1991)
On the Performance Guarantees of the
Minimum Multisets Binding (MMB) Problem

Yuan-Long Jeang, Jhing-Fa Wang and Jau-Yien Lee
Department of Electrical Engineering
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 JISEfor 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

  1. 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.