Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved approximation schemes for early work scheduling on identical parallel machines with common due date
57
0
0.0
(
0
)
Added by
Weidong Li
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Weidong Li
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 particular, we consider job scheduling under incompatibility relation forming bipartite graphs, under makespan optimality criterion, on uniform and unrelated machines. We show that no algorithm can achieve a good approximation ratio for uniform machines, even for a case of unit time jobs, under $P eq NP$. We also provide an approximation algorithm that achieves the best possible approximation ratio, even for the case of jobs of arbitrary lengths $p_j$, under the same assumption. Precisely, we present an $O(n^{1/2-epsilon})$ inapproximability bound, for any $epsilon > 0$; and $sqrt{p_{sum}}$-approximation algorithm, respectively. To enrich the analysis, bipartite graphs generated randomly according to Gilberts model $mathcal{G}_{n,n,p(n)}$ are considered. For a broad class of $p(n)$ functions we show that there exists an algorithm producing a schedule with makespan almost surely at most twice the optimum. Due to our knowledge, this is the first study of randomly generated graphs in the context of scheduling in the considered model. For unrelated machines, an FPTAS for $R2|G = bipartite|C_{max}$ is provided. We also show that there is no algorithm of approximation ratio $O(n^bp_{max}^{1-epsilon})$, even for $Rm|G = bipartite|C_{max}$ for $m ge 3$ and any $epsilon > 0$, $b > 0$, unless $P = NP$.
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.31 on page 82. The techniques used are very similar. He noted that the idea for dealing with the connected version using a constant number of extra layers in the shifting technique not only appeared Zhang et al.[ZGWD09] but also in his 2005 paper [vL05]. Finally, van Leeuwen also informed us that the open problem that we posted has been resolved by Marx~[Mar06, Mar07] who showed that an efficient PTAS for MDS does not exist [Mar06] and under ETH, the running time of $n^{O(1/epsilon)}$ is best possible [Mar07]. We thank Erik Jan van Leeuwen for the information and we regret that we made this mistake. Abstract before retraction: We present two (exponentially) faster PTASs for dominating set problems in unit disk graphs. Given a geometric representation of a unit disk graph, our PTASs that find $(1+epsilon)$-approximate solutions to the Minimum Dominating Set (MDS) and the Minimum Connected Dominating Set (MCDS) of the input graph run in time $n^{O(1/epsilon)}$. This can be compared to the best known $n^{O(1/epsilon log {1/epsilon})}$-time PTAS by Nieberg and Hurink~[WAOA05] for MDS that only uses graph structures and an $n^{O(1/epsilon^2)}$-time PTAS for MCDS by Zhang, Gao, Wu, and Du~[J Glob Optim09]. Our key ingredients are improved dynamic programming algorithms that depend exponentially on more essential 1-dimensional widths of the problems.
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 the first linear time-approximation schemes for a number of well-studied fundamental problems concerning clustering of binary vectors and low-rank approximation of binary matrices. Among the problems solvable by our approach are textsc{Low GF(2)-Rank Approximation}, textsc{Low Boolean-Rank Approximation}, and vario
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 problem is known to be ${bf NP}$-hard in vertex-labeled partial $11$-trees of bounded degree. We consider series-parallel graphs, i.e., partial $2$-trees. We show that the problem remains ${bf NP}$-hard in biconnected series-parallel graphs with all but one vertex of degree $3$ or less. A positive complexity result is presented for a related problem of high practical relevance which asks for a maximum common connected subgraph that preserves blocks and bridges of the input graphs. We present a polynomial time algorithm for this problem in series-parallel graphs, which utilizes a combination of BC- and SP-tree data structures to decompose both graphs.
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-fragile graph classes, a property that is true for many natural graph classes with sublinear separators. We also provide quasipolynomial-time approximation schemes for these problems in all classes with sublinear separators.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
