𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Artur Czumaj; Leszek Ga̧sieniec; Daya Ram Gaur; Ramesh Krishnamurti; Wojciech Rytter; Michele Zito

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
195 KB
Volume
302
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 k1; k2, denoted VLSP(k1; k2). In the current paper, we ÿrst 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(k1; k2), k1 ¡ k2, was presented and it was claimed that the algorithm achieves the approximation ratio of 1 + (k1(k2 -k1))=k2. In this paper we give a problem instance for which the same algorithm obtains the approximation ratio ≈ k 2 k 1 . We then present two simple approximation algorithms, one for the case k1 = 1 with an approximation ratio of 2, and one for the case k1 ¿ 1 with an approximation ratio of 2 + (k2=2k1). This corrects the result claimed in (Czumaj et al., Theoret. Comput. Sci. 262 (1-2), ( 2001) 569-582).

📜 SIMILAR VOLUMES

Polynomial time approximation algorithms
Polynomial time approximation algorithms for machine scheduling: ten open problems
✍ Petra Schuurman; Gerhard J. Woeginger 📂 Article 📅 1999 🏛 Springer US 🌐 English ⚖ 91 KB 👁 2 views

We discuss what we consider to be the 10 most vexing open questions in the area of polynomial time approximation algorithms for NP-hard deterministic machine scheduling problems. We summarize what is known on these problems, we discuss related results, and we provide pointers to the literature. Copy

A polynomial-time algorithm for the two-
A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
✍ Vadim G. Timkovsky 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 1014 KB

We consider a polynomial-time algorithm for the following scheduling problem: Given two machines, where each machine can process at most one job at a time; a set of jobs, where each job can start on or after its release date and consists of a chain of unit-time operations such that the machines have

A Polynomial Time Algorithm for Diophant
A Polynomial Time Algorithm for Diophantine Equations in One Variable
✍ F CUCKER; P KOIRAN; S SMALE 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 195 KB

We exhibit an algorithm computing, for a polynomial f ∈ Z [t], the set of its integer roots. The running time of the algorithm is polynomial in the size of the sparse encoding of f .

2-Approximation algorithms for the multi
2-Approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times
✍ Yoshiyuki Karuno; Hiroshi Nagamochi 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 180 KB

In this paper, given a path G with n vertices v1; v2; : : : ; vn and m identical vehicles, we consider a scheduling problem of the vehicles on the path. Each vertex vj in G has exactly one job j. Any of the n jobs must be served by some vehicle. Each job j has a release time rj and a handling time h