Search

P systems with active membranes are a variant of P systems where membranes can be created by division of existing membranes, thus creating an exponential amount of resources in a polynomial number of steps. Time and space complexity classes for active membrane systems have been introduced, to characterize classes of problems that can be solved by different membrane systems making use of different resources. In particular, space complexity classes introduced initially considered a hypothetical real implementation by means of biochemical materials, assuming that every single object or membrane requires some constant physical space (corresponding to unary notation). A different approach considered implementation of P systems in silico, allowing to store the multiplicity of each object in each membrane using binary numbers. In both cases, the elements contributing to the definition of the space required by a system (namely, the total number of membranes, the total number of objects, the types of different membranes, and the types of different objects) was considered as a whole. In this paper, we consider a different definition for space complexity classes in the framework of P systems, where each of the previous elements is considered independently. We review the principal results related to the solution of different computationally hard problems presented in the literature, highlighting the requirement of every single resource in each solution. A discussion concerning possible alternative solutions requiring different resources is presented.

Parametric timed automata (PTA) have been introduced by Alur, Henzinger, and Vardi as an extension of timed automata in which clocks can be compared against parameters. The reachability problem asks for the existence of an assignment of the parameters to the non-negative integers such that reachability holds in the underlying timed automaton. The reachability problem for PTA is long known to be undecidable, already over three parametric clocks. A few years ago, Bundala and Ouaknine proved that for PTA over two parametric clocks and one parameter the reachability problem is decidable and also showed a lower bound for the complexity class PSPACE^NEXP. Our main result is that the reachability problem for parametric timed automata over two parametric clocks and one parameter is EXPSPACE-complete. For the EXPSPACE lower bound we make use of deep results from complexity theory, namely a serializability characterization of EXPSPACE (in turn based on Barrington’s Theorem) and a logspace translation of numbers in Chinese Remainder Representation to binary representation due to Chiu, Davida, and Litow. It is shown that with small PTA over two parametric clocks and one parameter one can simulate serializability computations. For the EXPSPACE upper bound, we first give a careful exponential time reduction from PTA over two parametric clocks and one parameter to a (slight subclass of) parametric one-counter automata over one parameter based on a minor adjustment of a construction due to Bundala and Ouaknine. For solving the reachability problem for parametric one-counter automata with one parameter, we provide a series of techniques to partition a fictitious run into several carefully chosen subruns that allow us to prove that it is sufficient to consider a parameter value of exponential magnitude only. This allows us to show a doubly-exponential upper bound on the value of the only parameter of a PTA over two parametric clocks and one parameter. We hope that extensions of our techniques lead to finally establishing decidability of the long-standing open problem of reachability in parametric timed automata with two parametric clocks (and arbitrarily many parameters) and, if decidability holds, determining its precise computational complexity., LIPIcs, Vol. 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), pages 36:1-36:18

The first definition of space complexity for P systems was based on a hypothetical real implementation by means of biochemical materials, and thus it assumes that every single object or membrane requires some constant physical space. This is equivalent to using a unary encoding to represent multiplicities for each object and membrane. A different approach can also be considered, having in mind an implementation of P systems in silico; in this case, the multiplicity of each object in each membrane can be stored using binary numbers, thus reducing the amount of needed space. In this paper, we give a formal definition for this alternative space complexity measure, we define the corresponding complexity classes and we compare such classes both with standard space complexity classes and with complexity classes defined in the framework of P systems considering the original definition of space.

The goals and targets included in the 2030 Agenda compiled by the United Nations want to stimulate action in areas of critical importance for humanity and the Earth. These goals and targets regard everyone on Earth from both the health and economic and social perspectives. Reaching these goals means to deal with Complex Systems. Therefore, Complexity Science is undoubtedly valuable. However, it needs to extend its scope and focus on some specific objectives. This article proposes a development of Complexity Science that will bring benefits for achieving the United Nations’ aims. It presents a list of the features shared by all the Complex Systems involved in the 2030 Agenda. It shows the reasons why there are certain limitations in the prediction of Complex Systems’ behaviors. It highlights that such limitations raise ethical issues whenever new technologies interfere with the dynamics of Complex Systems, such as human beings and the environment. Finally, new methodological approaches and promising research lines to face Complexity Challenges included in the 2030 Agenda are put forward.

