We consider the discrete version of the well-known time-cost tradeoff problem for project networks, which has been extensively studied in the project management literature, We prove a strong in-approximability result ...
详细信息
We consider the discrete version of the well-known time-cost tradeoff problem for project networks, which has been extensively studied in the project management literature, We prove a strong in-approximability result with respect to polynomial time bicriteria approximation algorithms for this problem. (C) 2002 Elsevier Science B.V. All rights reserved.
This paper presents an approximation algorithm for simultaneously constructing a rectilinear Steiner tree and buffer insertion points into the tree. The objective of the algorithm is to divide each wire into multiple ...
详细信息
This paper presents an approximation algorithm for simultaneously constructing a rectilinear Steiner tree and buffer insertion points into the tree. The objective of the algorithm is to divide each wire into multiple smaller segments and minimize the number of the buffer insertion points (Steiner points) which are only located at the end of each segment. We show that (a) the Steiner ratio is 1/3, that is, the rectilinear minimum spanning tree yields a polynomial-time approximation with a performance ratio exactly 3;(b) there exists a polynomial-time approximation with a performance ratio 2. (C) 2001 Elsevier Science B.V. All rights reserved.
In this paper we consider the natural generalizations of two fundamental problems, the Set-Cover problem and the Min-Knapsack problem. We are given a hypergraph, each vertex of which has a nonnegative weight, and each...
详细信息
In this paper we consider the natural generalizations of two fundamental problems, the Set-Cover problem and the Min-Knapsack problem. We are given a hypergraph, each vertex of which has a nonnegative weight, and each edge of which has a nonnegative length. For a given threshold (l) over cap, our objective is to find a subset of the vertices with minimum total cost, such that at least a Length of (l) over cap of the edges is covered. This problem is called the partial set cover problem. We present an O(\V\(2) + \H\)-time. Delta (E)-approximation algorithm for this problem, where Delta (E) greater than or equal to 2 is an upper bound on the edge cardinality of the hypergraph and \H\ is the size of the hypergraph (i.e., the sum of all its edges cardinalities). The special case where Delta (E) = 2 is called the partial vertex cover problem. For this problem a 2-approximation was previously known, however, the time complexity of our solution, i.e., O(\V\(2)), is a dramatic improvement. We show that if the weights are homogeneous (i.e., proportional to the potential coverage of the sets) then any minimal cover is a good approximation. Now, using the local-ratio technique, it is sufficient to repeatedly subtract a homogeneous weight function from the given weight function. (C) 2001 Academic Press.
We study bottleneck constrained network upgrading problems. We are given an edge weighted graph G = (V,E) where node nu is an element of V can be upgraded at a cost of c(nu). This upgrade reduces the delay of each lin...
详细信息
We study bottleneck constrained network upgrading problems. We are given an edge weighted graph G = (V,E) where node nu is an element of V can be upgraded at a cost of c(nu). This upgrade reduces the delay of each link emanating from nu. The goal is to find a minimum cost set of nodes to be upgraded so that the resulting network has a good performance. The performance is measured by the bottleneck weight of a constrained forest defined by a proper function (Goemans and Williamson, SIAM J. Comput. 24 (1995) 296-317). These problems are a generalization of the node weighted constrained forest problems studied by Klein and Ravi (J. algorithms 19 (1995) 104-115). The main result of the paper is a polynomial-time approximation algorithm for this problem with performance guarantee of 2 ln(roote/2.\K\), where K:={nu: f({v}) = 1} is the set of terminals given by the proper function f. We also prove that the performance bound is tight up to small constant factors by providing a lower bound of In \K\. Our results are obtained by extending the elegant solution based decomposition technique of (Klein and Ravi, J. algorithms 19 (1995) 104-115) for approximating node weighted constrained forest problems. These results obtained extend those in (Klein and Ravi, J. algorithms 19 (1995) 104-115, Krumke et al., Lecture Notes in Comput. Sci., Vol. 1197, 1996, pp. 293-307). (C) 2001 Elsevier Science B.V. All rights reserved.
Random costs C(i, j) are assigned to the area of a complete directed graph on n labeled vertices. Given the cost matrix C-n = (C(i, j)), let T-k* = T-k*(C-n) be the spanning tree that has minimum cost among spanning t...
详细信息
Random costs C(i, j) are assigned to the area of a complete directed graph on n labeled vertices. Given the cost matrix C-n = (C(i, j)), let T-k* = T-k*(C-n) be the spanning tree that has minimum cost among spanning trees with in-degree less than or equal to k. Since it is NP-hard to find T-k(*) We instead consider an efficient algorithm that finds a near-optimal spanning tree T-k(a). If the edge costs are independent, with a common exponential(1) distribution, then, as n --> infinity, E(Cost(T-k(a))) = E(Cost(T-k(*))) + o(1). Upper and lower bounds for E(Cost(Tk*)) are also obtained for k greater than or equal to 2.
Given a bounded integer program with n variables and rn constraints, each with two variables, we present an O (mU) time and O (m) space feasibility algorithm, where U is the maximal variable range size. We show that w...
详细信息
Given a bounded integer program with n variables and rn constraints, each with two variables, we present an O (mU) time and O (m) space feasibility algorithm, where U is the maximal variable range size. We show that with the same complexity we can find an optimal solution for the positively weighted minimization problem for monotone systems. Using the local-ratio technique we develop an O (nmU) time and O(m) space 2-approximation algorithm for the positively weighted minimization problem fur the general case. We further generalize all results to nonlinear constraints (called axis-convex constraints) and to nonlinear (but monotone) weight functions. Our algorithms are not only better in complexity than other known algorithms, but also considerably simpler, and they contribute to the understanding of these very fundamental problems.
A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve n the vertical direction and no two edges cross. An undirected graph is rectilinear planar if ...
详细信息
A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve n the vertical direction and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems n the effective visualization of various graph and network structures. For example, upward planarity is useful for the display of order diagrams and subroutine-call graphs, while rectilinear planarity is useful for the display of circuit schematics and entity-relationship diagrams. We show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it is NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an O(n(1-epsilon)) error for any epsilon > 0.
For an edge weighted undirected graph G and an integer k > 2, a k-way cut is a set of edges whose removal leaves G with at least k components. We propose a simple approximation algorithm to the minimum k-way cut pr...
详细信息
For an edge weighted undirected graph G and an integer k > 2, a k-way cut is a set of edges whose removal leaves G with at least k components. We propose a simple approximation algorithm to the minimum k-way cut problem. It computes a nearly optimal k-way cut by using a set of minimum 3-way cuts. We show that the performance ratio of our algorithm is 2 - 3/k for an odd k and 2 - (3k - 4)/(k(2) - k) for an even k. The running time is O(kmn(3) log(n(2)/m)) where n and m are the numbers of vertices and edges respectively.
We consider the preemptive job shop scheduling problem with two machines, with the objective to minimize the makespan. We present an algorithm that finds a schedule of length at most P-max/12 greater than the optimal ...
详细信息
We consider the preemptive job shop scheduling problem with two machines, with the objective to minimize the makespan. We present an algorithm that finds a schedule of length at most P-max/12 greater than the optimal schedule length, where P-max is the length of the longest job.
It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P not equal NP....
详细信息
It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P not equal NP. However, this result holds only if the instance of the problem contains jobs consisting of at least three operations. This paper considers the open shop scheduling problem, provided that each job consists of at most two operations, one of which is to be processed on one of the m greater than or equal to 2 machines, while the other operation must be performed on the bottleneck machine, the same for all jobs. For this NP-hard problem we present a heuristic algorithm and show that its worst-case performance ratio is 5/4. (C) 2001 Elsevier Science B.V. All rights reserved.
暂无评论