On polynomial-time approximation algorithms for the variable length scheduling problem

This paper may be viewed as a corrigendum as well as an extension of the paper by (Czumaj et al. , Theoret. Comput. Sci. 262 (1–2), (2001) 569–582) where they deal with the variable length scheduling problem (VLSP) with parameters k 1, k 2, denoted VLSP(k 1, k 2). In the current paper, we first discuss an error in the analysis of one of the approximation algorithms described in (Czumaj et al. , Theoret. Comput. Sci. 262 (1–2), (2001) 569–582), where an approximation algorithm for VLSP(k 1, k 2), k 1<k 2, was presented and it was claimed that the algorithm achieves the approximation ratio of 1+(k 1(k 2−k 1))/k 2. In this paper we give a problem instance for which the same algorithm obtains the approximation ratio ≈ k2 k1. We then present two simple approximation algorithms, one for the case k1 =1 with an approximation ratio of 2, and one for the case k 1>1 with an approximation ratio of 2+(k 2/2k 1). This corrects the result claimed in (Czumaj et al. , Theoret. Comput. Sci. 262 (1–2), (2001) 569–582).

Authors

• Artur Czumaj
• Leszek Ga̧sieniec
• Daya Ram Gaur W. Ken Jackson
• Ramesh Krishnamurti
• Wojciech Rytter
• Michele Zito

Keywords

No keywords are indexed for this paper.