In reaction systems, preimages and nth ancestors are sets of reactants leading to the production of a target set of products in either 1 or n steps, respectively. Many computational problems on preimages and ancestors, such as finding all minimum-cardinality nth ancestors, computing their size or counting them, are intractable. In this paper, we characterize all nth ancestors using a Boolean formula that can be computed in polynomial time. Once simplified, this formula can be exploited to easily solve all preimage and ancestor problems. This allows us to directly relate the difficulty of ancestor problems to the cost of the simplification so that new insights into computational complexity investigations can be achieved. In particular, we focus on two problems: (i) deciding whether a preimage/nth ancestor exists and (ii) finding a preimage/nth ancestor of minimal size. Our approach is constructive, it aims at finding classes of reactions systems for which the ancestor problems can be solved in polynomial time, in exact or approximate way.

The chase procedure is a fundamental algorithmic tool in database theory with a variety of applications. A key problem concerning the chase procedure is all-instances termination: for a given set of tuple-generating dependencies (TGDs), is it the case that the chase terminates for every input database? In view of the fact that this problem is undecidable, it is natural to ask whether known well-behaved classes of TGDs, introduced in different contexts such as ontological reasoning, ensure decidability. We consider a prominent paradigm that led to a robust TGD-based formalism, called stickiness. We show that for sticky sets of TGDs, all-instances chase termination is decidable if we focus on the (semi-)oblivious chase, and we pinpoint its exact complexity: PSpace-complete in general, and NLogSpace-complete for predicates of bounded arity. These complexity results are obtained via a graph-based syntactic characterization of chase termination that is of independent interest.

P systems with active membranes have been widely used to attack problems in $${\mathbf{NP}}$$ or even in $${{\mathbf{PSPACE }}}$$; in general, an exponential amount of space is generated in polynomial time by dividing existing membranes. Natural questions arise in this framework, concerning the power of P systems when different bounds are considered for the use of the space resource. We consider in this paper two natural bounds: the amount of available physical space (in terms of the number of objects and membranes) and the organization of the membrane structure (in particular, concerning the depth of the membrane structure). We present the main results obtained so far on this subject.

In almost all contemporary power systems, the battery is an elementary component, and it is routinely used in a variety of critical applications such as drones, avionics, and cell phones. Due to their superior characteristics compared to the concurrent technologies, Li-ion batteries are widely utilized. Since batteries are costly, their usage is closely monitored by battery management systems (BMSs). It ensures that batteries survive and serve longer. Modern BMSs' are complex and sophisticated and can deal with hundreds of cells in a battery pack. It results in an increased processing resources requirement and can cause an overhead power consumption. The aim of this work is to improve current BMSs by redesigning their associative processing chain. It focuses on improving data collection, processing and prediction processes for Li-ion battery cell capacities. To prevent the processing of a large amount of unnecessary data, the classical sensing approach that is fix-rate is avoided and replaced by event-driven sensing (EDS) mechanism to digitize battery cell parameters such as voltages, currents, and temperatures in a way that allows for real-time data compressing. A new approach is proposed for event-driven feature extraction. The robust machine-learning algorithms are employed for processing the extracted features and to predict the capacity of considered battery cell. Results show a considerable compression gain with a correlation coefficient of 0.999 and the relative absolute error (RAE) and root relative squared error (RRSE) of 1.88% and 2.08%, respectively.

Despite being a central concept in cheminformatics, molecular similarity has so far been limited to the simultaneous comparison of only two molecules at a time and using one index, generally the Tanimoto coefficent. In a recent contribution we have not only introduced a complete mathematical framework for extended similarity calculations, (i.e. comparisons of more than two molecules at a time) but defined a series of novel idices. Part 1 is a detailed analysis of the effects of various parameters on the similarity values calculated by the extended formulas. Their features were revealed by sum of ranking differences and ANOVA. Here, in addition to characterizing several important aspects of the newly introduced similarity metrics, we will highlight their applicability and utility in real-life scenarios using datasets with popular molecular fingerprints. Remarkably, for large datasets, the use of extended similarity measures provides an unprecedented speed-up over “traditional” pairwise similarity matrix calculations. We also provide illustrative examples of a more direct algorithm based on the extended Tanimoto similarity to select diverse compound sets, resulting in much higher levels of diversity than traditional approaches. We discuss the inner and outer consistency of our indices, which are key in practical applications, showing whether then-ary and binary indices rank the data in the same way. We demonstrate the use of the newn-ary similarity metrics ont-distributed stochastic neighbor embedding (t-SNE) plots of datasets of varying diversity, or corresponding to ligands of different pharmaceutical targets, which show that our indices provide a better measure of set compactness than standard binary measures. We also present a conceptual example of the applicability of our indices in agglomerative hierarchical algorithms. The Python code for calculating the extended similarity metrics is freely available at:https://github.com/ramirandaq/MultipleComparisons

