Coderivative calculus and metric regularity for constraint and variational systems

This paper provides new developments in generalized differentiation theory of variational analysis with their applications to metric regularity of parameterized constraint and variational systems in finite-dimensional and infinite-dimensional spaces. Our approach to the study of metric regularity for these two major classes of parametric systems is based on appropriate coderivative constructions for set-valued mappings and on extended calculus rules supporting their computation and estimation. The main attention is paid in this paper to the so-called reversed mixed coderivative, which is of crucial importance for efficient pointwise characterizations of metric regularity in the general framework of set-valued mappings between infinite-dimensional spaces. We develop new calculus results for the latter coderivative that allow us to compute it for large classes of parametric constraint and variational systems. On this basis we derive verifiable sufficient conditions, necessary conditions as well as complete characterizations for metric regularity of such systems with computing the corresponding exact bounds of metric regularity constants/moduli. This approach allows us to reveal general settings in which metric regularity fails for major classes of parametric variational systems. Furthermore, the developed coderivative calculus leads us also to establishing new formulas for computing the radius of metric regularity for constraint and variational systems, which characterize the maximal region of preserving metric regularity under linear (and other types of) perturbations and are closely related to conditioning aspects of optimization.     

Wavelet Characterizations for Anisotropic Besov Spaces

The goal of this paper is to provide wavelet characterizations for anisotropic Besov spaces. Depending on the anisotropy, appropriate biorthogonal tensor product bases are introduced and Jackson and Bernstein estimates are proved for two-parameter families of finite-dimensional spaces. These estimates lead to characterizations for anisotropic Besov spaces by anisotropy-dependent linear approximation spaces and lead further on to interpolation and embedding results. Finally, wavelet characterizations for anisotropic Besov spaces with respect to L_p-spaces with 0<p<∞ are derived.     

All-shortest-path 2-interval routing is NP-complete

k-Interval Routing Scheme (k-IRS) is a compact routing method that allows up to k interval labels to be assigned to an arc. A fundamental problem is to characterize the networks that admit k-IRS. All of the problems related to single-shortest-path k-IRS have already been shown to be NP-complete. For all-shortest-path k-IRS, the characterization problems have been proved to be NP-complete for every k≥3, and remain open for k=1,2. In this paper, we close the open case of k=2 by showing that it is NP-complete to decide whether a graph admits an all-shortest-path 2-IRS. The same proof is also valid for all-shortest-path Strict 2-IRS. All-shortest-path Strict k-IRS is previously known to be polynomial for k=1, open for k=2,3, and NP-complete for every constant k≥4.     

The Logical vs. the Ontological Understanding of Conditions

According to the truth-functional analysis of conditions, to be ‘necessary for’ and ‘sufficient for’ are converse relations. From this, it follows that to be ‘necessary and sufficient for’ is a symmetric relation, that is, that if P is a necessary and sufficient condition for Q, then Q is a necessary and sufficient condition for P. This view is contrary to common sense. In this paper, I point out that it is also contrary to a widely accepted ontological view of conditions, according to which if P is a necessary and sufficient condition for Q, then Q is in no sense a condition for P; it is a mere consequence of P.     

Number-theoretic properties of certain CR mappings

We first prove a uniqueness result for certain group-invariant CR mappings to hyperquadrics. For cyclic groups these mappings lead to a collection of polynomials ƒ_p,q (with integer coefficients) in two variables; here p and q are positive integers. We use the uniqueness result to prove some surprising number-theoretic results about the ƒ_p,q, in particular, ƒ_p,q is congruent to x^P + y^P modulo (p) (for P ≥ 2) if and only if p is prime. We also determine recurrence relations for these polynomials for q ≤ 3 and determine a functional equation for a generating function. Finally, we discuss the invariant polynomials that arise for certain representations of dihedral groups to illustrate the non-Abelian case.     

Smooth and Nonsmooth Calderón-Zygmund Type Decompositions for Morrey Spaces

It is shown that it is possible to construct an analogue of the Calderón-Zygmund decomposition for the Morrey spaces Mor_λ for the entire interval λ ∈ (0,1]. Moreover, for λ ∈ (1-,1] it is possible to construct a smooth analogue of the Calderón-Zygmund decomposition. The reason why we do not have any smooth analogues for the entire interval λ ∈ (0,1] is related to the following interesting property of cubes in the Whitney decomposition lemma: The sum of the volumes of Whitney cubes to the power λ is equal to infinity for λ ∈ (0,1-(1/n)].     

BV-Ellipticity and Lower Semicontinuity of Surface Energy of Caccioppoli Partitions of ℝ n

