The best known solution methods for network reliability problems are of exponential time-complexity. This exponential behavior can render even moderately sized problems computationally intractable due to the enormous ...
详细信息
The best known solution methods for network reliability problems are of exponential time-complexity. This exponential behavior can render even moderately sized problems computationally intractable due to the enormous amount of time required to generate a solution. To render such problems manageable, a bounding algorithm has been developed that provides upper and lower bounds for the source-to-terminal reliability of an arbitrary network. A unique feature of this bounding algorithm is that it possesses linear time-complexity when the maximum indegree of all network nodes is limited.
The maximum cut problem is known to be an important NP-complete problem with many applications. In this paper, we investigate this problem (which we call the normal maximum cut problem) and a variant of it (which we c...
详细信息
The maximum cut problem is known to be an important NP-complete problem with many applications. In this paper, we investigate this problem (which we call the normal maximum cut problem) and a variant of it (which we call the connected maximum cut problem). Our main result are as follows. 1) We show that any n-vertex e-edge graph admits a cut with at least the fraction 1/2 + 1/2n of its edges, thus improving the ratio 1/2 + 2/e known befor. 2) We show that it is NP-complete to decide if a given graph has a normal maximum cut with at least a fraction (1/2 + epsilon) of its edges, where the positive constant epsilon can be taken smaller than any value of our choice. 3) We exhibit, however, an approximation algorithm for the normal maximum cut problem on any graph that runs in O((e log e + n log n)/p + log p . log n) parallel time using p (1 less-than-or-equal-to p less-than-or-equal-to e + n) processors, that guarantees a ratio of at least [1/2 + 1/2n], given a matching of size e/n in G. 4) We take up the connected maximum cut problem and show that, unlike the normal maximum cut problem, this problem admits an infinity of instances where the fraction of the edges in the connected maximum cut is arbitrarily close to zero. 5) We then show that the connected maximum cut problem is NP-complete even for planar graphs, in clear contrast to the normal maximum cut problem which is solvable in polynomial time on planar graphs.
A multiple stack branch and bound (MSBB) algorithm which uses a multiple stack data structure in order to reduce the overhead of selecting the most promising node in a best first search scheme is presented. A variatio...
详细信息
A multiple stack branch and bound (MSBB) algorithm which uses a multiple stack data structure in order to reduce the overhead of selecting the most promising node in a best first search scheme is presented. A variation of the algorithm MSBB is presented for providing an approximate solution with any prescribed bound on its cost of solution. Experiments were performed with the Euclidean traveling salesman problem.
In this paper, we address the job scheduling problem in a partitionable mesh-connected system when jobs require square meshes and the system is a square mesh of size a power of two. We present a heuristic algorithm of...
详细信息
In this paper, we address the job scheduling problem in a partitionable mesh-connected system when jobs require square meshes and the system is a square mesh of size a power of two. We present a heuristic algorithm of time complexity O(n(log n + log p)) where n is the number of jobs to be scheduled and p is the size of the system. The algorithm adopts the largest job first scheduling policy and uses a two-dimensional buddy system as the system partitioning scheme. It is shown that in the worst case, the algorithm produces a schedule four times longer than an optimal schedule. On the average, schedules generated by the algorithm are about twice longer than optimal schedules.
Given a set C = {c1, c2,..., c(n)} of n circles in the plane, in which circle c(i) is centered at point p(i) and has a radius of r(i), the repeaters allocating problem (RAP) is to allocate a set R = {p(n+1), p(n+2),.....
详细信息
Given a set C = {c1, c2,..., c(n)} of n circles in the plane, in which circle c(i) is centered at point p(i) and has a radius of r(i), the repeaters allocating problem (RAP) is to allocate a set R = {p(n+1), p(n+2),..., p(n+m)} of points (called repeaters) in the plane such that G(C, R) is strongly connected and the number of allocated repeaters is minimal;where digraph G(C, R) = (V, E), in which a vertex upsilon-i is-an-element-of V stands for the point p(i), 1 less-than-or-equal-to i less-than-or-equal-to n + m, and a directed edge is-an-element-of E if and only if p(j) is located within the circle of p(i) (the circle of p(k), n < i less-than-or-equal-to n + m, is assumed to have a radius of infinity). In this paper, we show that in the two-dimensional case, the RAP is NP-hard. We also show that the RAP can be reduced to the set covering problem (SCP) so that the approximation algorithms for the SCP can be applied to the RAP. An O(n log n + e) algorithm which uses an O(n) space is also proposed to solve the RAP for the one-dimensional case;here e is the number of edges in G(C, empty-set).
Although the jump number problem for partially ordered sets is NP-complete in general, there are some special classes of posets for which polynomial time algorithms are known. Here we prove that for the class of inter...
详细信息
Although the jump number problem for partially ordered sets is NP-complete in general, there are some special classes of posets for which polynomial time algorithms are known. Here we prove that for the class of interval orders the problem remains NP-complete. Moreover we describe another 3/2-approximation algorithm (two others have been developed already by Felsner and Syslo, respectively) by using a polynomial time subgraph packing algorithm.
For the traveling salesman problem in which the distances satisfy the triangle inequality, Christofides' heuristic produces a tour whose length is guaranteed to be less than 3/2 times the optimum tour length. We i...
详细信息
For the traveling salesman problem in which the distances satisfy the triangle inequality, Christofides' heuristic produces a tour whose length is guaranteed to be less than 3/2 times the optimum tour length. We investigate the performance of appropriate modifications of this heuristic for the problem of finding a shortest Hamiltonian path. There are three variants of this problem, depending on the number of prespecified endpoints: zero, one, or two. It is not hard to see that, for the first two problems, the worst-case performance ratio of a Christofides-like heuristic is still 3/2. For the third case, we show that the ratio is 5/3 and that this bound is tight.
We present a new polynomial-time heuristic algorithm for finding a solution to the Traveling Salesman Problem (TSP) for any complete and edge-weighted graph K sub(n), with a set of vertices V and a set of edges E wher...
详细信息
We present a new polynomial-time heuristic algorithm for finding a solution to the Traveling Salesman Problem (TSP) for any complete and edge-weighted graph K sub(n), with a set of vertices V and a set of edges E where !V! = n. In a few words, this method is based on the idea of linking the elements of V progressively, one by one, in such a way that the vertex selection which produces fewest disturbances to the other vertices not yet connected, will be selected as the next vertex to join to the subset of already connected vertices. When the cost of the result is compared to the cost of the best circuit, it appears that a good sub-solution is obtained in most of the cases tested. Moreover, comparison tests made between the heuristic introduced and the well-known Quick method, produce a better behaviour, for almost every case, in the first approach.
This paper proposes a new problem called the dynamic Steiner tree problem. Interest in the dynamic Steiner tree problem is motivated by multipoint routing in communication networks, where the set of nodes in the conne...
详细信息
This paper proposes a new problem called the dynamic Steiner tree problem. Interest in the dynamic Steiner tree problem is motivated by multipoint routing in communication networks, where the set of nodes in the connection changes over time. This problem, which has its basis in the Steiner tree problem on graphs, can be divided into two cases: one in which rearrangement of existing routes is not allowed, and a second in which rearrangement is allowed. For the nonrearrangeable version, it is shown that the worst-case performance for any algorithm is at least 1/2 lg n times the cost of an optimum solution with complete rearrnagement. Here n is the maximum number of nodes to be connected. In addition, a simple, polynomial time is present that has worst-case performance within two times this bound. In the rearrangeable case, a polynomial time algorithm is presented with worst-case performance bounded by a constant time optimum.
An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. The algorithm runs in O(pn) time, wh...
详细信息
An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. The algorithm runs in O(pn) time, where n is the number of vertices in G, and p is the minimum cardinality of a subset of the faces that cover all vertices, taken over all planar embeddings of G. The algorithm is based on a decomposition of the graph into O(pn) outerplanar subgraphs satisfying certain separator properties. Linear-time algorithms are presented for various subproblems including that of finding an appropriate embedding of G and a corresponding face-on-vertex covering of cardinality O(p), and of generating all pairs shortest path information in a directed outerplanar graph.
暂无评论