Image restoration and denoising is an essential preprocessing step for almost every subsequent task in computer vision. Markov Random Fields offer a well-founded, sophisticated approach for this purpose, but unfortunately the associated computation procedures are not sufficiently fast, due to a high-dimensional optimization problem. While the increase of computing power could not solve this runtime issue appropriately, we address it in a mathematical way: we suggest an analytical solution for the optimum of the inference problem, which provides desirable mathematical properties. In practice, our new method accelerates the runtime via reducing the computational complexity of the image restoration task by orders of magnitude, independent from the smoothing intensity. As a result, Markov Random Fields can be considered for modern big data problems in computer vision, especially if numerous images with equal sizes are processed.

Virtually all molecular interaction networks (MINs), irrespective of organism or physiological context, have a majority of loosely-connected ‘leaf’ genes interacting with at most 1-3 genes, and a minority of highly-connected ‘hub’ genes interacting with at least 10 or more other genes. Previous reports proposed adaptive and non-adaptive hypotheses describing sufficient but not necessary conditions for the origin of this majority-leaves minority-hubs (mLmH) topology. We modeled the evolution of MINs as a computational optimization problem which describes the cost of conserving, deleting or mutating existing genes so as to maximize (minimize) the overall number of beneficial (damaging) interactions network-wide. The model 1) provides sufficient and, assuming , necessary conditions for the emergence of mLmH as a software adaptation to circumvent computational intractability, 2) predicts the percentage number of genes having d interacting partners, and 3) when employed as a fitness function in an evolutionary algorithm, produces mLmH-possessing synthetic networks whose degree distributions match those of equal-size MINs.SummaryOur results indicate that the topology of molecular interaction networks is a selected-for software adaptation that minimizes the evolutionary cost of re-wiring the network in response to an evolutionary pressure to conserve, delete or mutate existing genes and interactions.

P systems with active membranes are a variant of P systems where membranes play an active role during the computation, for example by dividing existing membranes in order to create new ones. In this way, an exponential number of membranes can be obtained in polynomial time, and then used in parallel to attack computationally hard problems. Many interesting questions arise concerning the trade-off between time and space needed to solve various classes of computational problems by means of such membrane systems. In this paper we overview the main results presented in the literature concerning this subject.

Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios, however, the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality k without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to k. Further, we derive some polynomial-time solvable cases for $$k=2$$k=2 with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of k.

Image smoothing with edge preservation in the presence of outliers is a challenge in image processing. Anisotropic diffusion smoothing is a well-established paradigm in digital image smoothing with edge preservation. Anisotropic diffusion smoothing filters are not robust to impulse noise. They employ two or more stages for robustness in the presence of outliers, and, therefore, they demand significantly increased arithmetic operations for robustness; consequently, they are not power efficient. This paper introduces a low arithmetic complexity image smoothing model and proposes an intrinsically robust and power efficient algorithm for anisotropic diffusion smoothing of images. The algorithm outperforms the foundational robust smoothing algorithms in terms of the standard performance metrics and visual quality.

International audience; We study a 0-1 knapsack problem, in which the objective value is forbidden to take some values. We call gaps related forbidden intervals. The problem is NP-hard and pseudo-polynomially solvable independently on the measure of gaps. If the gaps are large, then the problem is polynomially non-approximable. A non-trivial special case with respect to the approximate solution appears when the gaps are small and polynomially close to zero. For this case, two fully polynomial time approximation schemes are proposed. The results can be extended for the constrained longest path problem and other combinatorial problems.

Multistage stochastic programs bring computational complexity which may increase exponentially with the size of the scenario tree in real case problems. For this reason approximation techniques which replace the problem by a simpler one and provide lower and upper bounds to the optimal value are very useful. In this paper we provide monotonic lower and upper bounds for the optimal objective value of a multistage stochastic program. These results also apply to stochastic multistage mixed integer linear programs. Chains of inequalities among the new quantities are provided in relation to the optimal objective value, the wait-and-see solution and the expected result of using the expected value solution. The computational complexity of the proposed lower and upper bounds is discussed and an algorithmic procedure to use them is provided. Numerical results on a real case transportation problem are presented.

