Recognition and dualization of disguised bidual Horn functions

We consider the problem of dualizing a Boolean function f given by CNF, i.e., computing a CNF for its dual f^d. While this problem is not solvable in quasi-polynomial total time in general (unless SAT is solvable in quasi-polynomial time), it is so in case the input belongs to special classes, e.g., the class of bidual Horn CNF ? [Discrete Appl. Math. 96-97 (1999) 55-88] (i.e., both ? and its dual ?^d represent Horn functions). In this paper, we show that a disguised bidual Horn CNF ? (i.e., ? becomes a bidual Horn CNF after renaming of variables) can be recognized in polynomial time, and its dualization can be done in quasi-polynomial total time. We also establish a similar result for dualization of prime CNFs.     

Synthesis of PID controllers for high-order plants with time-delay

This note deals with the problem of the stabilizing parameter set of PID controllers for high-order all pole plants with time-delay. The time constants of the plants are assumed to be arbitrary, either positive or negative. First of all, the stabilizing range of the proportional gain is given in terms of a version of the Hermite–Beihler Theorem and the properties of the imaginary part of the closed-loop characteristic quasi-polynomial. Then, based on a graphical stability criterion for time-delay systems, the stabilizing region in integral-derivative space is drawn and identified for a fixed admissible proportional gain. An algorithm for determining the stabilizing parameter set of PID controllers is also proposed. Finally, case studies are provided to illustrate the shapes of the stabilizing regions.     

Robust stability region of fractional order PIλ controller for fractional order interval plant

In this article, by using the fractional order PI^λ controller, we propose a simple and effective method to compute the robust stability region for the fractional order linear time-invariant plant with interval type uncertainties in both fractional orders and relevant coefficients. The presented method is based on decomposing the fractional order interval plant into several vertex plants using the lower and upper bounds of the fractional orders and relevant coefficients and then constructing the characteristic quasi-polynomial of each vertex plant, in which the value set of vertex characteristic quasi-polynomial in the complex plane is a polygon. The D-decomposition method is used to characterise the stability boundaries of each vertex characteristic quasi-polynomial in the space of controller parameters, which can obtain the stability region by varying λ orders in the range (0,?2). These regions of each vertex plant are computed by using three stability boundaries: real root boundary (RRB), complex root boundary (CRB) and infinite root boundary (IRB). The method gives the explicit formulae corresponding to these boundaries in terms of fractional order PI^λ controller parameters. Thus, the robust stability region for fractional order interval plant can be obtained by intersecting stability region of each vertex plant. The robustness of stability region is tested by the value set approach and zero exclusion principle. Our presented technique does not require sweeping over the parameters and also does not need linear programming to solve a set of inequalities. It also offers several advantages over existing results obtained in this direction. The method in this article is useful for analysing and designing the fractional order PI^λ controller for the fractional order interval plant. An example is given to illustrate this method.     

The triangle scheduling problem

This paper introduces a novel scheduling problem, where jobs occupy a triangular shape on the time line. This problem is motivated by scheduling jobs with different criticality levels. A measure is introduced, namely the binary tree ratio. It is shown that the Greedy algorithm solves the problem to optimality when the binary tree ratio of the input instance is at most 2. We also show that the problem is unary NP-hard for instances with binary tree ratio strictly larger than 2 and provide a quasi-polynomial time approximation scheme. The approximation ratio of Greedy on general instances is shown to be between 1.5 and 1.05.     

Decision tree approximations of Boolean functions

Decision trees are popular representations of Boolean functions. We show that, given an alternative representation of a Boolean function f, say as a read-once branching program, one can find a decision tree T which approximates f to any desired amount of accuracy. Moreover, the size of the decision tree is at most that of the smallest decision tree which can represent f and this construction can be obtained in quasi-polynomial time. We also extend this result to the case where one has access only to a source of random evaluations of the Boolean function f instead of a complete representation. In this case, we show that a similar approximation can be obtained with any specified amount of confidence (as opposed to the absolute certainty of the former case.) This latter result implies proper PAC-learnability of decision trees under the uniform distribution without using membership queries.     

A robust fractional-order PID controller design based on active queue management for TCP network

In this paper, a robust fractional-order controller is designed to control the congestion in transmission control protocol (TCP) networks with time-varying parameters. Fractional controllers can increase the stability and robustness. Regardless of advantages of fractional controllers, they are still not common in congestion control in TCP networks. The network parameters are time-varying, so the robust stability is important in congestion controller design. Therefore, we focused on the robust controller design. The fractional PID controller is developed based on active queue management (AQM). D-partition technique is used. The most important property of designed controller is the robustness to the time-varying parameters of the TCP network. The vertex quasi-polynomials of the closed-loop characteristic equation are obtained, and the stability boundaries are calculated for each vertex quasi-polynomial. The intersection of all stability regions is insensitive to network parameter variations, and results in robust stability of TCP/AQM system. NS-2 simulations show that the proposed algorithm provides a stable queue length. Moreover, simulations show smaller oscillations of the queue length and less packet drop probability for FPID compared to PI and PID controllers. We can conclude from NS-2 simulations that the average packet loss probability variations are negligible when the network parameters change.     

