Complexity of the min–max (regret) versions of min cut problems

This paper investigates the complexity of the min–max and min–max regret versions of the min s–t cut and min cut problems. Even if the underlying problems are closely related and both polynomial, the complexities of their min–max and min–max regret versions, for a constant number of scenarios, are quite contrasted since they are respectively strongly NP-hard and polynomial. However, for a non-constant number of scenarios, these versions become strongly NP-hard for both problems. In the interval scenario case, min–max versions are trivially polynomial. Moreover, for min–max regret versions, we obtain the same contrasted results as for a constant number of scenarios: min–max regret min s–t cut is strongly NP-hard whereas min–max regret min cut is polynomial.     

Strong Haagerup inequalities with operator coefficients

We prove a Strong Haagerup inequality with operator coefficients. If for an integer d, denotes the subspace of the von Neumann algebra of a free group F_I spanned by the words of length d in the generators (but not their inverses), then we provide in this paper an explicit upper bound on the norm on , which improves and generalizes previous results by Kemp–Speicher (in the scalar case) and Buchholz and Parcet–Pisier (in the non-holomorphic setting). Namely the norm of an element of the form ∑_{i=(i1,…,id)}a_iλ(g_i1g_id) is less than , where M₀,…,M_d are d+1 different block-matrices naturally constructed from the family (a_i)_iI^d for each decomposition of I^dI^l×I^d−l with l=0,…,d. It is also proved that the same inequality holds for the norms in the associated non-commutative L_p spaces when p is an even integer, pd and when the generators of the free group are more generally replaced by *-free -diagonal operators. In particular it applies to the case of free circular operators. We also get inequalities for the non-holomorphic case, with a rate of growth of order d+1 as for the classical Haagerup inequality. The proof is of combinatorial nature and is based on the definition and study of a symmetrization process for partitions.     

On Bernstein–Markov-type inequalities for multivariate polynomials in -norm

Bernstein–Markov-type inequalities provide estimates for the norms of derivatives of algebraic and trigonometric polynomials. They play an important role in Approximation Theory since they are widely used for verifying inverse theorems of approximation. In the past decades these inequalities were extended to the multivariate setting, but the main emphasis so far was on the uniform norm. It is considerably harder to derive Bernstein–Markov-type inequalities in the L_q-norm, and it requires introduction of new methods. In this paper we verify certain Bernstein–Markov-type inequalities in L_q-norm on convex and star-like domains. Special attention is given to the question of how the geometry of the domain affects the corresponding estimates.     

A quantitative version of Trotter's approximation theorem

A quantitative version, based on modified K-functionals, of the classical Trotter's theorem concerning the approximation of C₀-semigroups is presented. The result is applied to the study of the degree of convergence of the iterated Bernstein operators on the N-dimensional simplex to their limiting semigroup.     

Approximating the maximum 2- and 3-edge-colorable subgraph problems

For a fixed value of a parameter k≥2, the Maximum k-Edge-Colorable Subgraph Problem consists in finding k edge-disjoint matchings in a simple graph, with the goal of maximising the total number of edges used. The problem is known to be -hard for all k, but there exist polynomial time approximation algorithms with approximation ratios tending to 1 as k tends to infinity. Herein we propose improved approximation algorithms for the cases of k=2 and k=3, having approximation ratios of 5/6 and 4/5, respectively.     

Using fractional primal–dual to schedule split intervals with demands

