The Frobenius problem is to find a method (= algorithm) for calculating the largest "sum of money" that cannot be given by coins whose values b(0), b(1),..., b(w). are coprime integers. As admissible solutio...
详细信息
The Frobenius problem is to find a method (= algorithm) for calculating the largest "sum of money" that cannot be given by coins whose values b(0), b(1),..., b(w). are coprime integers. As admissible solutions (algorithms), it is common practice to study polynomial algorithms, which owe their name to the form of the dependence of time expenditure on the length of the original information. The difficulty of the Frobenius problem is apparent from the fact that already for w = 3 the existence of a polynomial solution is still an open problem. In the present paper, we distinguish some classes of input data for which the problem can be solved polynomially;nevertheless, argumentation in the spirit of complexity theory of algorithms is kept to a minimum.
Jobs are processed by a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a mach...
详细信息
Jobs are processed by a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time common for all batches. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource, which may be different from that for the jobs. polynomial time algorithms are presented to find an optimal batch sequence and resource values such that either the total weighted resource consumption is minimized, subject to meeting job deadlines, or the maximum job lateness is minimized, subject to an upper bound on the total weighted resource consumption. The algorithms are based on linear programming formulations of the corresponding problems. (C) 2001 Elsevier Science B.V. All rights reserved.
A vertex v in a graph G is called alpha -redundant if alpha (G - v) = alpha (C), where alpha (G) stands for the stability number of G, i.e. the maximum size of a subset of pairwise nonadjacent vertices. We describe su...
详细信息
A vertex v in a graph G is called alpha -redundant if alpha (G - v) = alpha (C), where alpha (G) stands for the stability number of G, i.e. the maximum size of a subset of pairwise nonadjacent vertices. We describe sufficient conditions for a vertex to be alpha -redundant in terms of some P-4 extensions. This leads to polynomial-time algorithms fur solving the stable set problem giving for an arbitrary input graph either the solution of the problem or a forbidden configuration such as an induced P-5 or an induced banner in the input graph. The algorithms extend and improve a number of previous results on the problem. (C) 2001 Elsevier Science B.V. All rights reserved.
We consider the problem of scheduling independent jobs on two machines in an open shop, a job shop and a flow shop environment. Both machines are batching machines, which means that several operations can be combined ...
详细信息
We consider the problem of scheduling independent jobs on two machines in an open shop, a job shop and a flow shop environment. Both machines are batching machines, which means that several operations can be combined into a batch and processed simultaneously on a machine. The batch processing time is the maximum processing time of operations in the batch, and all operations in a batch complete at the same time. Such a situation may occur, for instance, during the final testing stage of circuit board manufacturing, where burn-in operations are performed in ovens. We consider cases in which there is no restriction on the size of a batch on a machine, and in which a machine can process only a bounded number of operations in one batch. For most of the possible combinations of restrictions, we establish the complexity status of the problem. Copyright (C) 2001 John Wiley & Sons, Ltd.
We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of In elements with uncertainty in weights of the elements. We present a polynomial algorithm wi...
详细信息
We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of In elements with uncertainty in weights of the elements. We present a polynomial algorithm with the order of complexity O((min {p, m - p})(2) m) for the case where uncertainty is represented by means of interval estimates for the weights. We show that the problem is NP-hard in the case of an arbitrary finite set of possible scenarios, even if there are only two possible scenarios. This is the first known example of a robust combinatorial optimization problem that is NP-hard in the case of scenario-represented uncertainty bur is polynomially solvable in the case of the interval representation of uncertainty.
The uncapacitated facility location problem is considered in case when the transportation matrix has a totally balanced characteristic matrix. Since this problem is equivalent to the minimization problem of a polynomi...
详细信息
The uncapacitated facility location problem is considered in case when the transportation matrix has a totally balanced characteristic matrix. Since this problem is equivalent to the minimization problem of a polynomial in Boolean variables, an efficient algorithm is developed in terms of the latter. The idea of the algorithm is based on the fact that the minimization problem of a totally balanced polynomial can be reduced to the minimization problem of a similar polynomial having one fewer variables. (C) 2001 Published by Elsevier Science B.V.
作者：
Plesník, JComenius Univ
Fac Math Phys & Informat Dept Numer & Optimizat Methods Bratislava 84248 Slovakia
Given a graph G with nonnegative edge costs and an integer k, we consider the problem of finding an edge subset S of minimum total cost with respect to the constraint that S covers exactly k vertices of G. An O(n(3)) ...
详细信息
Given a graph G with nonnegative edge costs and an integer k, we consider the problem of finding an edge subset S of minimum total cost with respect to the constraint that S covers exactly k vertices of G. An O(n(3)) algorithm is presented where n is the order of G. It is based on the author's previous paper dealing with a similar problem asking S to cover at least k vertices.
In this paper we consider how to increase the capacities of the elements in a set E efficiently so that the capacity of a given family F of subsets of E can be increased to the maximum extent while the total cost for ...
详细信息
In this paper we consider how to increase the capacities of the elements in a set E efficiently so that the capacity of a given family F of subsets of E can be increased to the maximum extent while the total cost for the increment of capacity is within a given budget bound. We transform this problem into finding the minimum weight element of F when the weight of each element of E is a linear function of a single parameter and propose an algorithm for solving this problem. We further discuss the problem for some special cases. Especially, when E is the edge set of a network and the family F consists of all spanning trees, we give a strongly polynomial algorithm.
We consider the problem (minimum spanning strong subdigraph (MSSS)) of finding the minimum number of arcs in a spanning strongly connected subdigraph of a strongly connected digraph. This problem is NP-hard for genera...
详细信息
We consider the problem (minimum spanning strong subdigraph (MSSS)) of finding the minimum number of arcs in a spanning strongly connected subdigraph of a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamiltonian cycle problem. We characterize the number of arcs in a minimum spanning strong subdigraph for digraphs which are either extended semicomplete or semicomplete bipartite. Our proofs lead to polynomial algorithms for finding an optimal subdigraph for every digraph from each of these classes. Our proofs are based on a number of results (some of which are new and interesting in their own right) on the structure of cycles and paths in these graphs. Recently, it was shown that the Hamiltonian cycle problem is polynomially solvable for semicomplete multipartite digraphs, a superclass of the two classes above [15]. We conjecture that the MSSS problem is also polynomial for this class of digraphs. (C) 2001 Academic Press.
In the ring loading problem, traffic. demands are given for each pair of nodes in an undirected ring network and a flow is routed in either of two directions, clockwise and counterclockwise. The load of an edge is the...
详细信息
In the ring loading problem, traffic. demands are given for each pair of nodes in an undirected ring network and a flow is routed in either of two directions, clockwise and counterclockwise. The load of an edge is the sum of the flows routed through the edge and the objective of the problem is to minimize the maximum load on the ring. Myung [J. Korean OR and MS Society, 23 (1998), pp. 49-62 (in Korean)] has presented an efficient algorithm for solving a problem where flow is restricted to integers. However, the proof for the validity of the algorithm in their paper is long and complicated and as the paper is written in Korean, its accessibility is very limited. In this paper, we slightly modify their algorithm and provide a simple proof for the correctness of the proposed algorithm.
暂无评论