We apply the well-known Condorcet criterion from voting theory outside of its classical framework and link it with spanning trees of an undirected graph. In situations in which a network, represented by a spanning tree of an undirected graph, needs to be installed, decision-makers typically do not agree on the network to be implemented. Instead, each of these decision-makers has her own ideal conception of the network. In order to derive a group decision, i.e., a single spanning tree for the entire group of decision-makers, the goal would be a spanning tree that beats each other spanning tree in a simple majority comparison. When comparing two dedicated spanning trees, a decision-maker will be considered to be more satisfied with the one that is "closer" to her proposal. In this context, the most basic and natural measure of distance is the usual set difference: we simply count the number of edges the spanning tree has in common with the proposal of the decision-maker. In this work, we show that it is computationally intractable to decide (1) if such a spanning tree exists, and (2) if a given spanning tree satisfies the Condorcet criterion.

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as #CSP and Graph Homomorphism. An effective dichotomy for such frameworks can immediately settle the complexity of all combinatorial problems expressible in that framework. Both #CSP and Graph Homomorphism can be viewed as sub-families of Holant with the additional assumption that the equality constraints are always available. Other sub-families of Holant such as Holant^* and Holant^c problems, in which we assume some specific sets of constraints to be freely available, were also studied. The Holant framework becomes more expressive and contains more interesting tractable cases with less or no freely available constraint functions, while, on the other hand, it also becomes more challenging to obtain a complete characterization of its time complexity. Recently, complexity dichotomy for a variety of sub-families of Holant such as #CSP, Graph Homomorphism, Holant^* and Holant^c were proved. The dichotomy for the general Holant framework, which is the most desirable, still remains open. In this paper, we prove a dichotomy for the general Holant framework where all the constraints are real symmetric functions. This setting already captures most of the interesting combinatorial problems defined by local constraints, such as (perfect) matching, independent set, vertex cover and so on. This is the first time a dichotomy is obtained for general Holant Problems without any auxiliary functions. One benefit of working with Holant framework is some powerful new reduction techniques such as Holographic reduction. Along the proof of our dichotomy, we introduce a new reduction technique, namely realizing a constraint function by approximating it. This new technique is employed in our proof in a situation where it seems that all previous reduction techniques fail, thus this new idea of reduction might also be of independent interest. Besides proving dichotomy and developing new technique, we also obtained some interesting by-products. We prove a dichotomy for #CSP restricting to instances where each variable appears a multiple of d times for any d. We also prove that counting the number of Eulerian-Orientations on 2k-regular graphs is #P-hard for any k>=2.

In this paper we investigate the computational complexity of motivating time-inconsistent agents to complete long term projects. We resort to an elegant graph-theoretic model, introduced by Kleinberg and Oren, which consists of a task graph $G$ with $n$ vertices, including a source $s$ and target $t$, and an agent that incrementally constructs a path from $s$ to $t$ in order to collect rewards. The twist is that the agent is present-biased and discounts future costs and rewards by a factor $\beta\in [0,1]$. Our design objective is to ensure that the agent reaches $t$ i.e.\ completes the project, for as little reward as possible. Such graphs are called motivating. We consider two strategies. First, we place a single reward $r$ at $t$ and try to guide the agent by removing edges from $G$. We prove that deciding the existence of such motivating subgraphs is NP-complete if $r$ is fixed. More importantly, we generalize our reduction to a hardness of approximation result for computing the minimum $r$ that admits a motivating subgraph. In particular, we show that no polynomial-time approximation to within a ratio of $\sqrt{n}/4$ or less is possible, unless ${\rm P}={\rm NP}$. Furthermore, we develop a $(1+\sqrt{n})$-approximation algorithm and thus settle the approximability of computing motivating subgraphs. Secondly, we study motivating reward configurations, where non-negative rewards $r(v)$ may be placed on arbitrary vertices $v$ of $G$. The agent only receives the rewards of visited vertices. Again we give an NP-completeness result for deciding the existence of a motivating reward configuration within a fixed budget $b$. This result even holds if $b=0$, which in turn implies that no efficient approximation of a minimum $b$ within a ration grater or equal to $1$ is possible, unless ${\rm P}={\rm NP}$.

This paper considers the computational complexity of the design of voting rules, which is formulated by simple games. We prove that it is an NP-complete problem to decide whether a given simple game is stable, or not.

This paper discusses the problem of minimizing the reconfiguration cost of some types of reconfigurable systems. A formal definition of the problem and a proof of its NP-completeness are provided. In addition, an Integer Linear Programming formulation is proposed. The proposed problem has been used for optimizing a design stage of Finite Virtual State Machines.

