Study of a Monod–Haldene type food chain chemostat with pulsed substrate

In this paper, we introduce and study a model of a Monod–Haldene type food chain chemostat with pulsed substrate. We investigate the subsystem with substrate and prey and study the stability of the periodic solutions, which are the boundary periodic solutions of the system. The stability analysis of the boundary periodic solution yields an invasion threshold. By use of standard techniques of bifurcation theory, we prove that above this threshold there are periodic oscillations in substrate, prey, and predator. Simple cycles may give way to chaos in a cascade of period-doubling bifurcations. Furthermore, by comparing bifurcation diagrams with different bifurcation parameters, we can see that the impulsive system shows two kinds of bifurcations, whose are period-doubling and period-halfing.     

On estimating model complexity and prediction errors in multivariate calibration: generalized resampling by random sample weighting (RSW)

The present paper focuses on determining the number of PLS components by using resampling methods such as cross validation (CV), Monte Carlo cross validation (MCCV), bootstrapping (BS), etc. To resample the training data, random non‐negative weights are assigned to the original training samples and a sample‐weighted PLS model is developed without increasing the computational burden much. Random weighting is a generalization of the traditional resampling methods and is expected to have a lower risk of getting an insufficient training set. For prediction, only the training samples with random weights less than a threshold value are selected to ensure that the prediction samples have less influence on training. For complicated data, because the optimal number of PLS components is often not unique or readily distinguished and there might exist an optimal region of model complexity, the distribution of prediction errors can be more useful than a single value of root mean squared error of prediction (RMSEP). Therefore, the distribution of prediction errors are estimated by repeated random sample weighting and used to determine model complexity. RSW is compared with its traditional counterparts like CV, MCCV, BS and a recently proposed randomization test method to demonstrate its usefulness. Copyright © 2010 John Wiley & Sons, Ltd.     

FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension

We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. Moreover, using a weaker notion of approximation, we show the existence of a fully polynomial-time approximation scheme for the problem of maximizing or minimizing an arbitrary polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. A conference version of this article, containing a part of the results presented here, appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006, pp. 743–748. The first author gratefully acknowledges support from NSF grant DMS-0608785, a 2003 UC-Davis Chancellor’s fellow award, the Alexander von Humboldt foundation, and IMO Magdeburg. The remaining authors were supported by the European TMR network ADONET 504438.     

PSPACE complexity of modal logic <Emphasis Type="Italic">K D</Emphasis>45<Subscript>n</Subscript>

We study sequent calculus for multi-modal logic K D45_n and its complexity. We introduce a loop-check free sequent calculus. Loop-check is eliminated by using the marked modal operator □_i^•, which is used as an alternative to sequents with histories ([8], [3], [5]). All inference rules are invertible or semi-invertible. To get this, we use or branches beside common and branches. We prove the equivalence between known sequent calculus and our newly introduced efficient sequent calculus. We concentrate on the complexity analysis of the introduced sequent calculus for multi-modal logic K D45_n. We prove that the space complexity of the given calculus is polynomial (O(l ³)). We show the maximum height of the constructed derivation tree that leads to the reduction of the time and space complexity. We present a decision algorithm for multi-modal logic K D45_n and some nontrivial examples to improve the introduced loop-check free sequent calculus.     

Computing the minimal covering set

We present the first polynomial-time algorithm for computing the minimal covering set of a (weak) tournament. The algorithm draws upon a linear programming formulation of a subset of the minimal covering set known as the essential set. On the other hand, we show that no efficient algorithm exists for two variants of the minimal covering set–the minimal upward covering set and the minimal downward covering set–unless P equals NP. Finally, we observe a strong relationship between von Neumann–Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other.     

On Overlays and Minimization Diagrams

The overlay of 2≤m≤d minimization diagrams of n surfaces in ℝ ^d is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in ℝ ^d+m−1. This elementary observation leads to a new bound on the complexity of the overlay of minimization diagrams of collections of d-variate semi-algebraic surfaces, a tight bound on the complexity of the overlay of minimization diagrams of collections of hyperplanes, and faster algorithms for constructing such overlays. Further algorithmic implications are discussed. Work by V. Koltun was supported by NSF CAREER award CCF-0641402. Work by M. Sharir was supported by NSF Grants CCR-00-98246 and CCF-05-14079, by a grant from the Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.     

Characterizing PSPACE with pointers

This paper gives an implicit characterization of the class of functions computable in polynomial space by deterministic Turing machines – PSPACE. It gives an inductive characterization of PSPACE with no ad‐hoc initial functions and with only one recursion scheme. The main novelty of this characterization is the use of pointers (also called path information) to reach PSPACE. The presence of the pointers in the recursion on notation scheme is the main difference between this characterization of PSPACE and the well‐known Bellantoni‐Cook characterization of the polytime functions – PTIME. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)