A minimal siphon (or alternatively a structural deadlock) of a Petri net is defined as a minimal set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from s...
详细信息
A minimal siphon (or alternatively a structural deadlock) of a Petri net is defined as a minimal set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. The subject of the paper is to find a minimal siphon containing a given set of specified places of a general Petri net.
We discuss the problem of scheduling preemptive independent tasks, subject to release dates and due dates, on identical processors, so as to minimize the maximum lateness. This problem was solved by a polynomial flow ...
详细信息
We discuss the problem of scheduling preemptive independent tasks, subject to release dates and due dates, on identical processors, so as to minimize the maximum lateness. This problem was solved by a polynomial flow based algorithm, but the major drawback of this approach is its off-line character. We study a priority algorithm, the equivalent of a list scheduling method in the non-preemptive case, in which tasks are ordered according to their due dates. This algorithm is nearly on-line and of low complexity. It builds an optimal schedule when the release dates are equal. In the general case, it provides an absolute performance gurantee. These results hold when the number of available machines is allowed to vary with time in a zigzag way (the number of machines is either K, or K - 1).
We consider the following problem: given a labelled directed graph G and a regular expression R, find all pairs of nodes connected by a simple path such that the concatenation of the labels along the path satisfies R....
详细信息
We consider the following problem: given a labelled directed graph G and a regular expression R, find all pairs of nodes connected by a simple path such that the concatenation of the labels along the path satisfies R. The problem is motivated by the observation that many recursive queries in relational databases can be expressed in this form, and by the implementation of a query language, Gi, based on this observation. We show that the problem is in general intractable, but present an algorithm than runs in polynomialtime in the size of the graph when the regular expression and the graph are free of conflicts. We also present a class of languages whose expressions can always be evaluated in timepolynomial in the size of both the graph and the expression, and characterize syntactically the expressions for such languages.
It is well known that every instance of the classical stable marriage problem admits at least one stable matching, and that such a matching can be found in O(n2) time by application of the Gale/Shapley algorithm. In t...
详细信息
It is well known that every instance of the classical stable marriage problem admits at least one stable matching, and that such a matching can be found in O(n2) time by application of the Gale/Shapley algorithm. In the classical version of the problem, each person must rank the members of the opposite sex in strict order of preference. In practical applications, a person may not wish (or be able) to choose between alternatives, thus allowing ties in the preference lists (or, more generally, allowing each preference list to be a partial order). With the introduction of such indifference, the notion of stability may be generalised in three obvious ways. For the weakest extension of stability, the same existence result holds, and essentially the same algorithm may be applied. In the other two cases, however, there is no guarantee that stable matchings exist. Nonetheless, in this paper, we describe polynomial-time algorithms that will establish, in either of these two cases, whether a matching of the appropriate kind exists, and if so will find such a matching.
A spherical code is a finite set X of points lying on the unit sphere of R(n). For such a set, we define rho(X) as the minimum of the squared distances parallel-tox - yparallel-to2, when x, y is-an-element-of X and x ...
详细信息
A spherical code is a finite set X of points lying on the unit sphere of R(n). For such a set, we define rho(X) as the minimum of the squared distances parallel-tox - yparallel-to2, when x, y is-an-element-of X and x not-equal y. Define [GRAPHICS] Chabauty in 1953 and Shannon in 1959 have given a lower bound for R(rho), namely, R(rho) > R(CS)(rho) = 1 - 1/2 log2 rho(4 - rho). The complexity of construction of the spherical codes used in order to get this bound is doubly exponential. The polynomially constructible spherical bound R(pol)(rho) is defined as above with the additional restriction that only families of codes with polynomial complexity of construction are considered. We prove R(pol)(rho) greater-than-or-equal-to R(CS)(rho)/2, if rho less-than-or-equal-to 1.535 .... Denote by tau(X)(n) the number of spheres of equal radius that touch one sphere in the n-dimensional space given by some explicit family X, that is, a family of arrangements of spheres}. The asymptotic polynomially constructible kissing number is theta(pol) = lim sup (log2 tau(X)(n))/n, when X ranges over all polynomially constructible families. We prove theta(pol) greater-than-or-equal-to 2/15 = 0.133 ....
We derive a bound on the computational complexity of linear programs whose coefficients are real algebraic numbers. Key to this result is a notion of problem size that is analogous in function to the binary size of a ...
详细信息
We derive a bound on the computational complexity of linear programs whose coefficients are real algebraic numbers. Key to this result is a notion of problem size that is analogous in function to the binary size of a rational-number problem. We also view the coefficients of a linear program as members of a finite algebraic extension of the rational numbers. The degree of this extension is an upper bound on the degree of any algebraic number that can occur during the course of the algorithm, and in this sense can be viewed as a supplementary measure of problem dimension. Working under an arithmetic model of computation, and making use of a tool for obtaining upper and lower bounds on polynomial functions of algebraic numbers, we derive an algorithm based on the ellipsoid method that runs in time bounded by a polynomial in the dimension, degree, and size of the linear program. Similar results hold under a rational number model of computation, given a suitable binary encoding of the problem input.
This paper studies the complexity of computing (or approximating, or bounding) the various inner and outer radii of an n-dimensional convex polytope in the space R(n) equipped with an l(p) norm or a polytopal norm. Th...
详细信息
This paper studies the complexity of computing (or approximating, or bounding) the various inner and outer radii of an n-dimensional convex polytope in the space R(n) equipped with an l(p) norm or a polytopal norm. The polytope P is assumed to be presented as the convex hull of finitely many points with rational coordinates (V-presented) or as the intersection of finitely many closed halfspaces defined by linear inequalities with rational coefficients (He-presented). The inner j-radius of P is the radius of a largest j-ball contained in P;it is P's in radius when j = n and half of P's diameter when j = 1. The outer j-radius measures how well P can be approximated, in a minimax sense, by an (n - j)-flat;it is P's circumradius when j = n and half of P's width when j = 1. The binary (Turing machine) model of computation is employed. The primary concern is not with finding optimal algorithms, but with establishing polynomial-time computability or NP-hardness. Special attention is paid to the case in which P is centrally symmetric. When the dimension n is permitted to vary, the situation is roughly as follows: (a) for general H-presented polytopes in l(p) spaces with 1 < p < infinity, all outer radius computations are NP-hard;(b) in the remaining cases (including symmetric H-presented polytopes), some radius computations can be accomplished in polynomialtime and others are NP-hard. These results are obtained by using a variety of tools from the geometry of convex bodies, from linear and nonlinear programming, and from the theory of computational complexity. Applications of the results to various problems in mathematical programming, computer science and other fields are included.
We consider scheduling problems that involve processors of different classes and jobs with fixed start and finish times. We allow preemption of jobs, but impose restrictions on the assignment of processors to jobs. We...
详细信息
We consider scheduling problems that involve processors of different classes and jobs with fixed start and finish times. We allow preemption of jobs, but impose restrictions on the assignment of processors to jobs. We present polynomial-time algorithms for finding the minimal-cost preemptive solutions for two special cases in which the number of job classes is at most one more than the number of processor classes. We then discuss a generalized version in which a processor can be assigned only to a subset of the jobs and a job can be done only by a subset of the processors. We prove that for this case the problem of finding a preemptive feasible schedule with a given combination of processors can be solved in polynomialtime, by transforming it into a transportation-network problem. Next, we extend these results to cyclic scheduling problems. Further, we discuss some transformations among these class scheduling problems and provide simpler proofs of NP-completeness for the nonpreemptive versions of the first two cases.
In this paper, we propose an algorithm of O(Absolute value of V min{k, Absolute value of V, square-root Absolute value of A} Absolute value of A time complexity for finding all k-edge-connected components of a given d...
详细信息
In this paper, we propose an algorithm of O(Absolute value of V min{k, Absolute value of V, square-root Absolute value of A} Absolute value of A time complexity for finding all k-edge-connected components of a given digraph D = ( V, A) and a positive integer k. When D is symmetric, incorporating a preprocessing reduces this time complexity to 0 ( Absolute value of A + Absolute value of V2 + Absolute value of V min{k, Absolute value of V} min{k Absolute value of V, Absolute value of A}), which is at most O(Absolute value of A + k2 Absolute value of V2).
We show that a modified variant of the interior point method can solve linear programs (LPs) whose coefficients are real numbers from a subring of the algebraic integers. By defining the encoding size of such numbers ...
详细信息
We show that a modified variant of the interior point method can solve linear programs (LPs) whose coefficients are real numbers from a subring of the algebraic integers. By defining the encoding size of such numbers to be the bit size of the integers that represent them in the subring, we prove the modified algorithm runs in timepolynomial in the encoding size of the input coefficients, the dimension of the problem, and the order of the subring. We then extend the Tardos scheme to our case, obtaining a running time which is independent of the objective and right-hand side data. As a consequence of these results, we are able to show that LPs with real circulant coefficient matrices can be solved in strongly polynomialtime. Finally, we show how the algorithm can be applied to LPs whose coefficients belong to the extension of the integers by a fixed set of square roots.
暂无评论