This article presents a new approximation algorithm for globally solving a class of generalized fractional programming problems (P) whose objective functions are defined as an appropriate composition of ratios of affine functions. To solve this problem, the algorithm solves an equivalent optimization problem (Q) via an exploration of a suitably defined nonuniform grid. The main work of the algorithm involves checking the feasibility of linear programs associated with the interesting grid points. It is proved that the proposed algorithm is a fully polynomial time approximation scheme as the ratio terms are fixed in the objective function to problem (P), based on the computational complexity result. In contrast to existing results in literature, the algorithm does not require the assumptions on quasi-concavity or low-rank of the objective function to problem (P). Numerical results are given to illustrate the feasibility and effectiveness of the proposed algorithm.

This paper presents a linear decomposition approach for a class of nonconvex programming problems by dividing the input space into polynomially many grids. It shows that under certain assumptions the original problem can be transformed and decomposed into a polynomial number of equivalent linear programming subproblems. Based on solving a series of liner programming subproblems corresponding to those grid points we can obtain the near-optimal solution of the original problem. Compared to existing results in the literature, the proposed algorithm does not require the assumptions of quasi-concavity and differentiability of the objective function, and it differs significantly giving an interesting approach to solving the problem with a reduced running time.

Online social networks have transformed the way in which humans communicate and interact, leading to a new information ecosystem where people send and receive information through multiple channels, including traditional communication media. Despite many attempts to characterize the structure and dynamics of these techno-social systems, little is known about fundamental aspects such as how collective attention arises and what determines the information life-cycle. Current approaches to these problems either focus on human temporal dynamics or on semiotic dynamics. In addition, as recently shown, information ecosystems are highly competitive, with humans and memes striving for scarce resources -visibility and attention, respectively. Inspired by similar problems in ecology, here we develop a methodology that allows to cast all the previous aspects into a compact framework and to characterize, using microblogging data, information-driven systems as mutualistic networks. Our results show that collective attention around a topic is reached when the user-meme network self-adapts from a modular to a nested structure, which ultimately allows minimizing competition and attaining consensus. Beyond a sociological interpretation, we explore such resemblance to natural mutualistic communities via well-known dynamics of ecological systems., Main text + Supplementary Information (merged). To appear in Scientific Reports (2017)

International audience; The problems studied in this paper originate from Graph Motif, a problem introduced in 2006 in the context of biological networks. Informally speaking, it consists in deciding if a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Due to the high rate of noise in the biological data, more flexible definitions of the problem have been outlined. We present in this paper two inapproximability results for two different optimization variants of Graph Motif: one where the size of the solution is maximized, the other when the number of substitutions of colors to obtain the motif from the solution is minimized. We also study a decision version of Graph Motif where the connectivity constraint is replaced by the well known notion of graph modularity. While the problem remains N P-complete, it allows algorithms in F P T for biologically relevant parameterizations.

We describe a method of forcing against weak theories of arithmetic and its applications in propositional proof complexity.

We consider a setting where a coalition of individuals chooses one or several alternatives from each set in a collection of choice sets.We examine the computational complexity of Pareto rationalizability. Pareto rationalizability requires that we can endow each individual in the coalition with a preference relation such that the observed choices are Pareto efficient.We differentiate between the situation where the choice function is considered to select all Pareto optimal alternatives from a choice set and the situation where it only contains one or several Pareto optimal alternatives. In the former casewe find that Pareto rationalizability is an NP-complete problem. For the latter case we demonstrate that, if we have no additional information on the individual preference relations, then all choice behavior is Pareto rationalizable. However, if we have such additional information, then Pareto rationalizability is again NP-complete. Our results are valid for any coalition of size greater or equal than two. ispartof: Social Choice and Welfare vol:42 issue:3 pages:529-549 status: published

We study the maximum weighted independent-set problem on interval graphs with uncertainty on the vertexweights.We use the absolute robustness criterion and the min–max regret criterion to evaluate solutions. For a discrete scenario set, we find that the problem is NP-hard for each of the robustness criteria; we also provide pseudo-polynomial time algorithms when there is a constant number of scenarios and show that the problem is strongly NP-hard when the set of scenarios is unbounded. When the scenario set is a Cartesian product,we prove that the problem is equivalent to a maximum weighted independent-set problem on the same interval graph but without uncertainty for the first objective function and that the scenario set can be reduced for the second objective function. ispartof: Optimization Letters vol:8 issue:1 pages:227-235 status: published

