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