We study the problem of covering given points in Euclidean space with a minimum number of nonconvex objects of a given type. We concentrate on the one-dimensional case of this problem, whose computational complexity w...
详细信息
We study the problem of covering given points in Euclidean space with a minimum number of nonconvex objects of a given type. We concentrate on the one-dimensional case of this problem, whose computational complexity was previously unknown. We define a natural measure for the “degree of nonconvexity” of a nonconvex object. Our results show that for any fixed bound on the degree of nonconvexity of the covering objects the one-dimensional nonconvex covering problem can be solved in polynomialtime. On the other hand without such bound on the degree of nonconvexity the one-dimensional nonconvex covering problem is NP-complete. We also consider the capacitated version of the nonconvex covering problem and we exhibit a useful property of minimum coverings by objects whose degree of nonconvexity is low.
As a common generalization of bipartite and split graphs, monopolar graphs are defined in terms of the existence of certain vertex partitions. It has been shown that to determine whether a graph has such a partition i...
详细信息
As a common generalization of bipartite and split graphs, monopolar graphs are defined in terms of the existence of certain vertex partitions. It has been shown that to determine whether a graph has such a partition is an NP-complete problem for general graphs, and is polynomialtime solvable for several classes of graphs. In this paper, we investigate graphs that admit a unique such partition and call them uniquely monopolar-partitionable graphs. By employing a tree trimming technique, we obtain a characterization of uniquely monopolar-partitionable block graphs. Our characterization implies a polynomial time algorithm for determining whether a block graph is uniquely monopolar-partitionable.
Let G = (V, E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v E V has a demand d(V) epsilon Z(+) and a cost c(v) epsilon R+, where Z(+) and R+ denote the set of nonnegative i...
详细信息
Let G = (V, E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v E V has a demand d(V) epsilon Z(+) and a cost c(v) epsilon R+, where Z(+) and R+ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G requires finding a set S of vertices minimizing Sigma(v epsilon S) c(v) such that there are at least d(v) pairwise vertex-disjoint paths from S to v for each vertex v epsilon V - S. It is known that if there exists a vertex v epsilon V with d(v) >= 4, then the problem is NP-hard even in the case where every vertex has a uniform cost. In this paper, we show that the problem can be solved in O(vertical bar V vertical bar(4) log(2) vertical bar V vertical bar) time if d(v) <= 3 holds for each vertex v epsilon V. (c) 2006 Elsevier B.V. All rights reserved.
This article considered the single machine scheduling with controllable processing time (resource allocation) and deterioration effect concurrently. It discussed the minimization of three objectives, which involve the...
详细信息
This article considered the single machine scheduling with controllable processing time (resource allocation) and deterioration effect concurrently. It discussed the minimization of three objectives, which involve the weighted sum of the makespan and the total resource consumption cost, the total resource consumption cost under the condition that the makespan (total flow time) is restricted to a fixed constant and the optimal resource allocation and the optimal job sequence is what we need to make decision. Considering the makespan constraint, it proved that these problems can be solved in polynomialtime. A special case of the last problem can be solved in polynomialtime with respect to the total flow time constraint.
This paper is concerned with the best piecewise constant approximation of a function f of single variable. polynomial time algorithms are derived by using shortest path and dynamic programming techniques. Several appl...
详细信息
This paper is concerned with the best piecewise constant approximation of a function f of single variable. polynomial time algorithms are derived by using shortest path and dynamic programming techniques. Several applications of this class of problems will be briefly touched upon.
In the field of Discrete Tomography, the 2-color problem consists in reconstructing a matrix whose elements are of two different types, starting from its horizontal and vertical projections. It is known that the 1-col...
详细信息
In the field of Discrete Tomography, the 2-color problem consists in reconstructing a matrix whose elements are of two different types, starting from its horizontal and vertical projections. It is known that the 1-color problem admits a polynomialtime reconstruction algorithm, while the c-color problem, with c >= 2, is NP-hard. Thus, the 2-color problem constitutes an interesting example of a problem just in the frontier between hard and easy problems. In this paper we define a linear timealgorithm (in the size of the output matrix) to solve a subclass of its instances, where some values of the horizontal and vertical projections are constant, while the others are upper bounded by a positive number proportional to the dimension of the problem. Our algorithm relies on classical studies for the solution of the 1-color problem. (C) 2010 Elsevier B.V. All rights reserved.
This paper introduces the maximization version of the kpath vertex cover problem, called theM aximum k-P ath V ertex C over problem (MaxP(k)VC for short): A path consisting of k vertices, i.e., a path of length k 1 is...
详细信息
This paper introduces the maximization version of the kpath vertex cover problem, called theM aximum k-P ath V ertex C over problem (MaxP(k)VC for short): A path consisting of k vertices, i.e., a path of length k 1 is called a k-path. If a k-path P-k includes a vertex v in a vertex set S, then we say that v or S covers P-k. Given a graph G = (V;E) and an integer s, the goal of MaxP(k)VC is to find a vertex subset S subset of V of at most s vertices such that the number of k-paths covered by S is maximized. The problem MaxP(k)VC is generally NP-hard. In this paper we consider the tractability/intractability of MaxP(k)VC on subclasses of graphs. We prove that MaxP(3)VC remains NP-hard even for split graphs. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP(3)VC can be solved in polynomialtime.
This paper addresses the stochastic lot-sizing problem with quantity discounts. In particular, we examine the uncapacitated finite-period economic lot-sizing problem in which the parameters in each period are random a...
详细信息
This paper addresses the stochastic lot-sizing problem with quantity discounts. In particular, we examine the uncapacitated finite-period economic lot-sizing problem in which the parameters in each period are random and discrete. When an order is placed, a fixed cost is incurred and an all-unit quantity discount is awarded based on the quantity ordered. The lead time is zero and the order is delivered immediately. First we study the case with overstocks by which the excess inventory incurs a holding cost. The objective in this case is to minimize the expected total cost including ordering and holding costs. The stochastic dynamics is modeled with a scenario tree. We characterize properties Of the optimal policy and propose a polynomial time algorithm with complexity O(n(3)) for single discount level, where n is the number of nodes in the scenario tree. We extend the results to cases allowing stockout and multi-discount levels. Numerical experiments are conducted to evaluate the performance of the algorithm and to gain the management insights. (C) 2016 Elsevier Ltd. All rights reserved.
Let P be a set of n >= 4 points in the plane that is in general position and such that n is even. We investigate the problem whether there is a (0-, 1- or 2-connected) cubic plane straight-line graph on P. No polyn...
详细信息
Let P be a set of n >= 4 points in the plane that is in general position and such that n is even. We investigate the problem whether there is a (0-, 1- or 2-connected) cubic plane straight-line graph on P. No polynomial-timealgorithm is known for this problem. Based on a reduction to the existence of certain diagonals of the boundary cycle of the convex hull of P, we give the first polynomial-timealgorithm that checks for 2-connected cubic plane graphs;the algorithm is constructive and runs in time O (n(3)). We also show which graph structure can be expected when there is a cubic plane graph on P;e.g., a cubic plane graph on P implies a connected cubic plane graph on P, and a 2-connected cubic plane graph on P implies a 2-connected cubic plane graph on P that contains the boundary cycle of P. We extend the above algorithm to check for arbitrary cubic plane graphs in time O (n(3)). (C) 2014 Elsevier B.V. All rights reserved.
We solve the special case of the Euclidean Traveling Salesman Problem where n - m cities lie on the boundary of the convex hull of all n cities, and the other m cities lie on a line segment inside this convex hull by ...
详细信息
We solve the special case of the Euclidean Traveling Salesman Problem where n - m cities lie on the boundary of the convex hull of all n cities, and the other m cities lie on a line segment inside this convex hull by an algorithm which needs O(mn) time and O(n) space.
暂无评论