We investigate the problem of computing a minimal-volume container for the non-overlapping packing of a given set of three-dimensional convex objects. Already the simplest versions of the problem are 𝒩 ⻝...
详细信息
We investigate the problem of computing a minimal-volume container for the non-overlapping packing of a given set of three-dimensional convex objects. Already the simplest versions of the problem are 𝒩 𝒫 -hard so that we cannot expect to find polynomial time algorithms to determine the exact solution. We give constant ratio approximation algorithms for packing axis-parallel (rectangular) cuboids under translation into an axis-parallel (rectangular) cuboid as container, for packing cuboids under rigid motions into an axis-parallel cuboid or into an arbitrary convex container, and for packing convex polyhedra under rigid motions into an axis-parallel cuboid or arbitrary convex container. This work gives the first approximability results for the computation of minimum volume containers for the objects described.
The two-server problem is concerned with the movement of two servers to request points in a metric space. We consider an offline version of the problem in a graph in which the requests may be served in any order. A fa...
详细信息
The two-server problem is concerned with the movement of two servers to request points in a metric space. We consider an offline version of the problem in a graph in which the requests may be served in any order. A family of approximations algorithms is developed for this NP-complete problem.
We investigate the two and three dimensional bin packing problems, i.e., packing a list of rectangles (boxes) into unit square (cube) bins so that the number of bins used is a minimum. A simple on-line packing algorit...
详细信息
We investigate the two and three dimensional bin packing problems, i.e., packing a list of rectangles (boxes) into unit square (cube) bins so that the number of bins used is a minimum. A simple on-line packing algorithm for the one dimensional bin packing problem, the First-Fit algorithm, is generalized to two and three dimensions. We first give an algorithm for the two dimensional case and show that its asymptotic worse case performance ratio is . The algorithm is then generalized to the three dimensional case and its performance ratio . The second algorithm takes a parameter and we prove that by choosing the parameter properly, it has an asymptotic worst case performance bound which can be made as close as desired to 1.7 2 =2.89 and 1.7 3 =4.913 respectively in two and three dimensions.
A two-agent scheduling problem on parallel machines is considered in this paper. Our objective is to minimize the makespan for agent A, subject to an upper bound on the makespan for agent B. In this paper, we provide ...
详细信息
A two-agent scheduling problem on parallel machines is considered in this paper. Our objective is to minimize the makespan for agent A, subject to an upper bound on the makespan for agent B. In this paper, we provide a new approximation algorithm called CLPT. On the one hand, we compare the performance between the CLPT algorithm and the optimal solution and find that the solution obtained by the CLPT algorithm is very close to the optimal solution. On the other hand, we design different experimental frameworks to compare the CLPT algorithm and the A-LS algorithm for a comprehensive performance evaluation. A large number of numerical simulation results show that the CLPT algorithm outperformed the A-LS algorithm.
A dominating set of a graph is a subset of vertices such that every vertex not in the subset has at least one neighbor within the subset. The corresponding optimization problem is known to be NP-hard. It is proved to ...
详细信息
A dominating set of a graph is a subset of vertices such that every vertex not in the subset has at least one neighbor within the subset. The corresponding optimization problem is known to be NP-hard. It is proved to be beneficial to separate the solution process in two stages. First, one can apply a fast greedy algorithm to obtain an initial dominating set and then use an iterative procedure to purify (reduce) the size of this dominating set. In this work, we develop the purification stage and propose new purification algorithms. The purification procedures that we present here outperform, in practice, the earlier known purification procedure. We have tested our algorithms for over 1300 benchmark problem instances. Compared to the estimations due to known upper bounds, the obtained solutions are about seven times better. Remarkably, for the 500 benchmark instances for which the optimum is known, the optimal solutions are obtained for 46.33% of the tested instances, whereas the average error for the remaining instances is about 1.01.
In this paper we consider the k-bounded space on-line bin packing problem. Some efficient approximation algorithms are described and analyzed. Selecting either the smallest or the largest available bin size to start a...
详细信息
In this paper we consider the k-bounded space on-line bin packing problem. Some efficient approximation algorithms are described and analyzed. Selecting either the smallest or the largest available bin size to start a new bin as items arrive turns out to yield a worst-case performance bound of 2. By packing large items into appropriate bins, an efficient approximation algorithm is derived from k-bounded space on-line bin packing algorithms and its worst-case performance bounds is 1.7 for k ≥ 3.
The constrained shortest path (CSP) problem requires the determination of a minimum costs-tpath with delay at most a nonzero *** this paper, we first point out the equivalence of certain algorithms, simply called the ...
详细信息
The constrained shortest path (CSP) problem requires the determination of a minimum costs-tpath with delay at most a nonzero *** this paper, we first point out the equivalence of certain algorithms, simply called the LARAC (Lagrangian Relaxation Based Aggregated Cost) algorithm presented independently in some earlier works. The LARAC algorithm solves the integer relaxation of the CSP problem (RELAX-CSP) and is based on a geometric approach. We then present an algebraic study of RELAX-CSP and establish several new properties of the optimal solution. These properties also hold for a class of combinatorial optimization problems involving two additive parameters. We follow this by establishing a characterization of optimal solutions for the general CSP problem involving more than two additive parameters. We present a new heuristic called LARAC-BIN based on binary search. This heuristic involves a parameter whose value can be specified in advance depending on the allowable deviation of the cost from the optimum. Using Megiddo's parametric search, we also present a strongly polynomial time algorithm for RELAX-CSP. This algorithm has the best complexity to date for RELAX-CSP. Finally, we present an integrated approach to the CSP problem and show how the LARAC algorithm can be used to achieve considerable speedup of ϵ-approximation algorithms for the CSP problem.
Covering array (CA) on a hypergraph H is a combinatorial object used in interaction testing of a complex system modeled as H. Given a t-uniform hypergraph H and positive integer s, it is an array with a column for eac...
详细信息
Covering array (CA) on a hypergraph H is a combinatorial object used in interaction testing of a complex system modeled as H. Given a t-uniform hypergraph H and positive integer s, it is an array with a column for each vertex having entries from a finite set of cardinality s, such as Z(s), and the property that any set of t columns that correspond to vertices in a hyperedge covers all s(t) ordered t-tuples from Z(s)(t) at least once as a row. Minimizing the number of rows (size) of CA is important in industrial applications. Given a hypergraph H, a CA on H with the minimum size is called optimal. Determining the minimum size of CA on a hypergraph is NP-hard. We focus on constructions that make optimal covering arrays on large hypergraphs from smaller ones and discuss the construction method for optimal CA on the Cartesian product of a Cayley hypergraph with different families of hypergraphs. For a prime power q > 2, we present a polynomial-time approximation algorithm with approximation ratio ([log(q) (vertical bar V vertical bar/3(k-1))])(2) for constructing covering array CA(n, H, q) on 3-uniform hypergraph H = (V, E) with k > 1 prime factors with respect to the Cartesian product.
We study approximation bounds for the semidefinite programming (SDP) relaxation of quadratically constrained quadratic optimization: min f(0)(x) subject to f(k)(x) less than or equal to 0, k = 1,..., m, where f(k)(x) ...
详细信息
We study approximation bounds for the semidefinite programming (SDP) relaxation of quadratically constrained quadratic optimization: min f(0)(x) subject to f(k)(x) less than or equal to 0, k = 1,..., m, where f(k)(x) = x(T)A(k)x + (b(k))(T) x + c(k). In the special case of ellipsoid constraints with interior feasible solution at 0, we show that the SDP relaxation, coupled with a rank-1 decomposition result of Sturm and Zhang [ Math. Oper. Res., to appear], yields a feasible solution of the original problem with objective value at most (1 - gamma)(2)/(rootm + gamma)(2) times the optimal objective value, where gamma = rootmax(k) f(k)(0) + 1. For the single trust-region problem corresponding to m = 1, this yields an exact optimal solution. In the general case, we extend some bounds derived by Nesterov [Optim. Methods Softw., 9 (1998), pp. 141 - 160;working paper, CORE, Universite Catholique de Louvain, Louvain-la-Neuve, Belgium, 1998], Ye [Math. Program., 84 (1999), pp. 219 - 226], and Nesterov, Wolkowicz, and Ye [in Handbook of Semidefinite Programming, H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Kluwer Academic Publishers, Dordrecht, The Netherlands, 2000, pp. 360 - 419] for the special case where A(k) is diagonal and b(k) = 0 for k = 1,..., m. We also discuss the generation of approximate solutions with high probability.
A hybrid two-stage flowshop scheduling problem was considered which involves m identical parallel machines at Stage 1 and a burn-in processor M at Stage 2, and the makespan was taken as the minimization objective. Thi...
详细信息
A hybrid two-stage flowshop scheduling problem was considered which involves m identical parallel machines at Stage 1 and a burn-in processor M at Stage 2, and the makespan was taken as the minimization objective. This scheduling problem is NP-hard in general. We divide it into eight subcases. Except for the following two subcases： （1） b≥ an, max{m, B} 〈 n; （2） a1 ≤ b ≤ an, m ≤ B 〈 n, for all other subcases, their NP-hardness was proved or pointed out, corresponding approximation algorithms were conducted and their worst-case performances were estimated. In all these approximation algorithms, the Multifit and PTAS algorithms were respectively used, as the jobs were scheduled in m identical parallel machines.
暂无评论