We give a new proof that BV-ellipticity is sufficient for lower semicontinuity of surface energy of Caccioppoli partitions of ? ⁿ , for any n≥2, with respect to convergence in volume. BV-ellipticity, introduced by L. Ambrosio and A. Braides two decades ago, is the only condition known to be necessary and sufficient for lower semicontinuity in the context of Caccioppoli partitions of ? ⁿ ; it is analogous, for this setting, to C.B. Morrey’s quasi-convexity. We also show, for the first time, that BV-ellipticity suffices for lower semicontinuity with respect to weaker notions of convergence involving the weak and flat topologies on integral currents.     

Complete tree subset difference broadcast encryption scheme and its analysis

The subset difference (SD) method proposed by Naor, Naor and Lotspiech is the most popular broadcast encryption (BE) scheme. It is suitable for real-time applications like Pay-TV and has been suggested for use by the AACS standard for digital rights management in Blu-Ray and HD-DVD discs. The SD method assumes the number of users to be a power of two. We propose the complete tree subset difference (CTSD) method that allows the system to support an arbitrary number of users. In particular, it subsumes the SD method and all results proved for the CTSD method also hold for the SD method. Recurrences are obtained for the CTSD scheme to count the number, N(n, r, h), of possible ways r users in the system of n users can be revoked to result in a transmission overhead or header length of h. The recurrences lead to a polynomial time dynamic programming algorithm for computing N(n, r, h). Further, they provide bounds on the maximum possible header length. A probabilistic analysis is performed to obtain an O(r log n) time algorithm to compute the expected header length in the CTSD scheme. Further, for the SD scheme we obtain an explicit limiting upper bound on the expected header length.     

Crossing points of distributions and a theorem that relates them to second order stochastic dominance

We state formal definitions for crossing points in pairs of distributions and give a detailed proof of a theorem that relates those points to the second order stochastic dominance (SSD). The theorem states that the fulfillment of the area balance conditions for SSD at the t values that correspond to crossing points, and at the limit t→∞, is a necessary and sufficient condition for its fulfillment at all t: {−∞<t<∞}, as required for the existence of SSD. We provide examples for the application of the theorem in the case of continuous distributions, including a continuous counter example to prove that the Mean-Variance criterion is not sufficient to state preferences under risk aversion.     

On energy estimates for second order hyperbolic equations with Levi conditions for higher order regularity

We consider energy estimates for second order homogeneous hyperbolic equations with time dependent coefficients. The property of energy conservation, which holds in the case of constant coefficients, does not hold in general for variable coefficients; in fact, the energy can be unbounded as t → ∞ in this case. The conditions to the coefficients for the generalized energy conservation (GEC), which is an equivalence of the energy uniformly with respect to time, has been studied precisely for wave type equations, that is, only the propagation speed is variable. However, it is not true that the same conditions to the coefficients conclude (GEC) for general homogeneous hyperbolic equations. The main purpose of this paper is to give additional conditions to the coefficients which provide (GEC); they will be called as C ^k -type Levi conditions due to the essentially same meaning of usual Levi condition for the well-posedness of weakly hyperbolic equations.     

Research announcement on gaierkirfs method for a class of integra equations of the first kind

Let X and Y be locally convex spaces with K a closed convex cone in X Necessary and sufficient conditions are given for the image AK to be closed in Ywhen A:X→Y is a continuous linear map. This result is used to generalize a theorem of Abrams to infinite dimensional spaces and also to give sufficient conditions for the Hurwicz version of the Farkas lemma for locally convex spaces to hold.     

Formulas for sums of powers of integers by functional equations

This paper presents a direct and simple approach to obtaining the formulas forS _k(n)= 1 ^k + 2 ^k + ... +n ^k wheren andk are nonnegative integers. A functional equation is written based on the functional properties ofS _k (n) and several methods of solution are presented. These lead to several recurrence relations for the functions and a simple one-step differential-recurrence relation from which the polynomials can easily be computed successively. Arbitrary constants which arise are (almost) the Bernoulli numbers when evaluated and identities for these modified Bernoulli numbers are obtained. The functional equation for the formulas leads to another functional equation for the generating function for these formulas and this is used to obtain the generating functions for theS _k 's and for the modified Bernoulli numbers. This leads to an explicit representation, not a recurrence relation, for the modified Bernoulli numbers which then yields an explicit formula for eachS _k not depending on the earlier ones. This functional equation approach has been and can be applied to more general types of arithmetic sequences and many other types of combinatorial functions, sequences, and problems.     

Optimal location with equitable loads

The problem considered in this paper is to find p locations for p facilities such that the weights attracted to each facility will be as close as possible to one another. We model this problem as minimizing the maximum among all the total weights attracted to the various facilities. We propose solution procedures for the problem on a network, and for the special cases of the problem on a tree or on a path. The complexity of the problem is analyzed, O(n) algorithms and an O(pn ³) dynamic programming algorithm are proposed for the problem on a path respectively for p=2 and p>2 facilities. Heuristic algorithms (two types of a steepest descent approach and tabu search) are proposed for its solution. Extensive computational results are presented.     

