A combinatorial algorithm for max csp

We consider the problem max csp over multi-valued domains with variables ranging over sets of size s_i?s and constraints involving k_j?k variables. We study two algorithms with approximation ratios A and B, respectively, so we obtain a solution with approximation ratio max(A,B).The first algorithm is based on the linear programming algorithm of Serna, Trevisan, and Xhafa [Proc. 15th Annual Symp. on Theoret. Aspects of Comput. Sci., 1998, pp. 488-498] and gives ratio A which is bounded below by s^1−k. For k=2, our bound in terms of the individual set sizes is the minimum over all constraints involving two variables of , where s₁ and s₂ are the set sizes for the two variables.We then give a simple combinatorial algorithm which has approximation ratio B, with B>A/e. The bound is greater than s^1−k/e in general, and greater than s^1−k(1−(s−1)/2(k−1)) for s?k−1, thus close to the s^1−k linear programming bound for large k. For k=2, the bound is if s=2, 1/2(s−1) if s?3, and in general greater than the minimum of 1/4s₁+1/4s₂ over constraints with set sizes s₁ and s₂, thus within a factor of two of the linear programming bound.For the case of k=2 and s=2 we prove an integrality gap of . This shows that our analysis is tight for any method that uses the linear programming upper bound.     

Explicit convergence rates for MRAC-type systems

It is well known since many years ago that for the linear time-varying system , with A Hurwitz, and B(t) bounded and globally Lipschitz, it is necessary and sufficient for global exponential stability, that B(t) satisfy the so-called persistency of excitation condition. In this note, we revisit this question and provide explicit bounds for the convergence rate and on the overshoot of the transient behaviour of the solutions e(t), θ(t) as functions of the richness of B(·). We believe that the result that we present is useful since knowing convergence rates aids in the construction of converse Lyapunov functions. Moreover, the type of systems that we study here appear for instance in model reference adaptive control (MRAC).     

Spectral radius minimization for optimal average consensus and output feedback stabilization

In this paper, we consider two problems which can be posed as spectral radius minimization problems. Firstly, we consider the fastest average agreement problem on multi-agent networks adopting a linear information exchange protocol. Mathematically, this problem can be cast as finding an optimal such that x(k+1)=Wx(k), , and W∈S(E). Here, is the value possessed by the agents at the kth time step, is an all-one vector and S(E) is the set of real matrices in with zeros at the same positions specified by a network graph G(V,E), where V is the set of agents and E is the set of communication links between agents. The optimal W is such that the spectral radius is minimized. To this end, we consider two numerical solution schemes: one using the qth-order spectral norm (2-norm) minimization (q-SNM) and the other gradient sampling (GS), inspired by the methods proposed in [Burke, J., Lewis, A., & Overton, M. (2002). Two numerical methods for optimizing matrix stability. Linear Algebra and its Applications, 351-352, 117-145; Xiao, L., & Boyd, S. (2004). Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1), 65-78]. In this context, we theoretically show that when E is symmetric, i.e. no information flow from the ith to the jth agent implies no information flow from the jth to the ith agent, the solution from the 1-SNM method can be chosen to be symmetric and is a local minimum of the function . Numerically, we show that the q-SNM method performs much better than the GS method when E is not symmetric. Secondly, we consider the famous static output feedback stabilization problem, which is considered to be a hard problem (some think NP-hard): for a given linear system (A,B,C), find a stabilizing control gain K such that all the real parts of the eigenvalues of A+BKC are strictly negative. In spite of its computational complexity, we show numerically that q-SNM successfully yields stabilizing controllers for several benchmark problems with little effort.     

On domination number of Cartesian product of directed cycles

Let γ(G) denote the domination number of a digraph G and let Cm□Cn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In this paper, we determine the exact values: γ(C₂□Cn)=n; γ(C₃□Cn)=n if , otherwise, γ(C₃□Cn)=n+1; if , otherwise, .     

The size and depth of layered Boolean circuits

We consider the relationship between size and depth for layered Boolean circuits and synchronous circuits. We show that every layered Boolean circuit of size s can be simulated by a layered Boolean circuit of depth . For synchronous circuits of size s, we obtain simulations of depth . The best known result so far was by Paterson and Valiant (1976) [17], and Dymond and Tompa (1985) [6], which holds for general Boolean circuits and states that , where C(f) and D(f) are the minimum size and depth, respectively, of Boolean circuits computing f. The proof of our main result uses an adaptive strategy based on the two-person pebble game introduced by Dymond and Tompa (1985) [6]. Improving any of our results by polylog factors would immediately improve the bounds for general circuits.     

Delay-dependent stabilization of linear systems with time-varying state and input delays

The integral-inequality method is a new way of tackling the delay-dependent stabilization problem for a linear system with time-varying state and input delays: . In this paper, a new integral inequality for quadratic terms is first established. Then, it is used to obtain a new state- and input-delay-dependent criterion that ensures the stability of the closed-loop system with a memoryless state feedback controller. Finally, some numerical examples are presented to demonstrate that control systems designed based on the criterion are effective, even though neither (A,B₁) nor (A+A₁,B₁) is stabilizable.     

A note on balanced immunity

For a finite alphabet ∑ we define a binary relation on \(2^{\Sigma *} \times 2^{2^{\Sigma ^* } } \) , called balanced immunity. A setB ? ∑* is said to be balancedC-immune (with respect to a classC ? 2^Σ* of sets) iff, for all infiniteL εC, $$\mathop {\lim }\limits_{n \to \infty } \left| {L^{ \leqslant n} \cap B} \right|/\left| {L^{ \leqslant n} } \right| = \tfrac{1}{2}$$ Balanced immunity implies bi-immunity and in natural cases randomness. We give a general method to find a balanced immune set'B for any countable classC and prove that, fors(n) =o(t(n)) andt(n) >n, there is aB εSPACE(t(n)), which is balanced immune forSPACE(s(n)), both in the deterministic and nondeterministic case.     

Stability of switching infinite-dimensional systems

In this note, we generalize the results from Narendra and Balakrishnan (IEEE Trans. Automatic Control 39 (1994) 2469) to the infinite-dimensional system theoretic setting. The paper gives results on the stability of a switching system of the form , i∈{1,2}, when the infinitesimal generators A₁ and A₂ commute. In addition, the existence of a common quadratic Lyapunov function is demonstrated.     

Computation of zeros of linear multivariable systems

Several algorithms have been proposed in the literature for the computation of the zeros of a linear system described by a state-space model {A, B, C, D}. In this paper we discuss the numerical properties of a new algorithm and compare it with some earlier techniques of computing zeros. The method is a modified version of Silverman's structure algorithm and is shown to be backward stable in a rigorous sense. The approach is shown to handle both nonsquare and/or degenerate systems. Several numerical examples are also provided.     

Descendants of a recognizable tree language for sets of linear monadic term rewrite rules

For a tree language L and a set S of term rewrite rules over Σ, the descendant of L for S is the set S^∗(L) of trees reachable from a tree in L by rewriting in S. For a recognizable tree language L, we study the set D(L) of descendants of L for all sets of linear monadic term rewrite rules over Σ. We show that D(L) is finite. For each tree automaton A over Σ, we can effectively construct a set {R₁,…,Rk} of linear monadic term rewrite systems over Σ such that and for any 1?i<j?k, .