Background Even for moderate size inputs, there are a tremendous number of optimal rearrangement scenarios, regardless what the model is and which specific question is to be answered. Therefore giving one optimal solution might be misleading and cannot be used for statistical inferring. Statistically well funded methods are necessary to sample uniformly from the solution space and then a small number of samples are sufficient for statistical inferring. Contribution In this paper, we give a mini-review about the state-of-the-art of sampling and counting rearrangement scenarios, focusing on the reversal, DCJ and SCJ models. Above that, we also give a Gibbs sampler for sampling most parsimonious labeling of evolutionary trees under the SCJ model. The method has been implemented and tested on real life data. The software package together with example data can be downloaded from http://www.renyi.hu/~miklosi/SCJ-Gibbs/

In a less constrained capture of iris images to build a high-speed iris recognition system, the design of a robust and fast iris segmentation method is important. In this paper, a new iris segmentation technique based on the Fourier spectral density is proposed for noisy frontal view eye images captured with minimum cooperation from the subjects. The proposed segmentation method is not an iterative technique and it runs in deterministic time. The computational complexity of the proposed method is found to be significantly lower than the existing approaches based on integro-differential operator, Hough transform and active contour. The basic idea underlying the proposed method is to localize the limbic and pupil boundaries using the Fourier spectral density. The performance studies on a recently created iris database, called UBIRIS (Proenca and Alexandre in Lect Notes Comput Sci 3617:970-977, 2005) containing defocused, reflection-contained and eyelid-occluded iris images in visible spectral range, show that the proposed method is much faster than the existing methods and simultaneously achieves good segmentation accuracy. � 2009 Springer-Verlag London Limited.

We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main theorem is that if (uniform, constant-free) VPSPACE families can be evaluated efficiently then the class PAR of decision problems that can be solved in parallel polynomial time over the real numbers collapses to P. As a result, one must first be able to show that there are VPSPACE families which are hard to evaluate in order to separate over the reals P from NP, or even from PAR., Comment: Full version of the paper (appendices of the first version are now included in the text)

Copyright @ Springer Science + Business Media, LLC 2009 This paper presents an improved constraint satisfaction adaptive neural network for job-shop scheduling problems. The neural network is constructed based on the constraint conditions of a job-shop scheduling problem. Its structure and neuron connections can change adaptively according to the real-time constraint satisfaction situations that arise during the solving process. Several heuristics are also integrated within the neural network to enhance its convergence, accelerate its convergence, and improve the quality of the solutions produced. An experimental study based on a set of benchmark job-shop scheduling problems shows that the improved constraint satisfaction adaptive neural network outperforms the original constraint satisfaction adaptive neural network in terms of computational time and the quality of schedules it produces. The neural network approach is also experimentally validated to outperform three classical heuristic algorithms that are widely used as the basis of many state-of-the-art scheduling systems. Hence, it may also be used to construct advanced job-shop scheduling systems. This work was supported in part by the Engineering and Physical Sciences Research Council (EPSRC) of UK under Grant EP/E060722/01 and in part by the National Nature Science Fundation of China under Grant 60821063 and National Basic Research Program of China under Grant 2009CB320601.

We investigate polarizationless P systems with active membranes working in maximally parallel manner, which do not make use of evolution or communication rules, in order to find which features are sufficient to efficiently solve computationally hard problems. We show that such systems are able to solve the PSPACE-complete problem QUANTIFIED 3-SAT, provided that non-elementary membrane division is controlled by the presence of a (possibly non-elementary) membrane. Ministerio de Educación y Ciencia TIN2006-13425 Junta de Andalucía TIC-581

In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiry. At present, the complexity status of the MCB problem is settled only for undirected, directed, and strictly fundamental cycle bases (SFCBs). Weakly fundamental cycle bases (WFCBs) form a natural superclass of SFCBs. A cycle basis of a graph G is a WFCB iff ½=0 or there exists an edge e of G and a circuit C i in such that is a WFCB of Ge. WFCBs still possess several of the nice properties offered by SFCBs. At the same time, several classes of graphs enjoying WFCBs of cost asymptotically inferior to the cost of the cheapest SFCBs have been found and exhibited in the literature. Considered also the computational difficulty of finding cheap SFCBs, these works advocated an in-depth study of WFCBs. In this paper, we settle the complexity status of the MCB problem for WFCBs (the MWFCB problem). The problem turns out to be -hard. However, in this paper, we also offer a simple and practical 2⌈log 2 n⌉-approximation algorithm for the MWFCB problem. In O(n ν) time, this algorithm actually returns a WFCB whose cost is at most 2⌈log 2 n⌉∑e∈E(G) w e, thus allowing a fast 2⌈log 2 n⌉-approximation also for the MCB problem. With this algorithm, we provide tight bounds on the cost of any MCB and MWFCB.

