Text mining from large scaled data is of great importance in computer science. In this paper, we consider fundamental problems on text mining from compressed strings, i.e., computing a longest repeating substring, lon...
详细信息
Text mining from large scaled data is of great importance in computer science. In this paper, we consider fundamental problems on text mining from compressed strings, i.e., computing a longest repeating substring, longest non-overlapping repeating substring, most frequent substring, and most frequent non-overlapping substring from a given compressed string. Also, we tackle the following novel problem: given a compressed text and compressed pattern, compute the representative of the equivalence class of the pattern w.r.t. the text. We present algorithms that solve the above problems in timepolynomial in the size of input compressed strings. The compression scheme we consider is straight line program (SLP) which has exponential compression, and therefore our algorithms are more efficient than any existing algorithms that require decompression of given SLPs.
In the production of perishable goods, particular stress is often given to performance indicators generally less critical in such manufacturing settings as metal-cutting, or mechanical/electronic assembly, For instanc...
详细信息
In the production of perishable goods, particular stress is often given to performance indicators generally less critical in such manufacturing settings as metal-cutting, or mechanical/electronic assembly, For instance, in food or biochemical productions, a prominent interest of the producer is to reduce the time from distribution to the so-called best-before end. A scheduling problem with a goal of this sort is here addressed. The decision variables considered are launching and completion times of parts in a production line with critical aspects in the initial and/or final stages. The basic problem is to find an assignment of a maximum number of products to launching and completion times, so that no two products are assigned the same launching or completion time: feasible solutions have therefore the form of three-dimensional matchings. The problem is studied under two independent respects, assuming either (i) the relative perishability of products or (ii) the feasibility of launching/completion time pairs not affected by the intermediate transformation stage. We show that the problem is NP-Complete, even under such a ranking assumption as (i), whereas is in P under assumption (ii). polynomial-time algorithms are also proposed to solve other optimization versions of the problem (in two cases, based on the identification of a matroid structure). (C) 1999 Elsevier Science B.V. All rights reserved.
An extension of the Economic Order Quantity (EOQ) model to multi-stage production-distribution systems and the isotonic regression problem are known to be equivalent and to be solvable in O(N4) time. The following spe...
详细信息
An extension of the Economic Order Quantity (EOQ) model to multi-stage production-distribution systems and the isotonic regression problem are known to be equivalent and to be solvable in O(N4) time. The following specializations of the model are solvable in O(N log N) time: joint replenishment systems, pure assembly systems, nested policies in pure distribution systems, nonnested policies in one-warehouse multi-retailer systems, nested policies in multi-item, one-warehouse, multi-retailer systems, and system in which the underlying network is a series-parallel digraph. We show here that a generalization of this problem is solvable in O(N log N) time whenever the undirected version of the underlying network is a tree. The algorithm we proposed is used as a subroutine in an algorithm solving the EOQ problem on general circuitless directed graphs, the subject of a companion paper.
Background: Orthologs inference is the starting point of most comparative genomics studies, and a plethora of methods have been designed in the last decade to address this challenging task. In this paper we focus on t...
详细信息
Background: Orthologs inference is the starting point of most comparative genomics studies, and a plethora of methods have been designed in the last decade to address this challenging task. In this paper we focus on the problems of deciding consistency with a species tree (known or not) of a partial set of orthology/paralogy relationships C on a collection of n genes. Results: We give the first polynomial algorithm - more precisely a O(n(3)) time algorithm - to decide whether C is consistent, even when the species tree is unknown. We also investigate a biologically meaningful optimization version of these problems, in which we wish to minimize the number of duplication events;unfortunately, we show that all these optimization problems are NP-hard and are unlikely to have good polynomialtime approximation algorithms. Conclusions: Our polynomial algorithm for checking consistency has been implemented in Python and is available at https://***/UdeM-LBIT/OrthoPara-ConstraintChecker.
In this paper we study primal-dual path-following algorithms for second-order cone programming problems (SOCP). We extend the standard long-step/semilong-step/short-step primal-dual path-following alogorithms for LP a...
详细信息
In this paper we study primal-dual path-following algorithms for second-order cone programming problems (SOCP). We extend the standard long-step/semilong-step/short-step primal-dual path-following alogorithms for LP and SDP to SOCP, and prove that the long-step algorithm using the NT direction and the HRVW/KSH/M direction have O(n log epsilon(-1)) iteration-complexity and O(n(3/2) log epsilon(-1)) iteration-complexity, respectively, to reduce the duality gap by a factor of 1/epsilon, where n is the number of the second-order cones. We also show that the short and semilong-step algorithms using the NT direction and the HRVW/KSH/M direction have O(root n log epsilon(-1)) and O(n log epsilon(-1)) iteration-complexities, respectively.
We consider the open shop problem with n jobs, m machines, and the minimum makespan criterion. Let l(i) stand for the load of the ith machine, l(max) be the maximum machine load, and p(max) be the maximum operation le...
详细信息
We consider the open shop problem with n jobs, m machines, and the minimum makespan criterion. Let l(i) stand for the load of the ith machine, l(max) be the maximum machine load, and p(max) be the maximum operation length. Suppose that the machines are numbered in nonincreasing order of their loads and that p(max) = 1, while other processing times are numbers in the interval [0, 1]. Then, given an instance of the open shop problem, we define its vector of differences VOD = (Delta(1),...,Delta(m)), where Delta(i) = l(max) - l(i). An instance is called normal if its optimal schedule has length l(max). A vector Delta is an element of R-m is called normalizing if every instance with VOD = Delta is normal. A vector Delta is an element of R-m is called efficiently normalizing if it is normalizing and there is a polynomial-time algorithm which for any instance with VOD = Delta constructs its optimal schedule. In this paper, a few nontrivial classes of efficiently normalizing vectors are found in R-m . It is also shown that the vector (0, 0, 2) is the unique minimal normalizing vector in R-3, and that there are at least two minimal normalizing vectors in R-4 .
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.
We consider the problem of preemptively scheduling n independent jobs {J(1),J(2), ..., J(n)} on m parallel machines {M(1),M(2), ..., M(m)}, where each job J(j) can only be processed on a prespecified subset M(j) of ma...
详细信息
We consider the problem of preemptively scheduling n independent jobs {J(1),J(2), ..., J(n)} on m parallel machines {M(1),M(2), ..., M(m)}, where each job J(j) can only be processed on a prespecified subset M(j) of machines called its processing set. The machines are linearly ordered, and the processing set of J(j) is specified by two machine indexes a(j) and b(j);i.e., M(j) = {M(aj),M(aj+1), ..., M(bj)}. The processing sets are nested;i.e., for i not equal j, we have M(i) subset of M(j), or M(j) subset of M(i),or M(j) boolean AND M(i) = phi..Our goal is to minimize the makespan. We first give an O(n logn)-time algorithm to find an optimal schedule. We then give an O(mn + nlogn)-time algorithm to find a maximal schedule, where a schedule is said to be maximal if it processes as much work as any other schedule in any time interval [0, t], t>0.
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a ...
详细信息
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints;the problem is to decide whether or not the larger set of constraints has a satisfying assignment. This model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.
暂无评论