Latency of information propagating in wireless network is gaining more and more attention recently. This paper studies the problem of t-Latency Bounded Information Propagation (t-LBIP) problem in wireless networks whi...
详细信息
Latency of information propagating in wireless network is gaining more and more attention recently. This paper studies the problem of t-Latency Bounded Information Propagation (t-LBIP) problem in wireless networks which are represented by unit-disk graphs. So far, no guaranteed approximation algorithm has been achieved for t-LBIP when ta parts per thousand yen2. In this paper, we propose a polynomial time approximation scheme for t-LBIP under the condition that the maximum degree is bounded by a constant.
We study the scheduling problem with a common due date on two parallel identical machines and the total early work criterion. The problem is known to be NP-hard. We prove a few dominance properties of optimal solution...
详细信息
We study the scheduling problem with a common due date on two parallel identical machines and the total early work criterion. The problem is known to be NP-hard. We prove a few dominance properties of optimal solutions of this problem. Their proposal was inspired by the results of some auxiliary computational experiments. Test were performed with the dynamic programming algorithm and list algorithms. Then, we propose the polynomial time approximation scheme, based on structuring problem input. Moreover, we discuss the relationship between the early work criterion and the related late work criterion. We compare the computational complexity and approximability of scheduling problems with both mentioned objective functions.
We consider the classic setting of Capacitated Vehicle Routing Problem (CVRP): single product, single depot, demands of all customers are identical. It is known that this problem remains strongly NP-hard even being fo...
详细信息
ISBN:
(纸本)9783319266268;9783319266251
We consider the classic setting of Capacitated Vehicle Routing Problem (CVRP): single product, single depot, demands of all customers are identical. It is known that this problem remains strongly NP-hard even being formulated in Euclidean spaces of fixed dimension. Although the problem is intractable, it can be approximated well in such a special case. For instance, in the Euclidean plane, the problem (and it's several modifications) have polynomial time approximation schemes (PTAS). We propose polynomial time approximation scheme for the case of R-3.
Recently, there hav been considerable interests in the multiprocessor job scheduling problem, in which a job can be processed in parallel on one of several alternative subsets of processors. In this paper, a polynomia...
详细信息
Recently, there hav been considerable interests in the multiprocessor job scheduling problem, in which a job can be processed in parallel on one of several alternative subsets of processors. In this paper, a polynomial time approximation scheme is presented for the problem in which the number of processors in the system is a fixed constant. This result is the best possible because of the strong NP-hardness of the problem and is a significant improvement over the past results: the best previous result was an approximation algorithm of ratio 7/6 + epsilon for 3-processor systems based on Goemans's algorithm for a restricted version of the problem.
The multiple knapsack problem (MKP) is a natural and well-known generalization of the single knapsack problem and is defined as follows. We are given a set of n items and m bins ( knapsacks) such that each item i has ...
详细信息
The multiple knapsack problem (MKP) is a natural and well-known generalization of the single knapsack problem and is defined as follows. We are given a set of n items and m bins ( knapsacks) such that each item i has a profit p( i) and a size s( i), and each bin j has a capacity c( j). The goal is to find a subset of items of maximum profit such that they have a feasible packing in the bins. MKP is a special case of the generalized assignment problem ( GAP) where the profit and the size of an item can vary based on the specific bin that it is assigned to. GAP is APX-hard and a 2-approximation, for it is implicit in the work of Shmoys and Tardos [ Math. Program. A, 62 ( 1993), pp. 461 - 474], and thus far, this was also the best known approximation for MKP. The main result of this paper is a polynomial time approximation scheme (PTAS) for MKP. Apart from its inherent theoretical interest as a common generalization of the well-studied knapsack and bin packing problems, it appears to be the strongest special case of GAP that is not APX-hard. We substantiate this by showing that slight generalizations of MKP are APX-hard. Thus our results help demarcate the boundary at which instances of GAP become APX-hard. An interesting aspect of our approach is a PTAS-preserving reduction from an arbitrary instance of MKP to an instance with O(log n) distinct sizes and profits.
The problem of Minimum Congestion Hypergraph Embedding in a Weighted Cycle (MCHEWC) is to embed the hyperedges of a hypergraph as paths in a weighted cycle such that the maximum congestion is minimized. This problem i...
详细信息
The problem of Minimum Congestion Hypergraph Embedding in a Weighted Cycle (MCHEWC) is to embed the hyperedges of a hypergraph as paths in a weighted cycle such that the maximum congestion is minimized. This problem is NP-hard. In this paper, we present a polynomial time approximation scheme (PTAS) for this problem. (C) 2011 Elsevier B.V. All rights reserved.
The objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect n given highways under the constraint that the roads can intersect each highway only at one point in ...
详细信息
The objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect n given highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a polynomial time approximation scheme for this problem by applying Arora's framework (Arora, 1998;also available from http:***/arora). For every fixed c > 1 and given any n line segments in the plane, a randomized version of the scheme finds a (1+1/c)-approximation to the optimal cost in O(n(O)(c)log(n) time.
In this paper we investigate the two-stage multiprocessor flow shop scheduling problem F2(P)\ . \C-max, where the numbers m(1) and m(2) of machines available in the two stages are part of the input. We demonstrate the...
详细信息
In this paper we investigate the two-stage multiprocessor flow shop scheduling problem F2(P)\ . \C-max, where the numbers m(1) and m(2) of machines available in the two stages are part of the input. We demonstrate the existence of a polynomial time approximation scheme for this problem. This result solves the simplest case of an open problem that has been posed by Leslie Hall in a recent paper (Hall, 1995). hn extension of our algorithm yields an approximationscheme for the closely related two-stage multiprocessor job shop problem. (C) 2000 Elsevier Science B.V. All rights reserved.
We consider the classic single-depot single-product uniform customer demands setting of Capacitated Vehicle Routing Problem（CVRP）.It is known that this problem remains strongly NP-hard even being formulated in Eucli...
详细信息
We consider the classic single-depot single-product uniform customer demands setting of Capacitated Vehicle Routing Problem（CVRP）.It is known that this problem remains strongly NP-hard even being formulated in Euclidean spaces of fixed *** the problem is intractable,it can be approximated well in such a special *** instance,in the Euclidean plane,the problem（and it's several modifications） have polynomial time approximation schemes（PTAS）.We propose polynomial time approximation scheme for the case of R.
The problem of Minimum Congestion Hypergraph Embedding in a Weighted Cycle (MCHEWC) is to embed the hyperedges of a hypergraph as paths in a weighted cycle such that the maximum congestion, i.e. the maximum product of...
详细信息
ISBN:
(纸本)9783642145520
The problem of Minimum Congestion Hypergraph Embedding in a Weighted Cycle (MCHEWC) is to embed the hyperedges of a hypergraph as paths in a weighted cycle such that the maximum congestion, i.e. the maximum product of the weight of an edge and the number of times that the edge is passed by the embedding, is minimized. It is known that the problem, the same as the unweighted case, is NP-hard. The aim of this paper is to present a polynomial time approximation scheme (PTAS) for the problem.
暂无评论