The customer order scheduling problem (COSP) is defined as to determine the sequence of tasks to satisfy the demand of customers who order several types of products produced on a single machine. A setup is required whenever a product type is launched. The objective of the scheduling problem is to minimize the average customer order flow time. Since the customer order scheduling problem is known to be strongly NP-hard, we solve it using four major metaheuristics and compare the performance of these heuristics, namely, simulated annealing, genetic algorithms, tabu search, and ant colony optimization. These are selected to represent various characteristics of metaheuristics: nature-inspired vs. artificially created, population-based vs. local search, etc. A set of problems is generated to compare the solution quality and computational efforts of these heuristics. Results of the experimentation show that tabu search and ant colony perform better for large problems whereas simulated annealing performs best in small-size problems. Some conclusions are also drawn on the interactions between various problem parameters and the performance of the heuristics.

In 1923, Eduard Helly published his celebrated theorem, which originated the well known Helly property. Say that a family of subsets has the Helly property when every subfamily of it, formed by pairwise intersecting subsets, contains a common element. There are many generalizations of this property which are relevant to some parts of mathematics and several applications in computer science. In this work, we survey computational aspects of the Helly property. The main focus is algorithmic. That is, we describe algorithms for solving different problems arising from the basic Helly property. We also discuss the complexity of these problems, some of them leading to NP-hardness results.

The lexicographic kernel of a game lexicographically maximizes the surplusses s(ij) ( rather than the excesses as would the nucleolus) and is contained in both the least core and the kernel. We show that an element in the lexicographic kernel can be computed efficiently, provided we can efficiently compute the surplusses s(ij) (x) corresponding to a given allocation x. This approach improves the results in Faigle et al. ( in Int J Game Theory 30: 79-98, 2001) and allows us to determine a kernel element without appealing to Maschler transfers in the execution of the algorithm.

In this survey we have attempted to bring together most of the results and papers that deal with toughness related to cycle structure. We begin with a brief introduction and a section on terminology and notation, and then try to organize the work into a few self explanatory categories. These categories are circumference, the disproof of the 2-tough conjecture, factors, special graph classes, computational complexity, and miscellaneous results as they relate to toughness. We complete the survey with some tough open problems!

OFDM is recognized to be one of the best transmission techniques for wideband wireless communication systems. However, it exhibits two main drawbacks: its large amplitude fluctuation and its sensitivity to phase noise. Here we consider the phase noise impairments, taking care of the phase noise spectrum, which diverges form the classical Wiener model as the carrier frequency increases. Moreover, we show that the phase noise distortion can be decomposed in two terms, one dependent on the symbol under detection and the other dependent on the symbols of adjacent subcarriers, so that the performance degradation depends on both the constellation used in each subcarrier and the phase noise spectrum. As a consequence of this new results, the penalty due to phase noise expressed in terms of the average signal/noise plus interference ratio is not applicable in the case of modulations with non-constant amplitude constellations, such as 16- or 64-QAM. The method proposed here achieves a good accuracy, while keeping a low computational complexity, and it is confirmed by simulations.

Udgivelsesdato: August 2002 In this paper we refer to the Temporal Precedence Problem on Pure Pointer Machines . This problem asks for the design of a data structure, maintaining a set of stored elements and supporting the following two operations: insert and precedes . The operation insert (a) introduces a new element a in the structure, while the operation precedes (a,b) returns true iff element a was inserted before element b temporally. In [11] a solution was provided to the problem with worst-case time complexity O (log log n ) per operation and O(n log log n) space, where n is the number of elements inserted. It was also demonstrated that the precedes operation has a lower bound of Ω (log log n ) for the Pure Pointer Machine model of computation. In this paper we present two simple solutions with linear space and worst-case constant insertion time. In addition, we describe two algorithms that can handle the precedes (a,b) operation in O (log log d ) time, where d is the temporal distance between the elements a and b .

In the last two decades several NC algorithms for solving basic linear algebraic problems have ap- peared in the literature. This interest was clearly motivated by the emergence of a parallel computing technology and by the wide applicability of matrix computations. The traditionally adopted computation model, however, ignores the arithmetic aspects of the applications, and no analysis is currently available demonstrating the con- crete feasibility of many of the known fast methods. In this paper we give strong evidence to the contrary, on the sole basis of the issue of robustness, indicating that some theoretically brilliant solutions fail the severe test of the "Engineering of Algorithms." We perform a comparative analysis of several well-known numerical matrix inversion algorithms under both fixed- and variable-precision models of arithmetic. We show that, for most methods investigated, a typical input leads to poor numerical performance, and that in the exact-arithmetic set- ting no benefit derives from conditions usually deemed favorable in standard scientific computing. Under these circumstances, the only algorithm admitting sufficiently accurate NC implementations is Newton's iterative method, and the word size required to guarantee worst-case correctness appears to be the critical complexity measure. Our analysis also accounts for the observed instability of the considered superfast methods when implemented with the same floating-point arithmetic that is perfectly adequate for the fixed-precision approach.

