We give a polynomial-time algorithm for finding a solution to the Traveling Salesman Problem when the points given are constrained to lie on a fixed set of smooth curves of finite length. (C) 2007 John Wiley & Son...
详细信息
We give a polynomial-time algorithm for finding a solution to the Traveling Salesman Problem when the points given are constrained to lie on a fixed set of smooth curves of finite length. (C) 2007 John Wiley & Sons, Inc.
In this paper, we study undirected multiple graphs of any natural multiplicity k > 1. There are edges of three types: ordinary edges, multiple edges, and multiedges. Each edge of the last two types is a union of k ...
详细信息
In this paper, we study undirected multiple graphs of any natural multiplicity k > 1. There are edges of three types: ordinary edges, multiple edges, and multiedges. Each edge of the last two types is a union of k linked edges, which connect 2 or (k + 1) vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can also be incident to other multiple edges and it can be the common end of k linked edges of some multiedge. If a vertex is the common end of some multiedge, it cannot be the common end of another multiedge. Divisible multiple graphs are characterized by the possibility to divide the graph into k parts, which are adjusted on the linked edges and which have no common edges. Each part is an ordinary graph. As for an ordinary graph, we can define the integer function of the length of an edge for a multiple graph and set the problem of the shortest path joining two vertices. Any multiple path is a union of k ordinary paths, which are adjusted on the linked edges of all multiple and multiedges. In this article, we show that the problem of the shortest path is polynomial for a divisible multiple graph. The corresponding polynomial algorithm is formulated. We also propose the modification of the algorithm for the case of an arbitrary multiple graph. This modification has an exponential complexity in the parameter k.
The vertex packing problem for a given graph is to find a maximum number of vertices no two of which are joined by an edge. The weighted version of this problem is to find a vertex packingP such that the sum of the in...
详细信息
The vertex packing problem for a given graph is to find a maximum number of vertices no two of which are joined by an edge. The weighted version of this problem is to find a vertex packingP such that the sum of the individual vertex weights is maximum. LetG be the family of graphs whose longest odd cycle is of length not greater than 2K + 1, whereK is any non-negative integer independent of the number (denoted byn) of vertices in the graph. We present an O(n2K+1) algorithm for the maximum weighted vertex packing problem for graphs inG ≥ 1. A by-product of this algorithm is an algorithm for piecing together maximum weighted packings on blocks to find maximum weighted packings on graphs that contain more than one block. We also give an O(n2K+3) algorithm for testing membership inG
This paper addresses cyclic scheduling of multiple hoists in a no-wait electroplating line with constant processing times. The objective is to minimize the cycle time, or equivalently maximizing the production through...
详细信息
ISBN:
(纸本)1424404509
This paper addresses cyclic scheduling of multiple hoists in a no-wait electroplating line with constant processing times. The objective is to minimize the cycle time, or equivalently maximizing the production throughput, for a given number of hoists. The problem is first formulated as a set of prohibited intervals for the cycle time. We then prove that the optimal cycle time is necessarily one of special values of the cycle time, and thus reduce the problem to a feasibility-checking problem for a given value of the cycle time. We show that the latter problem can be transformed to a longest path problem in a directed graph. The complete algorithm is shown to be polynomial in the number of tanks in an electroplating line.
Let Lambda(k)(n) be the set of all n x n binary matrices with exactly k units in each row and each column, 1 <= k <= n. A matrix A is an element of Lambda(k)(n) will be called primitive, if there is no l x l sub...
详细信息
Let Lambda(k)(n) be the set of all n x n binary matrices with exactly k units in each row and each column, 1 <= k <= n. A matrix A is an element of Lambda(k)(n) will be called primitive, if there is no l x l submatrix of A that belongs to the set Lambda(k)(l), k <= l < n .The article describes a polynomial algorithm, which works in time O(n(2)) for verifying whether a Lambda(k)(n)-matrix is primitive. The work applies this algorithm for finding all primitive Lambda(k)(n)-matrices which rows and columns are in lexicographically nondecreasing order (semi-canonical binary matrices) for some integers n and k.
This paper deals with the problem of finding, for a given graph and a given natural number k, a subgraph of k nodes with a maximum number of edges. This problem is known as the k-cluster problem and it is NP-hard on g...
详细信息
For a large class of closed orientable 3-manifolds, we present a polynomial algorithm to go from a triangulation to a framed link presenting the same manifold. The algorithm applies whenever we can get a resoluble gem...
详细信息
For a large class of closed orientable 3-manifolds, we present a polynomial algorithm to go from a triangulation to a framed link presenting the same manifold. The algorithm applies whenever we can get a resoluble gem from the triangulation. Most minimal gems have this property (about 95% of gems in our complete catalogue up to 28 vertices). From the gems which fail, nothing prevents another gem from inducing the same 3-manifold to be resoluble. We leave as an open problem presenting a 3-manifold which is not induced by a resoluble gem. This paper is an application of the theory of gems to 3-manifold topology.
We study unreliable serial production lines with known failure probabilities for each operation. Such a production line consists of a series of stations;existing machines and optional quality control stations (QCS). O...
详细信息
We study unreliable serial production lines with known failure probabilities for each operation. Such a production line consists of a series of stations;existing machines and optional quality control stations (QCS). Our aim is to simultaneously decide where and if to install the QCSs along the line and to determine the production rate, so as to maximize the steady state expected net profit per time unit from the system. We use dynamic programming to solve the cost minimization auxiliary problem where the aim is to minimize the time unit production cost for a given production rate. Using the above developed O(N-2) dynamic programming algorithm as a subroutine, where N stands for the number of machines in the line, we present an O(N-4) algorithm to solve the Profit Maximization QCS Configuration Problem. (C) 2007 Elsevier B.V. All rights reserved.
A word w is a fixed point of a nontrivial morphism h if w = h(w) and h is not the identity on the alphabet of w. The paper presents the first polynomial algorithm deciding whether a given finite word is such a fixed p...
详细信息
A word w is a fixed point of a nontrivial morphism h if w = h(w) and h is not the identity on the alphabet of w. The paper presents the first polynomial algorithm deciding whether a given finite word is such a fixed point. The algorithm also constructs the corresponding morphism, which has the smallest possible number of non-erased letters. (C) 2009 Elsevier B.V. All rights reserved.
Free-floating car sharing (FFCS) systems are a promising concept to reduce the traffic volume in cities. However, spatial and temporal mismatches of supply and demand require a relocation of rental cars in order to av...
详细信息
Free-floating car sharing (FFCS) systems are a promising concept to reduce the traffic volume in cities. However, spatial and temporal mismatches of supply and demand require a relocation of rental cars in order to avoid low degrees of utilization. Here, especially user-based relocation strategies seem to be promising to increase utilization in a costefficient manner. However, a thorough optimization-based assessment of user-based relocation strategies for FFCS systems is still missing. In this paper, we introduce an integer program that optimizes the assignment of userbased relocation strategies in FFCS fleets. We develop a graph representation that allows to reformulate the problem as a k-disjoint shortest paths problem and propose an exact algorithm to solve large-size instances. We show that this algorithm can solve real-world instances within a few milliseconds as well as instances with up to 100,000 customers and 10,000 vehicles in a few minutes. Furthermore, we present a case study based on real-world data and derive managerial insights on user-based relocation strategies. Our results reveal an upper bound on the benefit of user-based relocation strategies and demonstrate that the employment of such strategies can increase the number of fulfilled rental requests by 21%, while increasing the operator's revenue by 10%. (C) 2020 Elsevier Ltd. All rights reserved.
暂无评论