We consider the N/P-hard problem of scheduling n jobs in m two-stage parallel flow shops so as to minimize the makespan. This problem decomposes into two subproblems: assigning the jobs to parallel flow shops;and sche...
详细信息
We consider the N/P-hard problem of scheduling n jobs in m two-stage parallel flow shops so as to minimize the makespan. This problem decomposes into two subproblems: assigning the jobs to parallel flow shops;and scheduling the jobs assigned to the same flow shop by use of Johnson's rule. For m = 2, we present a 3/2-approximation algorithm, and for m = 3, we present a 12/7-approximation algorithm. Both these algorithms run in O(n log n) time. These are the first approximation algorithms with fixed worst-case performance guarantees for the parallel flow shop problem. (C) 2011 Elsevier B.V. All rights reserved.
Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomp...
详细信息
Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible interval. Earlier works developed an optimal off-line algorithm to schedule all the jobs in a given job set and on-line heuristics to schedule the jobs in a best effort manner. This paper is concerned with how to find a schedule in which the number of jobs completed in one of their feasible intervals is maximized. We show that the maximization problem is NP-hard for both non-preemptible and preemptible jobs. This paper develops two approximation algorithms for non-preemptible and preemptible jobs. When jobs are non-preemptible, Algorithm Least Earliest Completion Time First (LECF) is shown to have a 2-approximation factor;when jobs are preemptible, Algorithm Least Execution Time First (LEF) is proved being a 3-approximation algorithm. We show that our analysis for the two algorithms are tight. We also evaluate our algorithms by extensive simulations. Simulation results show that algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms in average.
We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)***,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i....
详细信息
We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)***,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ E_(l) plus this line l,denoted by T_(l)=(S,l,E_(l)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(l) among all such Steiner ***,we are asked to find a set E_(0) of necessary edges such that a graph consisting of all line segments in S ∪ E_(0),denoted by T_(S)=(S,E_(0)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(0) among all such Steiner trees,we refer to this new problem as the minimum Steiner tree of line segments(MStT-LS)*** addition,when two endpoints of each edge in Eo need to be located on two different line segments in S,respectively,we refer to that problem as the minimum spanning tree of line segments(MST-LS)*** obtain three main results:(1)Using technique of Voronoi diagram of line segments,we design an exact algorithm in time O(n log n)to solve the MST-LS problem;(2)we show that the algorithm designed in(1)is a 1.214-approximation algorithm to solve the MStT-LS problem;(3)using the combination of the algorithm designed in(1)as a subroutine for many times,a technique of finding linear facility location and a key lemma proved by techniques of computational geometry,we present a 1.214-approximation algorithm in time O(n^(3) log n)to solve the 1L-MStT-LS problem.
When ties and incomplete preference lists are permitted in the Stable Marriage and Hospitals/Residents problems, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching ...
详细信息
When ties and incomplete preference lists are permitted in the Stable Marriage and Hospitals/Residents problems, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching in this context is known to be NP-hard, even under very severe restrictions on the number, size and position of ties. In this paper, we describe polynomial-time 5/3-approximation algorithms for variants of these problems in which ties are on one side only and at the end of the preference lists. The particular variant is motivated by important applications in large scale centralised matching schemes.
In this paper, we consider the 1-line Euclidean minimum Steiner tree problem, which is a variation of the Euclidean minimum Steiner tree problem and defined as follows. Given a set P=of n points in the Euclidean plane...
详细信息
In this paper, we consider the 1-line Euclidean minimum Steiner tree problem, which is a variation of the Euclidean minimum Steiner tree problem and defined as follows. Given a set P=of n points in the Euclidean plane R2, we are asked to find the location of a line l and an Euclidean Steiner tree T(l) in R2 such that at least one Steiner point is located at such a line l, the objective is to minimize total weight of such an Euclidean Steiner tree T(l), i.e., min{ n-ary sumation e is an element of T(l)w(e)|T(l)\ is an Euclidean Steiner tree as mentioned-above}, where we define weight w(e)=0 if the end-points u, v of each edge e=uv is an element of T(l) are both located at such a line l and otherwise we denote weight w(e) to be the Euclidean distance between u and v. Given a fixed line l as an input in R2, we refer this problem as the 1-line-fixed Euclidean minimum Steiner tree problem;In addition, when Steiner points added are all located at such a fixed line l, we refer this problem as the constrained Euclidean minimum Steiner tree problem. We obtain the following two main results. (1) Using a polynomial-time exact algorithm to find a constrained Euclidean minimum Steiner tree, we can design a 1.214-approximation algorithm to solve the 1-line-fixed Euclidean minimum Steiner tree problem, and this algorithm runs in time O(nlogn);(2) Using a combination of the algorithm designed in Sect. 1 for many times, a technique of finding linear facility location and an important lemma proved by some techniques of computational geometry, we can provide a 1.214-approximation algorithm to solve the 1-line Euclidean minimum Steiner tree problem, and this new algorithm runs in time O(n(3)log n).
Consider a set of n jobs and in uniform parallel machines, where each job has a length p(j )is an element of Q(+) and each machine has a speed s(i) is an element of Q(+). The goal of the graph balancing problem with s...
详细信息
Consider a set of n jobs and in uniform parallel machines, where each job has a length p(j )is an element of Q(+) and each machine has a speed s(i) is an element of Q(+). The goal of the graph balancing problem with speeds is to schedule each job j non-preemptively on one of a subset M-j of at most 2 machines so that the makespan is minimized. This is a NP-hard special case of the makespan minimization problem on unrelated parallel machines, where for the latter a longstanding open problem is to find an approximation algorithm with approximation ratio better than 2. Our main contribution is an approximation algorithm for the graph balancing problem with two speeds and two job lengths with approximation ratio (root 65+7)/8 approximate to 1.88278. In addition, we consider when every M-j has no cardinality constraints, this is the restricted assignment problem in the uniform parallel machine setting. We present a simple (2 - alpha/beta)-approximation algorithm in this case when every job has one of two job lengths p(j) is an element of {alpha, beta} where alpha < beta.
We study two generalizations of classic clustering problems called dynamic ordered k -median and dynamic k-supplier, where the points that need clustering evolve over time, and we are allowed to move the cluster cente...
详细信息
We study two generalizations of classic clustering problems called dynamic ordered k -median and dynamic k-supplier, where the points that need clustering evolve over time, and we are allowed to move the cluster centers between consecutive time steps. In these dynamic clustering problems, the general goal is to minimize certain combinations of the service cost of points and the movement cost of centers, or to minimize one subject to some constraints on the other. We obtain a constant-factor approximation algorithm for dynamic ordered k-median under mild assumptions on the input. We give a 3-approximation for dynamic k-supplier and a multi-criteria approximation for its outlier version where some points can be discarded, when the number of time steps is two. We complement the algorithms with almost matching hardness results.(c) 2022 Elsevier Inc. All rights reserved.
Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function L : E -> N. In addition, each label rho is an element of N has a non-negative cost c(rho). The m...
详细信息
Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function L : E -> N. In addition, each label rho is an element of N has a non-negative cost c(rho). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I subset of N such that the edge set {e is an element of E : L(e) is an element of I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label s - t path problem (MinLP) the goal is to identify an s-t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.
We consider the following two instances of the projective clustering problem: Given a set S of n points in R-d and an integer k > 0, cover S by k slabs (respectively d-cylinders) so that the maximum width of a slab...
详细信息
We consider the following two instances of the projective clustering problem: Given a set S of n points in R-d and an integer k > 0, cover S by k slabs (respectively d-cylinders) so that the maximum width of a slab (respectively the maximum diameter of a d-cylinder) is minimized. Let w* be the smallest value so that S can be covered by k slabs (respectively d-cylinders), each of width (respectively diameter) at most w*. This paper contains three main results: (i) For d = 2, we present a randomized algorithm that computes O(k log k) strips of width at most w* that cover S. Its expected running time is O(nk(2) log(4) n) if k(2) log k less than or equal to n;for larger values of k, the expected running time is O(n(2/3) k(8/3) log(14/3) n). (ii) For d = 3, a cover of S by O(k log k) slabs of width at most w* can be computed in expected time O(n(3/2)k(9/4) polylog(n)). (iii) We compute a cover of S subset of R-d by O(d k log k) d-cylinders of diameter at most 8w* in expected time O(dnk(3) log(4) n). We also present a few extensions of this result. (C) 2003 Elsevier Science (USA). All rights reserved.
Let G = (V,E,w) be an undirected graph with nonnegative edge length function w and nonnegative vertex weight function,. The optimal product-requirement communication spanning tree (PROCT) problem is to find a spanning...
详细信息
Let G = (V,E,w) be an undirected graph with nonnegative edge length function w and nonnegative vertex weight function,. The optimal product-requirement communication spanning tree (PROCT) problem is to find a spanning tree T minimizing Sigma(u,v is an element of V) r(u)r(v)d(T)(u,v), where d(T)(u,v) is the length of the path between u and v on T. The optimal sum-requirement communication spanning tree (SROCT) problem is to find a spanning tree T such that Sigma(u,v is an element of V) (r(u) + r(v))d(T)(u,v) is minimized. Both problems are special cases of the optimum communication spanning tree problem, and are reduced to the minimum routing cost spanning tree (MRCT) problem when all the vertex weights are equal to each other. In this paper, we present an O(n(5))-time 1.577-approximation algorithm for the PROCT problem, and an O(n(3)) time 2-approximation algorithm for the SROCT problem, where n is the number of vertices. We also show that a 1.577-approximation solution for the MRCT problem can be obtained in O(n(3))-time, which improves the time complexity of the previous result. (C) 2000 Elsevier Science B.V. All rights reserved.
暂无评论