Robust Stability of Quasi-Polynomials: Frequency-Sweeping Conditions and Vertex Tests

In this paper, we study the robust stability of uncertain time-delay systems. We consider uncertain quasi-polynomials whose coefficients may vary in a certain prescribed range. Our goal is to derive necessary and sufficient conditions for such uncertain quasi-polynomials to maintain stability independent of delay parameters. Our primary contributions are frequency-sweeping conditions for interval, diamond, and spherical quasi-polynomial families, which can be readily checked, requiring only the computation of two simple frequency-dependent functions. Additionally, we also obtain vertex- and edge-type results in the spirit of the Kharitonov approach known in robust stability analysis, showing that the stability of interval and diamond quasi-polynomials can be ascertained by checking the stability of certain special vertex and/or edge members in those families. Both type of results provide necessary and sufficient conditions for the quasi-polynomial families to be robustly stable independent of delay.      

On delay-derivative-dependent stability of systems with fast-varying delays

Stability of linear systems with uncertain bounded time-varying delays is studied under the assumption that the nominal delay values are not equal to zero. An input-output approach to stability of such systems is known to be based on the bound of the L₂-norm of a certain integral operator. There exists a bound on this operator norm in two cases: in the case where the delay derivative is not greater than 1 and in the case without any constraints on the delay derivative. In the present note we fill the gap between the two cases by deriving a tight operator bound which is an increasing and continuous function of the delay derivative upper bound d?1. For d→∞ the new bound corresponds to the second case and improves the existing bound. As a result, for the first time, delay-derivative-dependent frequency domain and time domain stability criteria are derived for systems with the delay derivative greater than 1.     

A new delay-dependent absolute stability criterion for a class of nonlinear neutral systems

This paper deals with absolute stability for a class of nonlinear neutral systems using a discretized Lyapunov functional approach. A delay-dependent absolute stability criterion is obtained and formulated in the form of linear matrix inequalities (LMIs). The criterion is valid not only for systems with small delay, but also for systems with non-small delay. Neither model transformation nor bounding technique for cross terms, nor free weighting matrix method is involved through derivation of the stability criterion. Numerical examples show that for small delay case, the results obtained in this paper significantly improve the estimate of the stability limit over some existing result in the literature; for non-small delay case, the ideal results can also be achieved.     

On robustness of constrained discrete-time systems to state measurement errors

In this note we show that robustness with respect to additive disturbances implies robustness with respect to state measurement errors and additive disturbances for a class of discrete-time closed-loop nonlinear systems. The main result is formulated in terms of input-to-state stability and includes the possible presence of input and state constraints. Moreover, the state feedback controllers are allowed to be discontinuous and set-valued and thus the result also applies to model predictive control laws.     

A note on a QPTAS for maximum weight triangulation of planar point sets

We observe that the recent quasi-polynomial time approximation scheme (QPTAS) of Adamaszek and Wiese for the Maximum Weight Independent Set of Polygons problem, where polygons have at most a polylogarithmic number of vertices and nonnegative weights, yields:

1.

a QPTAS for the problem of finding, for a set S of n points in the plane, a planar straight-line graph (PSLG) whose vertices are the points in S and whose each interior face is a simple polygon with at most a polylogarithmic in n number of vertices such that the total weight of the inner faces is maximized, and in particular,     

Exploiting sparsity in pricing routines for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a well-known and fundamental vehicle routing problem. A promising exact solution approach to the CARP is to model it as a set covering problem and solve it via branch-cut-and-price. The bottleneck in this approach is the pricing (column generation) routine. In this paper, we note that most CARP instances arising in practical applications are defined on sparse graphs. We show how to exploit this sparsity to yield faster pricing routines. Extensive computational results are given.     

A note on “A multiple-vendor single-buyer integrated inventory model with a variable number of vendors”

In this technical note, an alternative solution procedure to the model that Glock (2011) developed is presented. In particular, we take into account the same assumptions, but the total cost function is reformulated, i.e., the step-type discontinuity is replaced by a logistic approximation and the total costs of the system are computed on the whole set of preselected suppliers. Subsequently, we show that the total cost function possesses some properties in terms of convexity and continuity that allow the exploitation of standard constrained nonlinear minimization algorithms. Finally, tests conducted on the same set of problems that Glock (2011) originally considered illustrate the good performances of the solution procedure developed in this note.     

