This paper considers the uncapacitated lot sizing problem with batch delivery, focusing on the general case of time-dependent batch sizes. We study the complexity of the problem, depending on the other cost parameters...
详细信息
This paper considers the uncapacitated lot sizing problem with batch delivery, focusing on the general case of time-dependent batch sizes. We study the complexity of the problem, depending on the other cost parameters, namely the setup cost, the fixed cost per batch, the unit procurement cost and the unit holding cost. We establish that if any one of the cost parameters is allowed to be time-dependent, the problem is NP-hard. On the contrary, if all the cost parameters are stationary, and assuming no unit holding cost, we show that the problem is polynomially solvable in time O(T-3), where T denotes the number of periods of the horizon. We also show that, in the case of divisible batch sizes, the problem with time varying setup costs, a stationary fixed cost per batch and no unit procurement nor holding cost can be solved in time O(T-3 logT). (C) 2013 Elsevier B.V. All rights reserved.
We consider a single-machine common due-window assignment scheduling problem, in which the processing time of a job is a function of its position in a sequence and its resource allocation. The window location and size...
详细信息
We consider a single-machine common due-window assignment scheduling problem, in which the processing time of a job is a function of its position in a sequence and its resource allocation. The window location and size, along with the associated job schedule that minimizes a certain cost function, are to be determined. This function is made up of costs associated with the window location, window size, earliness, and tardiness. For two different processing time functions, we provide a polynomial time algorithm to find the optimal job sequence and resource allocation, respectively.
PREMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n(8)) timealgorithm f...
详细信息
PREMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n(8)) timealgorithm for PREIMAGE CONSTRUCTION on permutation graphs and an O(n(4)(n + m)) timealgorithm for PREIMAGE CONSTRUCTION on distance-hereditary graphs, where n is the number of graphs in the input, and m is the number of edges in a preimage: Since each graph of the input has n - 1 vertices and O(n(2)) edges, the input size is O(n(3)) (, or O(nm)). There are polynomialtime isomorphism algorithms for permutation graphs and distance-hereditary graphs. However the number of permutation (distance-hereditary) graphs obtained by adding a vertex to a permutation (distance-hereditary) graph is generally exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point.
In this paper, the time-optimal velocity planning problem for five-axis computer numerical control machining along a given parametric tool path under chord error, acceleration, and jerk constraints is studied. The vel...
详细信息
In this paper, the time-optimal velocity planning problem for five-axis computer numerical control machining along a given parametric tool path under chord error, acceleration, and jerk constraints is studied. The velocity planning problem under confined chord error, feedrate, and acceleration is reduced to an equivalent linear programming problem by discretizing the tool path and other quantities. As a consequence, a polynomial time algorithm with computational complexity O(N (3.5)) is given to find the optimal solution, where N is the number of discretized segments of the tool path. The velocity planning problem under confined chord error, feedrate, acceleration, and jerk is reduced to a linear programming program by using a linear function to approximate the nonlinear jerk constraint. As a consequence, a polynomial time algorithm is given to find the approximate time-optimal solution. Simulation results are used to show the efficiency and effectiveness of the algorithms.
A cycle C in a graph G is extendable if there is some other cycle in G that contains each vertex of C plus one additional vertex. A graph is cycle extendable if every non-Hamilton cycle in the graph is extendable. A b...
详细信息
A cycle C in a graph G is extendable if there is some other cycle in G that contains each vertex of C plus one additional vertex. A graph is cycle extendable if every non-Hamilton cycle in the graph is extendable. A balanced incomplete block design, BIBD(v,k,), consists of a set V of v elements and a block set B of k-subsets of V such that each 2-subset of V occurs in exactly of the blocks of B. The block-intersection graph of a design D=(V,B) is the graph GD having B as its vertex set and such that two vertices of GD are adjacent if and only if their corresponding blocks have nonempty intersection. In this paper, we prove that the block-intersection graph of any BIBD(v,k,) is cycle extendable. Furthermore, we present a polynomial time algorithm for constructing cycles of all possible lengths in a block-intersection graph. (C) 2012 Wiley Periodicals, Inc. J. Combin. Designs 21: 303-310, 2013
We consider two graph optimization problems called vector domination and total vector domination. In vector domination one seeks a small subset S of vertices of a graph such that any vertex outside S has a prescribed ...
详细信息
We consider two graph optimization problems called vector domination and total vector domination. In vector domination one seeks a small subset S of vertices of a graph such that any vertex outside S has a prescribed number of neighbors in S. In total vector domination, the requirement is extended to all vertices of the graph. We prove that these problems (and several variants thereof) cannot be approximated to within a factor of c In n, where c is a suitable constant and n is the number of the vertices, unless P=NP. We also show that two natural greedy strategies have approximation factors In Delta + 0(1), where Delta is the maximum degree of the input graph. We also provide exact polynomial time algorithms for several classes of graphs. Our results extend, improve, and unify several results previously known in the literature. (C) 2012 Elsevier B.V. All rights reserved.
Starting with Knutson and Tao's hive model [J. Amer. Math. Soc., 12 (1999), pp. 1055-1090] we characterize the Littlewood-Richardson coefficient c(lambda)(nu),(mu) of given partitions lambda, mu, nu is an element ...
详细信息
Starting with Knutson and Tao's hive model [J. Amer. Math. Soc., 12 (1999), pp. 1055-1090] we characterize the Littlewood-Richardson coefficient c(lambda)(nu),(mu) of given partitions lambda, mu, nu is an element of N-n as the number of capacity achieving hive flows on the honeycomb graph. Based on this, we design a polynomial time algorithm for deciding c(lambda)(nu),(mu) > 0. This algorithm is easy to state and takes O(n(3) log nu(1)) arithmetic operations and comparisons. We further show that the capacity achieving hive flows can be seen as the vertices of a connected graph, which leads to new structural insights into Littlewood-Richardson coefficients.
Following Golubitsky, Stewart, and others, we give definitions of networks and input trees. In order to make our work as general as possible, we work with a somewhat extended notion of multiplicity, and introduce the ...
详细信息
Following Golubitsky, Stewart, and others, we give definitions of networks and input trees. In order to make our work as general as possible, we work with a somewhat extended notion of multiplicity, and introduce the concept of "bunching" of trees. We then de. ne balanced equivalence relations on networks, and a partial ordering on these relations. Previous work has shown that there is a maximal balanced equivalence relation on networks of certain classes: we provide a different style of proof which gives this result for any network. We de. ne two algorithms to determine this relation in practice on a given finite network-one for use with networks with all multiplicities equal, and a second for the more general case. We then provide illustrative examples of each algorithm in use. We show both of these algorithms to be quartic in the size of the given network.
Determining the complexity of the colouring problem on AT-free graphs is one of long-standing open problems in algorithmic graph theory. One of the reasons behind this is that AT-free graphs are not necessarily perfec...
详细信息
Determining the complexity of the colouring problem on AT-free graphs is one of long-standing open problems in algorithmic graph theory. One of the reasons behind this is that AT-free graphs are not necessarily perfect unlike many popular subclasses of AT-free graphs such as interval graphs or co-comparability graphs. In this paper, we resolve the smallest open case of this problem, and present the first polynomial time algorithm for the 3-colouring problem on AT-free graphs.
This paper considers the problem of projecting a vector on the intersection of a closed half-space and a variable box. We present a polynomial time algorithm that is based on a parametric approach for finding the expl...
详细信息
This paper considers the problem of projecting a vector on the intersection of a closed half-space and a variable box. We present a polynomial time algorithm that is based on a parametric approach for finding the explicit formulas for the metric projection. As an application, the proposed algorithm is applied to compute the metric projection over the epigraph of the Ky Fan k-norm functions. Computational results on large-scale random test problems are also reported in order to evaluate the algorithm and its complexity time. (C) 2013 Elsevier B.V. All rights reserved.
暂无评论