Title: A generic FPTAS for partition type optimisation problems

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.

DOI: 10.1504/IJPS.2012.050127

International Journal of Planning and Scheduling, 2012 Vol.1 No.3, pp.209 - 233

Received: 21 Jun 2012
Accepted: 21 Aug 2012

Published online: 29 Oct 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article