The THTMTP (two-level hierarchical time minimization transportation problem) is an important problem arising in industries. In literature, there are only two approaches with shortcomings to solve the problem. In this ...
详细信息
The THTMTP (two-level hierarchical time minimization transportation problem) is an important problem arising in industries. In literature, there are only two approaches with shortcomings to solve the problem. In this paper, the THTMTP is formulated as a mathematical model applicable to the case in which the total available supply at the sources is no less than the total demand at the destinations. A feasible flow-based iterative algorithm named THTMTP-A is proposed to solve the THTMTP by constructing network with lower and upper arc capacities. It is proved that the THTMTP-A algorithm can find the optimal solution to the THTMTP in a polynomial time. The proposed THTMTP-A algorithm has good performance in terms of computer implementation, computational time and required memory for computation, and hence overcomes successfully the shortcomings of the two existing approaches. Computational experiments validate that the THTMTP-A algorithm is an efficient and robust method to solve the THTMTP, and can serve as efficient tool to solve other related optimization problems. (C) 2017 Elsevier Ltd. All rights reserved.
The MAX-MIN dispersion problem, which arises in the placement of undesirable facilities, involves selecting a specified number of sites among a set of potential sites so as to maximize the minimum distance between any...
详细信息
The MAX-MIN dispersion problem, which arises in the placement of undesirable facilities, involves selecting a specified number of sites among a set of potential sites so as to maximize the minimum distance between any pair of selected sites. We consider different versions of this dispersion problem where each potential site has an associated storage capacity and a storage cost. A typical problem in this context is to choose a subset of potential sites so that the total capacity of the chosen sites is at least a given value, the total storage cost is within the specified budget and the minimum distance between any pair of chosen sites is maximized. Since these constrained optimization problems are NP-hard in general, we consider whether there are efficient approximation algorithms for them with good performance guarantees. Our results include approximation algorithms for some versions, approximation schemes for some geometric versions and polynomial algorithms for special cases. We also present results that bring out the intrinsic difficulty of obtaining near-optimal solutions to some versions.
For a given undirected graph G = (V, E, c(G)) with edges weighted by nonnegative reals c(G): E --> R+, let Lambda(G)(k) stand for the minimum amount of weights which needs to be added to make G k-edge-connected, an...
详细信息
For a given undirected graph G = (V, E, c(G)) with edges weighted by nonnegative reals c(G): E --> R+, let Lambda(G)(k) stand for the minimum amount of weights which needs to be added to make G k-edge-connected, and let G*(k) be the resulting graph obtained from G. This paper first shows that function Lambda(G) over the entire range k is an element of [0, + infinity] can be computed in O(nm + n(2) log n) time, and then shows that all G*(k) in the entire range can be obtained from O(n log n) weighted cycles, and such cycles can be computed in O(nm + n(2) log n) time, where n and m are the numbers of vertices and edges, respectively. (C) 1999 Academic Press.
This paper presents a scaling scheme for submodular functions. A small but strictly submodular function is added before scaling so that the resulting functions should be submodular. This scaling scheme leads to a weak...
详细信息
This paper presents a scaling scheme for submodular functions. A small but strictly submodular function is added before scaling so that the resulting functions should be submodular. This scaling scheme leads to a weakly polynomial algorithm to solve minimum cost integral submodular flow problems with separable convex cost functions, provided that an oracle for exchange capacities is available.
We study the following problem: for given integers d, k and graph G, can we obtain a graph with diameter d via at most k edge deletions? We determine the computational complexity of this and related problems for diffe...
详细信息
We study the following problem: for given integers d, k and graph G, can we obtain a graph with diameter d via at most k edge deletions? We determine the computational complexity of this and related problems for different values of d. (C) 2021 Elsevier B.V. All rights reserved.
We survey recent results on the computational complexity of mixed shop scheduling problems. In a mixed shop, some jobs have fixed machine orders (as in the job shop), while the operations of the other jobs may be proc...
详细信息
We survey recent results on the computational complexity of mixed shop scheduling problems. In a mixed shop, some jobs have fixed machine orders (as in the job shop), while the operations of the other jobs may be processed in arbitrary order (as in the open shop). The main attention is devoted to establishing the boundary between polynomially solvable and NP-hard problems. When the number of operations per job is unlimited, we focus on problems with a lived number of jobs. (C) 2000 Elsevier Science B.V. All rights reserved.
Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between per...
详细信息
Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapezoids are lines) and cocomparability graphs (the complement has a transitive orientation). The operation of "vertex splitting", introduced in (Cheah and Corneil, 1996) [3], first augments a given graph G and then transforms the augmented graph by replacing each of the original graph's vertices by a pair of new vertices. This "splitted graph" is a permutation graph with special properties if and only if G is a trapezoid graph. Recently vertex splitting has been used to show that the recognition problems for both tolerance and bounded tolerance graphs is NP-complete (Mertzios et al., 2010) [11]. Unfortunately, the vertex splitting trapezoid graph recognition algorithm presented in (Cheah and Corneil, 1996) [3] is not correct. In this paper, we present a new way of augmenting the given graph and using vertex splitting such that the resulting algorithm is simpler and faster than the one reported in (Cheah and Corneil, 1996)[3]. (C) 2011 Elsevier B.V. All rights reserved.
We consider a generalization of the uncapacitated facility location problem, where the setup cost for a facility and the price charged for service may depend on the number of customers patronizing the facility. Custom...
详细信息
We consider a generalization of the uncapacitated facility location problem, where the setup cost for a facility and the price charged for service may depend on the number of customers patronizing the facility. Customers are represented by the nodes of the transportation network, and facilities can be located only at nodes;a customer selects a facility to patronize so as to minimize his (her) expenses (price for service + the part of transportation costs paid by the customer). We assume that transportation costs are paid partially by the service company and partially by customers. The objective is to choose locations for facilities and balanced prices so as to either minimize the expenses of the service company (the sum of the total setup cost and the total part of transportation costs paid by the company), or to maximize the total profit. A polynomial-time dynamic programming algorithm for the problem on a tree network is developed. (c) 2006 Elsevier B.V. All rights reserved.
In this paper, we consider a collision detection problem of spheres which asks to detect all pairs of colliding spheres in a set of n spheres located in d-dimensional space. We propose a collision detection algorithm ...
详细信息
In this paper, we consider a collision detection problem of spheres which asks to detect all pairs of colliding spheres in a set of n spheres located in d-dimensional space. We propose a collision detection algorithm for spheres based on slab partitioning technique and a plane sweep method. We derive a theoretical upper bound on the time complexity of the algorithm. Our bound tells that if both the dimension and the maximum ratio of radii of two spheres are bounded. then our algorithm runs in O(n log n + K) time with O(n + K) space, where K denotes the number of pairs of colliding spheres.
We consider the two machine flow shop and open shop problems to minimize the weighted mean flow-time, processing times being equal to 0 or 1. The solution to the open shop problem is based on algorithms for the flow s...
详细信息
We consider the two machine flow shop and open shop problems to minimize the weighted mean flow-time, processing times being equal to 0 or 1. The solution to the open shop problem is based on algorithms for the flow shop problem and the corresponding two parallel identical machine problem. For all problems O(n log n) algorithms are proposed. (C) 1998 Elsevier Science B.V. All rights reserved.
暂无评论