ﻻ يوجد ملخص باللغة العربية
We study the early work scheduling problem on identical parallel machines in order to maximize the total early work, i.e., the parts of non-preemptive jobs executed before a common due date. By preprocessing and constructing an auxiliary instance which has several good properties, we propose an efficient polynomial time approximation scheme with running time $O(n)$, which improves the result in [Gy{o}rgyi, P., Kis, T. (2020). A common approximation framework for early work, late work, and resource leveling problems. {it European Journal of Operational Research}, 286(1), 129-137], and a fully polynomial time approximation scheme with running time $O(n)$ when the number of machines is a fixed number, which improves the result in [Chen, X., Liang, Y., Sterna, M., Wang, W., B{l}a.{z}ewicz, J. (2020b). Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date. {it European Journal of Operational Research}, 284(1), 67-74], where $n$ is the number of jobs, and the hidden constant depends on the desired accuracy.
In this paper the problem of scheduling of jobs on parallel machines under incompatibility relation is considered. In this model a binary relation between jobs is given and no two jobs that are in the relation can be scheduled on the same machine. In
Retraction note: After posting the manuscript on arXiv, we were informed by Erik Jan van Leeuwen that both results were known and they appeared in his thesis[vL09]. A PTAS for MDS is at Theorem 6.3.21 on page 79 and A PTAS for MCDS is at Theorem 6.3.
We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constrains. The new constrained clustering problem encompasses a number of problems and by solving it, we obtain t
The complexity of the maximum common connected subgraph problem in partial $k$-trees is still not fully understood. Polynomial-time solutions are known for degree-bounded outerplanar graphs, a subclass of the partial $2$-trees. On the other hand, the
We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable in graphs of bounded treewidth. These schemes apply in all fractionally treewidth-