We investigate the seemingly untouched yet the most general parallel identical k-stage flow-shops scheduling, in which we are given an arbitrary number of indistinguishable k-stage flow-shops and a set of jobs each to...
详细信息
We investigate the seemingly untouched yet the most general parallel identical k-stage flow-shops scheduling, in which we are given an arbitrary number of indistinguishable k-stage flow-shops and a set of jobs each to be processed on one of the flow-shops, and the goal is to schedule these jobs to the flow-shops so as to minimize the makespan. Here the number k of stages is a fixed constant, but the number of flow-shops is part of the input. This scheduling problem is strongly NP-hard. To the best of our knowledge all previously presented approximation algorithms are for the special case where k=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 2$$\end{document}, including a 17/6-approximation in 2017, a (2+epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(2 + \epsilon )$$\end{document}-approximation in 2018, and the most recent polynomial-time approximation scheme in 2020;they all take advantage of the number of stages being two. We deal with an arbitrary constant k >= 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 3$$\end{document}, where the k-stage flow-shop scheduling is already strongly NP-hard. To define a configuration that summarizes the key information about the job assignments in a feasible schedule, we present novel concepts of big job type, big job assignment pair type, and flow-shop type. We show that the total number of distinct configurations is a polynomial in the input number of flow-shops. We t
For two independent Erdos-Renyi graphs G(n,p)$$ \mathbf{G}\left(n,p\right) $$, we study the maximal overlap (i.e., the number of common edges) of these two graphs over all possible vertex correspondence. We present a ...
详细信息
For two independent Erdos-Renyi graphs G(n,p)$$ \mathbf{G}\left(n,p\right) $$, we study the maximal overlap (i.e., the number of common edges) of these two graphs over all possible vertex correspondence. We present a polynomial-time algorithm which finds a vertex correspondence whose overlap approximates the maximal overlap up to a multiplicative factor that is arbitrarily close to 1. As a by-product, we prove that the maximal overlap is asymptotically n2 alpha-1$$ \frac{n}{2\alpha -1} $$ for p=n-alpha$$ p={n}<^>{-\alpha } $$ with some constant alpha is an element of(1/2,1)$$ \alpha \in \left(1/2,1\right) $$.
As a hybrid of the Parallel Two-stage Flowshop problem and the Multiple Knapsack problem, we investigate the scheduling of parallel two-stage flowshops under makespan constraint, which was motivated by applications in...
详细信息
As a hybrid of the Parallel Two-stage Flowshop problem and the Multiple Knapsack problem, we investigate the scheduling of parallel two-stage flowshops under makespan constraint, which was motivated by applications in cloud computing and introduced by Chen et al. [3] recently. A set of two-stage jobs are selected and scheduled on parallel two-stage flowshops to achieve the maximum total profit while maintaining the given makespan constraint. We give a positive answer to an open question about its approximability proposed by Chen et al. [3]. More specifically, based on guessing strategies and rounding techniques for linear programs, we present a polynomialtimeapproximationscheme (PTAS) for the case when the number of flowshops is a fixed constant. As the case with two flowshops is already strongly NP-hard, our PTAS achieves the best possible approximation ratio. (C) 2022 Elsevier B.V. All rights reserved.
The paper is addressed to one strongly NP-hard problem of searching for the largest subset in the finite set of points in Euclidean space. A restriction is imposed on the searched subset: quadratic variation of its po...
详细信息
ISBN:
(纸本)9783030406165
The paper is addressed to one strongly NP-hard problem of searching for the largest subset in the finite set of points in Euclidean space. A restriction is imposed on the searched subset: quadratic variation of its points with respect to the unknown centroid of this subset must not exceed a given value. We present the first polynomial-time approximation scheme for this problem.
We investigate the approximability of the m parallel two-stage flow-shop (mP2FS) problem, where a set of jobs is scheduled on the multiple identical two-stage flow-shops to minimize the makespan, i.e., the finishing t...
详细信息
We investigate the approximability of the m parallel two-stage flow-shop (mP2FS) problem, where a set of jobs is scheduled on the multiple identical two-stage flow-shops to minimize the makespan, i.e., the finishing time of the last job. Each job needs to be processed non-preemptively on one flow-shop without switching to the other flow-shops. This problem is a hybrid of the classic parallel machine scheduling and two-stage flow-shop scheduling problems. Its strong NP-hardness follows from the parallel machine scheduling problem when the number of machines is part of the input. Our main contribution is a polynomial-time approximation scheme (PTAS) for the mP2FS problem when the number of shops is part of the input, which improves the previous best approximation algorithm of a ratio (2 + epsilon). Owing to the strong NP-hardness, our PTAS achieves the best possible approximation ratio. (C) 2019 Elsevier B.V. All rights reserved.
We study classical deadline-based preemptive scheduling of jobs in a computing environment equipped with both dynamic speed scaling and sleep state capabilities: Each job is specified by a release time, a deadline and...
详细信息
We study classical deadline-based preemptive scheduling of jobs in a computing environment equipped with both dynamic speed scaling and sleep state capabilities: Each job is specified by a release time, a deadline and a processing volume, and has to be scheduled on a single, speed-scalable processor that is supplied with a sleep state. In the sleep state, the processor consumes no energy, but a constant wake-up cost is required to transition back to the active state. In contrast to speed scaling alone, the addition of a sleep state makes it sometimes beneficial to accelerate the processing of jobs in order to transition the processor to the sleep state for longer amounts of time and incur further energy savings. The goal is to output a feasible schedule that minimizes the energy consumption. Since the introduction of the problem by Irani et al. (ACM Trans Algorithms 3(4), 2007), its exact computational complexity has been repeatedly posed as an open question (see e.g. Albers and Antoniadis in ACM Trans Algorithms 10(2):9, 2014;Baptiste et al. in ACM Trans Algorithms 8(3):26, 2012;Irani and Pruhs in SIGACT News 36(2):63-76, 2005). The currently best known upper and lower bounds are a 4 / 3-approximation algorithm and NP-hardness due to Albers and Antoniadis (2014) and Kumar and Shannigrahi (CoRR, 2013. ), respectively. We close the aforementioned gap between the upper and lower bound on the computational complexity of speed scaling with sleep state by presenting a fully polynomial-time approximation scheme for the problem. The scheme is based on a transformation to a non-preemptive variant of the problem, and a discretization that exploits a carefully defined lexicographical ordering among schedules.
We consider the classic FACILITY LOCATION problem on planar graphs (non-uniform, uncapacitated). Given an edge-weighted planar graph G, a set of clients C subset of V(G), a set of facilities F subset of V(G), and open...
详细信息
ISBN:
(纸本)9781728149523
We consider the classic FACILITY LOCATION problem on planar graphs (non-uniform, uncapacitated). Given an edge-weighted planar graph G, a set of clients C subset of V(G), a set of facilities F subset of V(G), and opening costs open : F -> R->= 0, the goal is to find a subset D of F that minimizes Sigma(c is an element of C) min(f is an element of D), dist(c, f) + Sigma(f is an element of D) open (f). The FACILITY LOCATION problem remains one of the most classic and fundamental optimization problem for which it is not known whether it admits a polynomial-time approximation scheme (PTAS) on planar graphs despite significant effort for obtaining one. We solve this open problem by giving an algorithm that for any epsilon > 0, computes a solution of cost at most (1 + epsilon) times the optimum in time n(2O(epsilon-2 log(1/epsilon))).
We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that ma...
详细信息
We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen [9] introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen [21] before our work was 2. Our scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. (C) 2015 Elsevier B.V. All rights reserved.
We study the minimum-weight k-size cycle cover problem (Min-k-SCCP) of finding a partition of a complete weighted digraph into k vertex-disjoint cycles of minimum total weight. This problem is a natural generalization...
详细信息
We study the minimum-weight k-size cycle cover problem (Min-k-SCCP) of finding a partition of a complete weighted digraph into k vertex-disjoint cycles of minimum total weight. This problem is a natural generalization of the known traveling salesman problem (TSP) and has a number of applications in operations research and data analysis. We show that the problem is strongly NP-hard in the general case and preserves intractability even in the geometric statement. For the metric subclass of the problem, a 2-approximation algorithm is proposed. For the Euclidean Min-2-SCCP, a polynomial-time approximation scheme based on Arora's approach is built.
In the integrated network design and scheduling problem (INDS-P), we are asked to repair edges in a graph by using parallel machines so that the performance of the network is recovered by a certain level, and the obje...
详细信息
ISBN:
(纸本)9783031185298;9783031185304
In the integrated network design and scheduling problem (INDS-P), we are asked to repair edges in a graph by using parallel machines so that the performance of the network is recovered by a certain level, and the objective is to minimize the makespan required to finish repairing edges. The main aim of this paper is to show that polynomial-time approximation schemes exist for some class of the problem (INDSP), including the problems associated with minimum spanning tree, shortest path, maximum flow with unit capacity, and maximum-weight matching.
暂无评论