Minimum-cost single-source 2-splittable flow

In the single-source unsplittable flow problem, commodities must be routed simultaneously from a common source vertex to certain sinks in a given directed graph with edge capacities and costs. The demand of each commodity must be routed along a single path so that the total flow through any edge is at most its capacity. Moreover the cost of the solution should not exceed a given budget. An important open question is whether a simultaneous (2,1)-approximation can be achieved for minimizing congestion and cost, i.e., the budget constraint should not be violated. In this note we show that this is possible for the case of 2-splittable flows, i.e., flows where the demand of each commodity is routed along at most two paths. Our result holds under the “no-bottleneck” assumption, i.e., the maximum demand does not exceed the minimum capacity.     

Specifying safety-critical systems with a decidable duration logic

Punctual timing constraints are important in formal modelling of safety-critical real-time systems. But they are very expensive to express in dense time. In most cases, punctuality and dense-time lead to undecidability. Efforts have been successful to obtain decidability; but the results are either non-primitive recursive or nonelementary. In this paper we propose a duration logic which can express quantitative temporal constraints and punctuality timing constraints over continuous intervals and has a reasonable complexity. Our logic allows most specifications that are interesting in practice, and retains punctuality. It can capture the semantics of both events and states, and incorporates the notions duration and accumulation. We call this logic ESDL (the acronym stands for Event- and State-based Duration Logic). We show that the satisfiability problem is decidable, and the complexity of the satisfiability problem is NEXPTIME. ESDL is one of a few decidable interval temporal logics with metric operators. Through some case studies, we also show that ESDL can specify many safety-critical real-time system properties which were previously specified by undecidable interval logics or their decidable reductions based on some abstractions.     

Mapping Based Algorithm for Large-Scale Computation of Quasi-Polynomial Zeros

A method for computing all zeros of a retarded quasi-polynomial that are located in a large region of the complex plane is presented. The method is based on mapping the quasi-polynomial and on utilizing asymptotic properties of the chains of zeros. First, the asymptotic exponentials of the chains are determined based on the distribution diagram of the quasi-polynomial. Secondly, large regions free of zeros are defined. Finally, the zeros are located as the intersection points of the zero-level curves of the real and imaginary parts of the quasi-polynomial, which are evaluated over the areas of the region outside those free of zeros.     

The asymptotic analysis of multiple imaginary characteristic roots for LTI delayed systems based on Puiseux–Newton diagram

The paper proposes a novel procedure for the asymptotic expansions of root loci around multiple imaginary roots of an exponential polynomial, which is necessary for the stability analysis of the LTI systems with commensurate delays. With the LTI delay systems given as exponential polynomials (also called quasi-polynomial), we seek to characterise the asymptotic behaviours of the characteristic roots of such systems in an algebraic way and determine whether the imaginary roots cross from one half-plane into another or only touch the imaginary axis. According to the Weierstrass preparation theorem, the quasi-polynomial equation is equivalent to an algebraic equation in the neighbourhood of a singular point. Furthermore, our result gives an explicit expression of the coefficients of the algebraic equation in infinite power series of delay parameter, and the determinations of such power series coefficients refer to the computation of residues of memorphic functions. Subsequently, the classic Puiseux–Newton diagram algorithm can be used to calculate the algebraic expansions of the reduced equation directly. Thus, the asymptotic behaviours of root loci around singular points of the quasi-polynomial equation are obtained. Some illustrative simulations are given to check the validity of the proposed method on asymptotic analysis with a powerful software.     

Stable scheduling policies for flexible manufacturing systems

In this brief note we provide a new analysis of the transient behavior of the clear-a-fraction policy of Perkins and Kumar (1989). In addition, we show that a new “clear-average-oldest-buffer” policy and a “random part selection” policy (of which “first-come-first-served” is a special case) are stable. Finally, we introduce a stable and efficient “stream modifier” that can be used to obtain network level stability results     

Approximation Algorithms for Minimizing Average Distortion

This paper considers embeddings f of arbitrary finite metrics into the line metric ℜ so that none of the distances is shrunk by the embedding f; the quantity of interest is the factor by which the average distance in the metric is stretched. We call this quantity the average distortion of the non-contracting map f. We prove that finding the best embedding of even a tree metric into a line metric to minimize the average distortion is NP-hard, and hence focus on approximating the average distortion of the best possible embedding for the given input metric. We give a constant-factor approximation for the problem of embedding general metrics into the line metric. For the case of n-point tree metrics, we provide a quasi-polynomial time approximation scheme which outputs an embedding with distortion at most (1 + ε) times the optimum in time n^{O(log n/ε^2)}. Finally, when the average distortion is measured only over the endpoints of the edges of an input tree metric, we show how to exploit the structure of tree metrics to give an exact solution in polynomial time.