International audience; A three-dimensional (3-D) model for the prediction of dendritic grain structures formed during solidification is presented. This model is built on the basis of a 3-D cellular automaton (CA) algorithm. The simulation domain is subdivided into a regular lattice of cubic cells. Using physically based rules for the simulation of nucleation and growth phenomena, a state index associated with each cell is switched from zero (liquid state) to a positive value (mushy and solid state) as solidification proceeds. Because these physical phenomena are related to the temperature field, the cell grid is superimposed to a coarser finite element (FE) mesh used for the solution of the heat flow equation. Two coupling modes between the microscopic CA and macroscopic FE calculations have been designed. In a so-called “weak” coupling mode, the temperature of each cell is simply interpolated from the temperature of the FE nodes using a unique solidification path at the macroscopic scale. In a “full” coupling mode, the enthalpy field is also interpolated from the FE nodes to the CA cells and a fraction of solid increment is computed for each mushy cell using a truncated Scheil microsegregation model. These fractions of solid increments are then fed back to the FE nodes in order to update the new temperature field, thus accounting for a more realistic release of the latent heat (i.e., the solidification path is no longer unique). Special dynamic allocation techniques have been designed in order to minimize the computation costs and memory size associated with a very large number of cells (typically 107 to 108). The potentiality of the CAFE model is demonstrated through the predictions of typical grain structures formed during the investment casting and continuous casting processes.

“Logical analysis of data” (LAD) is a methodology developed since the late eighties, aimed at discovering hidden structural information in data sets. LAD was originally developed for analyzing binary data by using the theory of partially defined Boolean functions. An extension of LAD for the analysis of numerical data sets is achieved through the process of “binarization” consisting in the replacement of each numerical variable by binary “indicator” variables, each showing whether the value of the original variable is above or below a certain level. Binarization was successfully applied to the analysis of a variety of real life data sets. This paper develops the theoretical foundations of the binarization process studying the combinatorial optimization problems related to the minimization of the number of binary variables. To provide an algorithmic framework for the practical solution of such problems, we construct compact linear integer programming formulations of them. We develop polynomial time algorithms for some of these minimization problems, and prove NP-hardness of others.

Time-delay estimation is studied for cognitive radio systems, which facilitate opportunistic use of spectral resources. A two-step approach is proposed to obtain accurate time-delay estimates of signals that occupy multiple dispersed bands simultaneously, with significantly lower computational complexity than the optimal maximum likelihood (ML) estimator. In the first step of the proposed approach, an ML estimator is used for each band of the signal in order to estimate the unknown parameters of the signal occupying that band. Then, in the second step, the estimates from the first step are combined in various ways in order to obtain the final time-delay estimate. The combining techniques that are used in the second step are called optimal combining, signal-to-noise ratio (SNR) combining, selection combining, and equal combining. It is shown that the performance of the optimal combining technique gets very close to the Cramer-Rao lower bound at high SNRs. These combining techniques provide various mechanisms for diversity combining for time-delay estimation and extend the concept of diversity in communications systems to the time-delay estimation problem in cognitive radio systems. Simulation results are presented to evaluate the performance of the proposed estimators and to verify the theoretical analysis.

The recently developed blind adaptive techniques for multiuser detection in code division multiple access (CDMA) systems offer an attractive compromise of performance and complexity. However, the desire to further reduce complexity at the mobile unit has led to the investigation of techniques that move signal processing from the mobile unit to the base station. In this paper, we investigate transmitter precoding for downlink time division duplex (TDD) code division multiple access (CDMA) communications. In particular, we develop a linear minimum mean square error precoding strategy using blind channel estimation for fading multipath channels that allows for simple matched filtering at the mobile unit and is easy to make adaptive. We also present a performance analysis using tools developed for the analysis of conventional (receiver-based) linear blind multiuser detection in unknown channels. We compare the analytical and simulation results to traditional receiver-based blind multiuser detection. It is seen that transmitter precoding offers a reasonable alternative for TDD-mode CDMA when minimizing computational complexity at the mobile unit is a priority.