With the development of information and the integration of media, it has great practical significance and research value to build a digital learning environment based on the complicated electronic circuit. However, th...
详细信息
ISBN:
(纸本)9781467380386
With the development of information and the integration of media, it has great practical significance and research value to build a digital learning environment based on the complicated electronic circuit. However, the complicated electronic circuit in real-time need a complex and expensive technology. In order to overcome the high cost and technology, an approach was proposed for simplifying generation by approximating the excitations with rectangular pulses, triangular pulses and cosine waves which can be implemented with a moderate cost in analogical electronics. In this work, we improved a novel approach based on genetic programming, The differences between theoretical excitation signals and the approximation driving pulses, related to their excitation effects, were minimized by genetic programming. From these results, the accuracy of simulation can be improved by the new approach, the difference between theoretical complicated digital signals and the new approach is reduced. A tradeoff is obtained between the costs of implementation of digital processing in digital learning environments.
We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second mac...
详细信息
We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a 3/2-approximation algorithm that outputs a two-shipment schedule. We design a 4/3-approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables.
Given a set P of n points in the plane, the two-circle point-labeling problem consists of placing 2n uniform, non-intersecting, maximum-size open circles such that each point touches exactly two circles. It is known t...
详细信息
Given a set P of n points in the plane, the two-circle point-labeling problem consists of placing 2n uniform, non-intersecting, maximum-size open circles such that each point touches exactly two circles. It is known that this problem is NP-hard to approximate. In this paper we give a simple algorithm that improves the best previously known approximation factor from 4/(1 + root33) approximate to 0.5931 to 2/3. The main steps of our algorithm are as follows. We first compute the Voronoi diagram, then label each point optimally within its cell, compute the smallest label diameter over all points and finally shrink all labels to this size, We keep the O (n log n) time and O (n) space bounds of the previously best algorithm.
Given a graph G = (V, E) and a function r : V -> {0, 1, 2}, a node v is an element of V is said to be Roman dominated if r(v) = 1 or there exists a node u is an element of N-G[v] such that r(u) = 2, where N-G[v] is...
详细信息
Given a graph G = (V, E) and a function r : V -> {0, 1, 2}, a node v is an element of V is said to be Roman dominated if r(v) = 1 or there exists a node u is an element of N-G[v] such that r(u) = 2, where N-G[v] is the closed neighbor set of v in G. For i is an element of {0, 1, 2}, denote V-r(i) as the set of nodes with value i under function r. The cost of r is defined to be c(r) = vertical bar V-r(1)vertical bar + 2 vertical bar V-r(2)vertical bar. Given a positive integer Q <= vertical bar V vertical bar, the minimum partial connected Roman dominating set (MinPCRDS) problem is to compute aminimum cost function r such that at least Q nodes in G are Roman dominated and the subgraph of G induced by V-r(1) boolean OR V-r(2) is connected. In this paper, we give a (3 ln vertical bar V vertical bar + 9)-approximation algorithm for the MinPCRDS problem.
This paper addresses the problem of preemptive scheduling on parallel-task systems. A parallel-task system consists of several independent tasks, each of which can be executed on one or more processors. Du and Leung i...
详细信息
This paper addresses the problem of preemptive scheduling on parallel-task systems. A parallel-task system consists of several independent tasks, each of which can be executed on one or more processors. Du and Leung introduced the problem of minimizing the schedule length in parallel-task systems and showed that it is strongly NP-hard for both nonpreemptive and preemptive scheduling of independent tasks. This paper presents a polynomial-time approximation algorithm for preemptive scheduling of a parallel-task system with n processors and ur tasks. We derive a tight worst-case performance bound of r for the approximation algorithm, where r is the maximum factor by which we can increase the number of processors on which a task can be executed. For example, r = 2 in the model defined by Du and Leung for parallel-task systems in which a task can be executed on any integral number of processors.
In this paper we consider the maximum independent set problem in which one would like to find a maximum set of independent (i.e., pairwise nonadjacent) vertices in a given graph. The problem is NP-complete, and still ...
详细信息
In this paper we consider the maximum independent set problem in which one would like to find a maximum set of independent (i.e., pairwise nonadjacent) vertices in a given graph. The problem is NP-complete, and still remains so even if we restrict ourselves to the class of planar graphs. It has been conjectured that there exist no polynomial-time exact algorithms for any NP-complete problems. We present a polynomial-time approximation algorithm for the maximum independent set problem on planar graphs. For a given planar graph having any number n of vertices, our algorithm finds, in O(nlogn
We consider the following single-machine scheduling problem, which is often denoted 1 || Sigma f(j): we are given n jobs to be scheduled on a single machine, where each job j has an integral processing time p(j), and ...
详细信息
We consider the following single-machine scheduling problem, which is often denoted 1 || Sigma f(j): we are given n jobs to be scheduled on a single machine, where each job j has an integral processing time p(j), and there is a nondecreasing, nonnegative cost function f(j)(C-j)that specifies the cost of finishing j at time C-j;the objective is to minimize Sigma(n)(j=1) f(j)(C-j). Bansal and Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the linear program is less than 4. Finally, we show how the technique can be adapted to yield, for any epsilon > 0, a polynomial time (4 + epsilon)-approximation algorithm for this problem.
A modified fast approximation algorithm for the 0-1 knapsack problem with improved complexity is presented, based on the schemes of lbarra, Kim and Babat. By using a new partition of items, the algorithm solves the n-...
详细信息
A modified fast approximation algorithm for the 0-1 knapsack problem with improved complexity is presented, based on the schemes of lbarra, Kim and Babat. By using a new partition of items, the algorithm solves the n-item 0-1 knapsack problem to any relative error tolerance epsilon > 0 in the scaled profit space P*/K = O(1/epsilon(1+delta)) with time O(n log(l/s) + 1/epsilon(2+2delta)) and space O(n + 1/epsilon(2+delta)), where P* and b are the maximal profit and the weight capacity of the knapsack problem, respectively, K is a problem-dependent scaling factor, delta = alpha/(1 + alpha) and alpha = O(log b). This algorithm reduces the exponent of the complexity bound in [5].
作者：
Liu, XiaofeiLi, WeidongPeking Univ
Sch Elect Engn & Comp Sci Beijing 100871 Peoples R China Yunnan Univ
Sch Math & Stat Kunming 650504 Yunnan Peoples R China Yunnan Univ
Dianchi Coll Kunming 650000 Yunnan Peoples R China
In this paper, we introduce the multicut problem in trees with submodular penalties, which generalizes the prize-collecting multicut problem in trees and vertex cover with submodular penalties. We present a combinator...
详细信息
ISBN:
(数字)9783030271954
ISBN:
(纸本)9783030271954;9783030271947
In this paper, we introduce the multicut problem in trees with submodular penalties, which generalizes the prize-collecting multicut problem in trees and vertex cover with submodular penalties. We present a combinatorial 3-approximation algorithm, based on the primal-dual scheme for the multicut problem in trees.
We present a combinatorial primal-dual 7-approximation algorithm for the k-level stochastic facility location problem, the stochastic counterpart of the standard k-level facility location problem. This approximation r...
详细信息
ISBN:
(纸本)9783642143540
We present a combinatorial primal-dual 7-approximation algorithm for the k-level stochastic facility location problem, the stochastic counterpart of the standard k-level facility location problem. This approximation ratio is slightly worse than that of the primal-dual 6-approximation for the standard k-level facility location problem [3] because of the extra stochastic assumption. This new result complements the recent non-combinatorial 3-approximation algorithm for the same problem by Wang et al [21].
暂无评论