Authors: Mikhail Y. Kovalyov; Wieslaw Kubiak
Addresses: United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012, Minsk, Belarus. ' Faculty of Business Administration, Memorial University, St. John's, NL, A1B 3X5, Canada
Abstract: A partition type optimisation problem (problem PTopt) defined on partitions of a set is introduced. Its objective function is a composition of a number of auxiliary recursively computable functions. The conditions on the composition and the auxiliary functions sufficient for developing a fully polynomial time approximation scheme (FPTAS) for PTopt are established. An FPTAS for PTopt is given under these conditions. Several well-known discrete optimisation and scheduling problems are shown to be special cases of the problem PTopt and meet the sufficient conditions. This results into FPTASes for some new problems, and generalises several existing FPTASes under one framework.
Keywords: fully polynomial time approximation scheme; FPTAS; discrete optimisation; scheduling.
International Journal of Planning and Scheduling, 2012 Vol.1 No.3, pp.209 - 233
Received: 21 Jun 2012
Accepted: 21 Aug 2012
Published online: 27 Oct 2012 *