In this paper, we consider the W-prize-collecting scheduling problem on a single machine, where each job has a profit. The objective is to minimize the makespan of the accepted jobs and the total rejection cost of the...
详细信息
ISBN:
(纸本)9781450397773
In this paper, we consider the W-prize-collecting scheduling problem on a single machine, where each job has a profit. The objective is to minimize the makespan of the accepted jobs and the total rejection cost of the rejected jobs, conditional on their total profit no less than a given threshold. We first analyze the computational complexities when all jobs have the same parameter. Then, we present a 2-approximation algorithm. Furthermore, we provide two pseudo-polynomial time algorithms. Finally, a fully polynomial time approximation scheme (FPTAS) is given for this problem. Our numerical tests indicate that both dynamic programming algorithms can easily solve large-size problems.
Green data transmission is important for wireless networks,such as sensor networks, mobile networks, *** paper gives approximation algorithms for constructing energy constrained minimum cost Steiner trees (ECMST), a t...
详细信息
Green data transmission is important for wireless networks,such as sensor networks, mobile networks, *** paper gives approximation algorithms for constructing energy constrained minimum cost Steiner trees (ECMST), a topology for data multicast considering both saving energy and minimizing the occupied *** a given undirected graph, in which each edge is with nonnegative integral cost and energy consumption, the ECMST problem is to compute a minimum cost tree spanning all specified terminals and satisfying a given energy consumption *** ECMST is NP-hard, since it includes the minimum Steiner tree problem which is known *** the paper, we first presents an approximation algorithm by extending Byrka et al.'s method [3] via Lagrangian ***, we improve the ratio of the approximation algorithm to (9, 3) by replacing components of the computed Steiner *** improvement is mainly based on three ingredients: a generalization of the k-Steiner ratio against ECMST, the observation that ECMST is pseudo-polynomial solvable when the number of the terminals are fixed, and the extension of Byrka and et al.'s approximation *** the best of our knowledge, our algorithm is with the best ratio in the current state of the *** Ravi and Goemans [21] have proposed a (1 + ε, 1)-approximation algorithm for the special case when all vertices are terminals, their method can not be applied to ECMST, since their method is based on a matroid property which doesn't ho]d for ECMST.
With the rise of industrialization, the importance of the industrial Internet of Things (IIoT) has increased significantly, and with it comes a variety of security threats. Therefore, the security of these networks is...
详细信息
With the rise of industrialization, the importance of the industrial Internet of Things (IIoT) has increased significantly, and with it comes a variety of security threats. Therefore, the security of these networks is critical. Industrial Response Systems (IRSs), as the last line of security, plays an important role in the security system of the Industrial Internet of Things. In this paper, a new IRS model based on the non-cooperative game is proposed. First, by combining the Partially Observable Markov Decision Process (POMDP) model with the stochastic game model based on the expanded attack tree, our model could effectively perceive the changes at each node. Second, our model incorporates the alarms of intrusion detection system (IDS) and the physical quantities of sensors in Industrial Cyber-Physical System (ICPS) into the quantization system so that the model can respond to intruders more accurately and comprehensively. Finally, we develop this model based on multiprocessors to speed up the solution process, and adopt an approximation algorithm to reduce the number of iterations of the POMDP
The Set Cover problem is tantalizingly simple to describe: given a collection F of sets, each containing a subset of a universe U of objects, find a smallest sub-collection A of F such that every object in U is includ...
详细信息
ISBN:
(纸本)9781921770302
The Set Cover problem is tantalizingly simple to describe: given a collection F of sets, each containing a subset of a universe U of objects, find a smallest sub-collection A of F such that every object in U is included in at least one of the sets in A. However, like many such combinatorial problems, Set Cover is NP-hard, meaning that it is unlikely that an efficient algorithm will be found, and that approximation algorithms must be preferred for non-trivial problem instances. One well-known approximation approach for Set Cover is to repeatedly add the set with the most uncovered items to the solution, continuing until every element in the universe is covered; this Greedy approach has a provable logarithmic approximation ratio, essentially the best feasible ratio. Here we study the implementation of the Greedy approach to Set Cover, evaluating eager and lazy versions and other implementation options. Experiments with several large datasets demonstrate that lazy "as required" priority queue updates should be preferred, rather than eager "as soon as possible" ones; and that when implemented in this way, the Greedy mechanism can solve some large instances of the Set Cover problem very quickly. This practical superiority contrasts with the lazy version's having a demonstrably higher worst-case operation cost.
This paper presents a novel theoretical analysis for Borda's algorithm and local search algorithm for rank aggregation, which is a heated topic in the field of search technology nowadays and is also known as a ...
详细信息
This paper presents a novel theoretical analysis for Borda's algorithm and local search algorithm for rank aggregation, which is a heated topic in the field of search technology nowadays and is also known as a NPhard problem. In contrast to the previous known approximation ratio of Borda's algorithm, which is 5, we show in this paper that Borda's algorithm is at most 5-8/k approximation for rank aggregation, where k is the number of permutations to be aggregated. Local search algorithm is also widely used in this area but to our best knowledge, there is no approximation ratio analysis for such an algorithm. In other words, this paper proposes the first theoretical analysis for local search rank aggregation algorithm and shows that this algorithm is;actually expected-k/2 approximation. At the end of this paper, several simulation results yields that local search algorithm is a good practical way for the approximation of rank aggregation.
We consider a new two-stage flexible flow shop in which there are twoparallel processors at stage 1 and only one burn-in processor with capacity of twoat stage 2. The problem is to determine an optimal schedule so as ...
详细信息
We consider a new two-stage flexible flow shop in which there are twoparallel processors at stage 1 and only one burn-in processor with capacity of twoat stage 2. The problem is to determine an optimal schedule so as to minimize themakespan. This scheduling problem is NP-hard, two approximation algorithms withworst-case performance ratio 5/2 are given.
In the classical scheduling problems, it is always assumed that jobs would be delivery immediately when they are completed. However, in many production-distribution systems, the jobs are required to be delivered by th...
详细信息
In the classical scheduling problems, it is always assumed that jobs would be delivery immediately when they are completed. However, in many production-distribution systems, the jobs are required to be delivered by their due date but completed times. Then those jobs completed ahead of their due dates must be stored. In this paper, we consider the single machine scheduling problem with inventory operations. The objective is to minimize makespan subject to minimize ∑Uj . We show the problem is strongly NP-hard. A polynomial 2-approximation scheme for the problem is presented and a special case of the problem, in which each job is one unit in size, is provided an optimal algorithm.
We revisit the traveling salesman problem with neighborhoods (TSPN) and propose several new approximation algorithms. These constitute either first approximations (for hyperplanes, lines, and balls in R-d, for d >=...
详细信息
We revisit the traveling salesman problem with neighborhoods (TSPN) and propose several new approximation algorithms. These constitute either first approximations (for hyperplanes, lines, and balls in R-d, for d >= 3) or improvements over previous approximations achievable in comparable times (for unit disks in the plane). (I) Given a set of n hyperplanes in R-d, a traveling salesman problem (TSP) tour whose length is at most O(1) times the optimal can be computed in O(n) time when d is constant. (II) Given a set of n lines in R-d, a TSP tour whose length is at most O(log(3) n) times the optimal can be computed in polynomial time for all d. (III) Given a set of n unit balls in R-d, a TSP tour whose length is at most O(1) times the optimal can be computed in polynomial time when d is constant.
In this paper,we consider the Soft-Capacitated dynamic facility location problem with penalties （SCDFLPWP）.We present a 3.7052-approximation primal-dual combinatorial algorithm for DFLPSP.
In this paper,we consider the Soft-Capacitated dynamic facility location problem with penalties （SCDFLPWP）.We present a 3.7052-approximation primal-dual combinatorial algorithm for DFLPSP.
暂无评论