The longest path problem is a well-known NP-hard problem which can be used to model and solve some optimization problems. There are only a few classes of graphs for which this problem can be solved polynomially. In ad...
详细信息
The longest path problem is a well-known NP-hard problem which can be used to model and solve some optimization problems. There are only a few classes of graphs for which this problem can be solved polynomially. In addition, the results show that the problem is hard to approximate within any reasonable factor for general graphs. We introduce a polynomial-time 2/3-approximation algorithm for the longest path problem in solid grid graphs. Our algorithm can also approximate the longest path between any two given boundary vertices of a solid grid graph within the same approximation factor.
We consider the following packing problem. Let alpha be a fixed real in (0, 1]. We are given a bounding rectangle rho and a set R of n possibly intersecting unit disks whose centers lie in rho. The task is to pack a s...
详细信息
We consider the following packing problem. Let alpha be a fixed real in (0, 1]. We are given a bounding rectangle rho and a set R of n possibly intersecting unit disks whose centers lie in rho. The task is to pack a set B of m disjoint disks of radius alpha into rho such that no disk in B intersects a disk in R, where m is the maximum number of unit disks that can be packed. In this paper we present a polynomial-time algorithm for alpha = 2/3. So far only the case of packing squares has been considered. For that case, Baur and Fekete have given a polynomial-time algorithm for alpha = 2/3 and have shown that the problem cannot be solved in polynomial time for any alpha > 13/14 unless P = NP.
Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. A self-stabilizing system tolerates any kind and any finite number of transient faults, such as message loss, memory ...
详细信息
Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. A self-stabilizing system tolerates any kind and any finite number of transient faults, such as message loss, memory corruption, and topology change. Because such transient faults occur so frequently in mobile ad hoc networks, distributed algorithms on them should tolerate such events. In this paper, we propose a self-stabilizing distributed approximation algorithm for the minimum connected dominating set, which can be used, for example, as a virtual backbone or routing in mobile ad hoc networks. The size of the solution by our algorithm is at most 7.6 vertical bar D-opt vertical bar + 1.4, where D-opt is the minimum connected dominating set. The time complexity is O(k) rounds, where k is the depth of input BFS tree.
Localization is a fundamental problem in robotics. The "kidnapped robot" possesses a compass and map of its environment;it must determine its location at a minimum cost of travel distance. The problem is NP-...
详细信息
Localization is a fundamental problem in robotics. The "kidnapped robot" possesses a compass and map of its environment;it must determine its location at a minimum cost of travel distance. The problem is NP-hard [G. Dudek, K. Romanik, and S. Whitesides, SIAM J. Comput., 27 (1998), pp. 583-604] even to minimize within factor c log n [C. Tovey and S. Koenig, Proceedings of the National Conference on Artificial Intelligence, Austin, TX, 2000, pp. 819-824], where n is the map size. No approximation algorithm has been known. We give an O(log(3) n)-factor algorithm. The key idea is to plan travel in a "majority-rule" map, which eliminates uncertainty and permits a link to the 1/2-Group Steiner (not Group Steiner) problem. The approximation factor is not far from optimal: we prove a c log(2-epsilon) n lower bound, assuming NP not subset of ZTIME(n(polylog(n))), for the grid graphs commonly used in practice. We also extend the algorithm to polygonal maps by discretizing the problem using novel geometric techniques.
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
暂无评论