In this paper we propose a long-step logarithmic barrier function method for convex quadratic programming with linear equality constraints. After a reduction of the barrier parameter, a series of long steps along proj...
详细信息
In this paper we propose a long-step logarithmic barrier function method for convex quadratic programming with linear equality constraints. After a reduction of the barrier parameter, a series of long steps along projected Newton directions are taken until the iterate is in the vicinity of the center associated with the current value of the barrier parameter. We prove that the total number of iterations is O(square-root nL) or O(nL), depending on how the barrier parameter is updated.
Extending linear constraints by admitting parameters allows for more abstract problem modeling and reasoning. A lot of focus has been given to conducting research that demonstrates the usefulness of parameterized line...
详细信息
Extending linear constraints by admitting parameters allows for more abstract problem modeling and reasoning. A lot of focus has been given to conducting research that demonstrates the usefulness of parameterized linear constraints and implementing tools that utilize their modeling strength. However, there is no approach that considers basic theoretical tools related to such constraints that allow for reasoning over them. Hence, in this paper we introduce satisfiability with respect to polyhedral sets and entailment for the class of parameterized linear constraints. In order to study the computational complexities of these problems, we relate them to classes of quantified linear implications. The problem of satisfiability with respect to polyhedral sets is then shown to be co- hard. The entailment problem is also shown to be co- hard in its general form. Nevertheless, we characterize some subclasses for which this problem is in a"(TM). Furthermore, we examine a weakening and a strengthening extension of the entailment problem. The weak entailment problem is proved to be complete. On the other hand, the strong entailment problem is shown to be co- hard.
We study the problem of nonpreemptively scheduling n jobs on m identical machines in parallel to maximize the weighted number of jobs that are completed exactly at their due dates. We show that this problem is solvabl...
详细信息
We study the problem of nonpreemptively scheduling n jobs on m identical machines in parallel to maximize the weighted number of jobs that are completed exactly at their due dates. We show that this problem is solvable in polynomial time even if positive set-up times are allowed. Moreover, we show that if due date tolerances are permitted, then already the single-machine case is NP-hard even if all set-up times are zero and all weights are the same.
The computational complexity of inverse mimimum capacity path problem with lower bound on capacity of maximum capacity path is examined, and it is proved that solution of this problem is NP-complete. A strong polynomi...
详细信息
The computational complexity of inverse mimimum capacity path problem with lower bound on capacity of maximum capacity path is examined, and it is proved that solution of this problem is NP-complete. A strong polynomial algorithm for a local optimal solution is provided.
Computation of elementary siphons proposed by Li et al. is essential for deadlock control and expensive since complete siphon enumeration of the Petri net is needed, and the number of strict minimal siphons (SMS) grow...
详细信息
Computation of elementary siphons proposed by Li et al. is essential for deadlock control and expensive since complete siphon enumeration of the Petri net is needed, and the number of strict minimal siphons (SMS) grows quickly and exponentially with the size of the net. They assumed that the siphon constructed from each resource circuit is an elementary one and proposed a polynomial algorithm to compute elementary siphons. However, the author demonstrates a counter example where there may be an exponential number of resource circuits. Hence, constructing elementary siphons from resource circuits will result in an exponential number of elementary siphons, which is wrong. The author then develops a polynomial algorithm to find elementary siphons, which also constructs all SMS on the way. This is because, in the method proposed by Li et al., a linear algebraic expression must be established for each dependent siphon, which implies, all SMS must be located. However, all elementary siphons with polynomial complexity can be located.
We consider the one-machine scheduling problem to minimize the number of late jobs under the group technology assumption, where jobs are classified into groups and all jobs from the same group must be processed contig...
详细信息
We consider the one-machine scheduling problem to minimize the number of late jobs under the group technology assumption, where jobs are classified into groups and all jobs from the same group must be processed contiguously. This problem is shown to be strongly NP-hard, even for the case of unit processing time and zero set-up time. A polynomial time algorithm is developed for the restricted version in which the jobs in each group have the same due date. However, the problem is proved to be ordinarily NP-hard if the jobs in a group have the same processing time as well as the same due date.
We introduce two variants of proper colorings with imposed partial ordering on the set of colors. One variant shows very close connections to some fundamental problems in graph theory, e.g., directed graph homomorphis...
详细信息
We introduce two variants of proper colorings with imposed partial ordering on the set of colors. One variant shows very close connections to some fundamental problems in graph theory, e.g., directed graph homomorphism and list colorings. We study the border between tractability and intractability for both variants.
We prove polynomial solvability of the maximum stable set problem in P-5-free banner-free ((P-5,B)-free) graphs, where Ps is the simple path on five vertices and a banner is the graph with vertices a,b,c,d,e and edges...
详细信息
We prove polynomial solvability of the maximum stable set problem in P-5-free banner-free ((P-5,B)-free) graphs, where Ps is the simple path on five vertices and a banner is the graph with vertices a,b,c,d,e and edges (a,b), (b, c), (b, d), (c, e), (d, e). (C) 2000 Elsevier Science B.V. All rights reserved.
This article considers a class of bottleneck capacity expansion problems. Such problems aim to enhance bottleneck capacity to a certain level with minimum cost. Given a network G（V,A,C^-） consisting of a set of node...
详细信息
This article considers a class of bottleneck capacity expansion problems. Such problems aim to enhance bottleneck capacity to a certain level with minimum cost. Given a network G（V,A,C^-） consisting of a set of nodes V = {v1,v2,... ,vn}, a set of arcs A C {（vi,vj） ｜ i = 1,2,...,n; j = 1,2,...,n} and a capacity vector C. The component C^-ij of C is the capacity of arc （vi, vj）. Define the capacity of a subset A′ of A as the minimum capacity of the arcs in A, the capacity of a family F of subsets of A is the maximum capacity of its members. There are two types of expanding models. In the arc-expanding model, the unit cost to increase the capacity of arc （vi, vj） is ωij. In the node-expanding model, it is assumed that the capacities of all arcs （vi, vj） which start at the same node vi should be increased by the same amount and that the unit cost to make such expansion is wi. This article considers three kinds of bottleneck capacity expansion problems （path, spanning arborescence and maximum flow） in both expanding models. For each kind of expansion problems, this article discusses the characteristics of the problems and presents several results on the complexity of the problems.
The complexity status of the stable set problem in P-5-free graphs remains an open question for a long time in spite of a lot of particular results in this direction. The purpose of the present paper is to summarize t...
详细信息
The complexity status of the stable set problem in P-5-free graphs remains an open question for a long time in spite of a lot of particular results in this direction. The purpose of the present paper is to summarize these results and to propose several new ones. In particular, we prove that the problem of finding a maximum stable set can be solved in polynomial time in the class of (P-5,K-m,K-m)-free graphs for any fixed m. (C) 2001 Elsevier Science B.V. All rights reserved.
暂无评论