MEXIT: Maximal un-coupling times for stochastic processes

Classical coupling constructions arrange for copies of the same Markov process started at two different initial states to become equal as soon as possible. In this paper, we consider an alternative coupling framework in which one seeks to arrange for two different Markov (or other stochastic) processes to remain equal for as long as possible, when started in the same state. We refer to this “un-coupling” or “maximal agreement” construction as MEXIT, standing for “maximal exit”. After highlighting the importance of un-coupling arguments in a few key statistical and probabilistic settings, we develop an explicit MEXIT construction for stochastic processes in discrete time with countable state-space. This construction is generalized to random processes on general state-space running in continuous time, and then exemplified by discussion of MEXIT for Brownian motions with two different constant drifts.     

Motion Planning for Multiple Robots

We study the motion-planning problem for pairs and triples of robots operating in a shared workspace containing n obstacles. A standard way to solve such problems is to view the collection of robots as one composite robot, whose number of degrees of freedom is d , the sum of the numbers of degrees of freedom of the individual robots. We show that it is sufficient to consider a constant number of robot systems whose number of degrees of freedom is at most d-1 for pairs of robots, and d-2 for triples. (The result for a pair assumes that the sum of the number of degrees of freedom of the robots constituting the pair reduces by at least one if the robots are required to stay in contact; for triples a similar assumption is made. Moreover, for triples we need to assume that a solution with positive clearance exists.) We use this to obtain an O(n ^d ) time algorithm to solve the motion-planning problem for a pair of robots; this is one order of magnitude faster than what the standard method would give. For a triple of robots the running time becomes O(n ^d-1 ) , which is two orders of magnitude faster than the standard method. We also apply our method to the case of a collection of bounded-reach robots moving in a low-density environment. Here the running time of our algorithm becomes O(n log n) both for pairs and triples. Received August 10, 1998, and in revised form February 17, 1999.     

Steiner trees for fixed orientation metrics

We consider the problem of constructing Steiner minimum trees for a metric defined by a polygonal unit circle (corresponding to σ ≥ 2 weighted legal orientations in the plane). A linear-time algorithm to enumerate all angle configurations for degree three Steiner points is given. We provide a simple proof that the angle configuration for a Steiner point extends to all Steiner points in a full Steiner minimum tree, such that at most six orientations suffice for edges in a full Steiner minimum tree. We show that the concept of canonical forms originally introduced for the uniform orientation metric generalises to the fixed orientation metric. Finally, we give an O(σ n) time algorithm to compute a Steiner minimum tree for a given full Steiner topology with n terminal leaves.     

A constructive approach to Noether's problem

A general method is developed to attack Noether's Problem constructively by trying to find minimal bases consisting of rational invariants which are quotients of polynomials of small degrees. This approach turns out to be successful for many small groups and for most of the classical groups with their natural representations. The applications include affirmative answers to Noether's Problem for the conformal symplectic groups CSp _2n (q), for the simple subgroups Ω _n (q) of the orthogonal groups forn andq odd, for some other subgroups of orthogonal groups and for the special unitary groups SU _n (q ²). The author was supported by the Graduate College “Modelling and Scientific Computing in Mathematics and Science” during this work     

An existence and uniqueness criterion for solutions of boundary value problems

In this paper a technique is developed for the study of the existence and uniqueness of solutions to nth order ordinary differential equations satisfying n-point boundary conditions. Liapunov-like functions are employed to determine the existence and uniqueness of solutions to linear equations satisfying the boundary conditions, and these solutions are in turn used to determine existence for the general nonlinear case. A by-product of this technique is a matching technique for linear equations by which solutions of certain k-point boundary value problems (k < n) can be matched to extend the interval of existence for solutions to the n-point problem.     

Distributed personnel scheduling—negotiation among scheduling agents

This paper introduces a model for Distributed Employee Timetabling Problems (DisETPs) and proposes a general architecture for solving DisETPs by using a Multi Agent System (MAS) paradigm. The architecture is composed of a set of autonomous software Scheduling Agents (SAs) that solve the Employee Timetabling Problems (ETP) for each department. Each agent has its own local ETP problem and its own goals. The Scheduling Agents must coordinate their local solution with the other agents in order to achieve a global solution for the whole organization that yields a better result with respect to the organization’s global targets. To achieve a coherent and consistent global solution, the SAs make use of a sophisticated negotiation protocol among scheduling agents that always ends in an agreement (not ensured to be optimal). The main functionalities of this protocol are agent to agent relation definition, a mechanism to approve a chain of Request for Changes and an electronic marketplace for bidding on preferred common time slots. Experimental analysis of the implemented Multi Agent System for the Soroka medical center is presented. The results of our study indicate that the proposed framework has the potential to reduce the cost of transportation for the nurses that traveling to and from the hospital.