We consider the problem of scheduling jobs that are given as groups of non-intersecting intervals on the real line. Each job j is associated with a t-interval (which consists of up to t segments, for some t≥1), a demand, d_j[0,1], and a weight, w(j). A feasible schedule is a collection of jobs such that, for every , the total demand of the jobs in the schedule whose t-interval contains s does not exceed 1. Our goal is to find a feasible schedule that maximizes the total weight of scheduled jobs.We present a 6t-approximation algorithm for this problem that uses a novel extension of the primal–dual schema called fractional primal–dual. The first step in a fractional primal–dual r-approximation algorithm is to compute an optimal solution, x^*, of an LP relaxation of the problem. Next, the algorithm produces an integral primal solution x, and a new LP, denoted by P′, that has the same objective function as the original problem, but contains inequalities that may not be valid with respect to the original problem. Moreover, x^* is a feasible solution of P′. The algorithm also computes a solution y to the dual of P′. The solution x is r-approximate, since its weight is bounded by the value of y divided by r.We present a fractional local ratio interpretation of our 6t-approximation algorithm. We also discuss the connection between fractional primal–dual and the fractional local ratio technique. Specifically, we show that the former is the primal–dual manifestation of the latter.     

Dynamical analysis of the transmission of seasonal diseases using the differential transformation method

The aim of this paper is to apply the differential transformation method (DTM) to solve systems of nonautonomous nonlinear differential equations that describe several epidemic models where the solutions exhibit periodic behavior due to the seasonal transmission rate. These models describe the dynamics of the different classes of the populations. Here the concept of DTM is introduced and then it is employed to derive a set of difference equations for this kind of epidemic models. The DTM is used here as an algorithm for approximating the solutions of the epidemic models in a sequence of time intervals. In order to show the efficiency of the method, the obtained numerical results are compared with the fourth-order Runge–Kutta method solutions. Numerical comparisons show that the DTM is accurate, easy to apply and the calculated solutions preserve the properties of the continuous models, such as the periodic behavior. Furthermore, it is showed that the DTM avoids large computational work and symbolic computation.     

A new exclusion test for finding the global minimum

Exclusion algorithms have been used recently to find all solutions of a system of nonlinear equations or to find the global minimum of a function over a compact domain. These algorithms are based on a minimization condition that can be applied to each cell in the domain. In this paper, we consider Lipschitz functions of order α and give a new minimization condition for the exclusion algorithm. Furthermore, convergence and complexity results are presented for such algorithm.     

Cone-valued Lyapunov functions and stability for impulsive functional differential equations

The stability criteria in terms of two measures for impulsive functional differential equations are established via cone-valued Lyapunov functions and Razumikhin technique. The stability can be deduced from the (Q₀,Q)-stability of comparison impulsive differential equations. An example is given to illustrate the advantages of the results obtained.     

Robust stabilization for uncertain switched impulsive control systems with state delay: An LMI approach

This paper deals with the problem of robust H_∞ state feedback stabilization for uncertain switched linear systems with state delay. The system under consideration involves time delay in the state, parameter uncertainties and nonlinear uncertainties. The parameter uncertainties are norm-bounded time-varying uncertainties which enter all the state matrices. The nonlinear uncertainties meet with the linear growth condition. In addition, the impulsive behavior is introduced into the given switched system, which results a novel class of hybrid and switched systems called switched impulsive control systems. Using the switched Lyapunov function approach, some sufficient conditions are developed to ensure the globally robust asymptotic stability and robust H_∞ disturbance attenuation performance in terms of certain linear matrix inequalities (LMIs). Not only the robustly stabilizing state feedback H_∞ controller and impulsive controller, but also the stabilizing switching law can be constructed by using the corresponding feasible solution to the LMIs. Finally, the effectiveness of the algorithms is illustrated with an example.     

On Rockafellar’s theorem using proximal point algorithm involving -maximal monotonicity framework

On the basis of the general framework of H-maximal monotonicity (also referred to as H-monotonicity in the literature), a generalization to Rockafellar’s theorem in the context of solving a general inclusion problem involving a set-valued maximal monotone operator using the proximal point algorithm in a Hilbert space setting is explored. As a matter of fact, this class of inclusion problems reduces to a class of variational inequalities as well as to a class of complementarity problems. This proximal point algorithm turns out to be of interest in the sense that it plays a significant role in certain computational methods of multipliers in nonlinear programming. The notion of H-maximal monotonicity generalizes the general theory of set-valued maximal monotone mappings to a new level. Furthermore, some results on general firm nonexpansiveness and resolvent mapping corresponding to H-monotonicity are also given.     

