In this paper we consider the job interval selection problem (JISP), a simple scheduling model with a rich history and numerous applications. Special cases of this problem include the so-called real-time scheduling pr...
详细信息
In this paper we consider the job interval selection problem (JISP), a simple scheduling model with a rich history and numerous applications. Special cases of this problem include the so-called real-time scheduling problem (also known as the throughput maximization problem) in single- and multiple-machine environments. In these special cases we have to maximize the number of jobs scheduled between their release date and deadline (preemption is not allowed). Even the single-machine case is NP-hard. The unrelated machines case, as well as other special cases of JISP, are MAX SNP-hard. A simple greedy algorithm gives a two-approximation for JISP. Despite many efforts, this was the best approximation guarantee known, even for throughput maximization on a single machine. In this paper, we break this barrier and show an approximation guarantee of less than 1.582 for arbitrary instances of JISP. For some special cases, we show better results.
A large number of network applications today allow several users to interact together using the many-to-many service mode. In many-to-many communication, also referred to as group communication, a session consists of ...
详细信息
A large number of network applications today allow several users to interact together using the many-to-many service mode. In many-to-many communication, also referred to as group communication, a session consists of a group of users (we refer to them as members), where each member transmits its traffic to all other members in the same group. In this paper, we address the problem of grooming subwavelength many-to-many traffic (e. g., OC-3) into high-bandwidth wavelength channels (e.g., OC-192) in optical wavelength division multiplexing (WDM) mesh networks. The cost of an optical WDM network is dominated by the cost of higher-layer electronic ports (i.e., transceivers). A transceiver is needed for each initiation and termination of a lightpath. Therefore, our objective is to minimize the total number of lightpaths established. Unfortunately, the grooming problem even with unicast traffic has been shown to be NP-hard. In this paper, we introduce two novel approximation algorithms for the many-to-many traffic grooming problem. We also consider the routing and wavelength assignment problem with the objective of minimizing the number of wavelengths used. Through extensive experiments, we show that the proposed algorithms use a number of lightpaths that is very close to that of a derived lower bound. Also, we compare the two algorithms on other important objectives such as the number of logical hops traversed by a traffic stream, total amount of electronic switching at a node, and Min-Max objectives.
We present approximation algorithms for several network design problems in the model of flexible graph connectivity (Adjiashvili et al., in: IPCO, pp 13-26, 2020, Math Program 1-33, 2021). Let k >== 1, p >= 1 an...
详细信息
We present approximation algorithms for several network design problems in the model of flexible graph connectivity (Adjiashvili et al., in: IPCO, pp 13-26, 2020, Math Program 1-33, 2021). Let k >== 1, p >= 1 and q >= 0 be integers. In an instance of the ( p, q)-Flexible Graph Connectivity problem, denoted ( p, q)-FGC, we have an undirected connected graph G = (V, E), a partition of E into a set of safe edges l and a set of unsafe edges U, and nonnegative costs c : E -> R(>=)0 on the edges. A subset F subset of. E of edges is feasible for the ( p, q)-FGC problem if for any set F 'subset of. U with | F '| <= q, the subgraph (V, F\ F ') is p-edge connected. The algorithmic goal is to find a feasible solution F that minimizes c( F) = Sigma F-e is an element of(ce.) We present a simple 2-approximation algorithm for the (1, 1)-FGC problem via a reduction to the minimum-cost rooted 2-arborescence problem. This improves on the 2.527-approximation algorithm of Adjiashvili et al. Our 2-approximation algorithm for the (1, 1)-FGC problem extends to a (k + 1)-approximation algorithm for the (1, k)-FGC problem. We present a 4-approximation algorithm for the (k, 1)-FGC problem, and an O(q log | V|)-approximation algorithm for the ( p, q)-FGC problem. Finally, we improve on the result of Adjiashvili et al. for the unweighted (1, 1)-FGC problem by presenting a 16/11-approximation algorithm. The ( p, q)-FGC problem is related to the well-known Capacitated k-Connected Subgraph problem (denoted Cap-k-ECSS) that arises in the area of Capacitated Network Design. We give a min(k, 2u(max))-approximation algorithm for the Cap-k-ECSS problem, where u(max) denotes the maximum capacity of an edge.
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.
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.
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.
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.
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.
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).
For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a n...
详细信息
For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K-2}. In this paper we provide new approximation algorithms and hardness results for the K-r-packing problem where K-r = {K-2, K-3,K- . . . , K-r}. We show that already for r = 3 the K-r-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.
暂无评论