Three solutions for a differential inclusion problem involving the -Laplacian

In this paper we consider differential inclusion problem involving the p(x)-Laplacian of the type

Applying a version of the non-smooth three-critical-points theorem we obtain the existence of three solutions of the problem in .     

Accelerating gradient projection methods for -constrained signal recovery by steplength selection rules

We propose a new gradient projection algorithm that compares favorably with the fastest algorithms available to date for ℓ₁-constrained sparse recovery from noisy data, both in the compressed sensing and inverse problem frameworks. The method exploits a line-search along the feasible direction and an adaptive steplength selection based on recent strategies for the alternation of the well-known Barzilai–Borwein rules. The convergence of the proposed approach is discussed and a computational study on both well conditioned and ill-conditioned problems is carried out for performance evaluations in comparison with five other algorithms proposed in the literature.     

Linear information versus function evaluations for -approximation

We study algorithms for the approximation of functions, the error is measured in an L₂ norm. We consider the worst case setting for a general reproducing kernel Hilbert space of functions. We analyze algorithms that use standard information consisting in n function values and we are interested in the optimal order of convergence. This is the maximal exponent b for which the worst case error of such an algorithm is of order n^-b.Let p be the optimal order of convergence of all algorithms that may use arbitrary linear functionals, in contrast to function values only. So far it was not known whether p>b is possible, i.e., whether the approximation numbers or linear widths can be essentially smaller than the sampling numbers. This is (implicitly) posed as an open problem in the recent paper [F.Y. Kuo, G.W. Wasilowski, H. Woźniakowski, On the power of standard information for multivariate approximation in the worst case setting, J. Approx. Theory, to appear] where the authors prove that implies . Here we prove that the case and b=0 is possible, hence general linear information can be exponentially better than function evaluation. Since the case is quite different, it is still open whether b=p always holds in that case.     

Delay-dependent robust control for uncertain discrete-time singular systems with time-delays

The robust memoryless state feedback H_∞ control problem for uncertain time-delay discrete-time singular systems is discussed. Under a series of equivalent transformation, the equivalence of this problem and the robust state feedback H_∞ control problem for standard state-space uncertain time-delay discrete-time systems is presented. In terms of matrix inequality, the delay-dependent sufficient condition for the solution of this problem is given, the design method of the memoryless state feedback controller and the controller are also given.     

The behavior of best -approximations as . A counterexample of convergence

In the space of summable sequences we give an example of a one-dimensional affine subspace C such that the best L_p-approximations of 0 from C fail to converge as p↓1. We thus give an answer to this problem of convergence in infinite measure spaces.     

Formal systems of fuzzy logic and their fragments

Formal systems of fuzzy logic (including the well-known Łukasiewicz and Gödel–Dummett infinite-valued logics) are well-established logical systems and respected members of the broad family of the so-called substructural logics closely related to the famous logic BCK. The study of fragments of logical systems is an important issue of research in any class of non-classical logics. Here we study the fragments of nine prominent fuzzy logics to all sublanguages containing implication. However, the results achieved in the paper for those nine logics are usually corollaries of theorems with much wider scope of applicability. In particular, we show how many of these fragments are really distinct and we find axiomatic systems for most of them. In fact, we construct strongly separable axiomatic systems for eight of our nine logics. We also fully answer the question for which of the studied fragments the corresponding class of algebras forms a variety. Finally, we solve the problem how to axiomatize predicate versions of logics without the lattice disjunction (an essential connective in the usual axiomatic system of fuzzy predicate logics).     

Existence of periodic solutions for a fourth-order -Laplacian equation with a deviating argument

In this paper, we study the existence of periodic solutions for a fourth-order p-Laplacian differential equation with a deviating argument as follows:

[φ_p(u^″(t))]^″+f(u^″(t))+g(u(t−τ(t)))=e(t).