Existence Theorems for Generalized Hammerstein Equations

In this paper we obtain existence theorems for generalized Hammerstein-type equations K(u)Nu + u = 0, where for each u in the dual X* of a real reflexive Banach space X, K(u): X -- X* is a bounded linear map and N: X* - X is any map (possibly nonlinear). The method we adopt is totally different from the methods adopted so far in solving these equations. Our results in the reflexive spacegeneralize corresponding results of Petry and Schillings.

On some results of A. E. Livingston and coefficient problems for concave univalent functions

We consider functions that map the open unit disc conformally onto the complement of a bounded convex set. We call these functions concave univalent functions. In 1994, Livingston presented a characterization for these functions. In this paper, we observe that there is a minor flaw with this characterization. We obtain certain sharp estimates and the exact set of variability involving Laurent and Taylor coefficients for concave functions. We also present the exact set of variability of the linear combination of certain successive Taylor coefficients of concave functions.

Euclideanization, topological theories, higher dimensions and all that

It is shown that the euclideanized Yukawa theory, with the Dirac fermion belonging to an irreducible representation of the Lorentz group, is not bounded from below. A one parameter family of supersymmetric actions is presented which continuously interpolates between the N = 2 SSYM and the N = 2 supersymmetric topological theory. In order to obtain a theory which is bounded from below and satisfies Osterwalder-Schrader positivity, the Dirac fermion should belong to a reducible representation of the Lorentz group and the scalar fields have to be reinterpreted as the extra components of a higher dimensional vector field.

Search Strategies for Multiple UAV Search and Destroy Missions

Multiple UAVs are deployed to carry out a search and destroy mission in a bounded region. The UAVs have limited sensor range and can carry limited resources which reduce with use. The UAVs perform a search task to detect targets. When a target is detected which requires different type and quantities of resources to completely destroy, then a team of UAVs called as a coalition is formed to attack the target. The coalition members have to modify their route to attack the target, in the process, the search task is affected, as search and destroy tasks are coupled. The performance of the mission is a function of the search and the task allocation strategies. Therefore, for a given task allocation strategy, we need to devise search strategies that are efficient. In this paper, we propose three different search strategies namely; random search strategy, lanes based search strategy and grid based search strategy and analyze their performance through Monte-Carlo simulations. The results show that the grid based search strategy performs the best but with high information overhead.

Popular matchings with variable item copies

We consider the problem of matching people to items, where each person ranks a subset of items in an order of preference, possibly involving ties. There are several notions of optimality about how to best match a person to an item; in particular, popularity is a natural and appealing notion of optimality. A matching M* is popular if there is no matching M such that the number of people who prefer M to M* exceeds the number who prefer M* to M. However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not admit popular matchings. This motivates the following extension of the popular matchings problem: Given a graph G = (A U 3, E) where A is the set of people and 2 is the set of items, and a list < c(1),...., c(vertical bar B vertical bar)> denoting upper bounds on the number of copies of each item, does there exist < x(1),...., x(vertical bar B vertical bar)> such that for each i, having x(i) copies of the i-th item, where 1 <= xi <= c(i), enables the resulting graph to admit a popular matching? In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each c(i) is 1 or 2. We show a polynomial time algorithm for a variant of the above problem where the total increase in copies is bounded by an integer k. (C) 2011 Elsevier B.V. All rights reserved.

A Flexible Class of Regenerating Codes for Distributed Storage

In the distributed storage setting introduced by Dimakis et al., B units of data are stored across n nodes in the network in such a way that the data can be recovered by connecting to any k nodes. Additionally one can repair a failed node by connecting to any d nodes while downloading at most beta units of data from each node. In this paper, we introduce a flexible framework in which the data can be recovered by connecting to any number of nodes as long as the total amount of data downloaded is at least B. Similarly, regeneration of a failed node is possible if the new node connects to the network using links whose individual capacity is bounded above by beta(max) and whose sum capacity equals or exceeds a predetermined parameter gamma. In this flexible setting, we obtain the cut-set lower bound on the repair bandwidth along with a constructive proof for the existence of codes meeting this bound for all values of the parameters. An explicit code construction is provided which is optimal in certain parameter regimes.

Goal Seeking for Robots in Unknown Environments

We consider the problem of goal seeking by robots in unknown environments. We present a frontier based algorithm for finding a route to a goal in a fully unknown environment, where information about the goal region (GR), the region where the goal is most likely to be located, is available. Our algorithm efficiently chooses the best candidate frontier cell, which is on the boundary between explored space and unexplored space, having the maximum ``goal seeking index'', to reach the goal in minimal number of moves. Modification of the algorithm is also proposed to further reduce the number of moves toward the goal. The algorithm has been tested extensively in simulation runs and results demonstrate that the algorithm effectively directs the robot to the goal and completes the search task in minimal number of moves in bounded as well as unbounded environments. The algorithm is shown to perform as well as a state of the art agent centered search algorithm RTAA*, in cluttered environments if exact location of the goal is known at the beginning of the mission and is shown to perform better in uncluttered environments.

A characteristic based numerical method with tracking for nonlinear wave equations

Many physical problems can be modeled by scalar, first-order, nonlinear, hyperbolic, partial differential equations (PDEs). The solutions to these PDEs often contain shock and rarefaction waves, where the solution becomes discontinuous or has a discontinuous derivative. One can encounter difficulties using traditional finite difference methods to solve these equations. In this paper, we introduce a numerical method for solving first-order scalar wave equations. The method involves solving ordinary differential equations (ODEs) to advance the solution along the characteristics and to propagate the characteristics in time. Shocks are created when characteristics cross, and the shocks are then propagated by applying analytical jump conditions. New characteristics are inserted in spreading rarefaction fans. New characteristics are also inserted when values on adjacent characteristics lie on opposite sides of an inflection point of a nonconvex flux function, Solutions along characteristics are propagated using a standard fourth-order Runge-Kutta ODE solver. Shocks waves are kept perfectly sharp. In addition, shock locations and velocities are determined without analyzing smeared profiles or taking numerical derivatives. In order to test the numerical method, we study analytically a particular class of nonlinear hyperbolic PDEs, deriving closed form solutions for certain special initial data. We also find bounded, smooth, self-similar solutions using group theoretic methods. The numerical method is validated against these analytical results. In addition, we compare the errors in our method with those using the Lax-Wendroff method for both convex and nonconvex flux functions. Finally, we apply the method to solve a PDE with a convex flux function describing the development of a thin liquid film on a horizontally rotating disk and a PDE with a nonconvex flux function, arising in a problem concerning flow in an underground reservoir.

Hierarchies of circuit classes that are closed under complement

We examine three hierarchies of circuit classes and show they are closed under complementation. (1) The class of languages recognized by a family of polynomial size skew circuits with width O(w), are closed under complement. (2) The class of languages recognized by family of polynomial size circuits with width O(w) and polynomial tree-size, are closed under complement. (3) The class of languages recognized by a family of polynomial size, O(log(n)) depth, bounded AND fan-in with OR fan-in f (f⩾log(n)) circuits are closed under complement. These improve upon the results of (i) Immerman (1988) and Szelepcsenyi (1988), who show that 𝒩L𝒪𝒢 is closed under complementation, and (ii) Borodin et al. (1989), who show that L𝒪𝒢𝒞ℱL is closed under complement

On boundedness and parallel to center dot parallel to(p) continuity of second quantisation

in this short note, we determine precisely which operators have the property that their (full, symmetric or antisymmetric) second quantisation is an operator which is bounded or belongs to one of the various Schatten ideals; we also note that in 'the interior' of the natural domain, the second quantisation is a continuous map.

A polynomial bound on the number of light cycles in an undirected graph

Let G be an undirected graph with a positive real weight on each edge. It is shown that the number of minimum-weight cycles of G is bounded above by a polynomial in the number of edges of G. A similar bound holds if we wish to count the number of cycles with weight at most a constant multiple of the minimum weight of a cycle of G.

Coherence of the real symmetric Hardy algebra

Let D denote the open unit disk in C centered at 0. Let H-R(infinity) denote the set of all bounded and holomorphic functions defined in D that also satisfy f(z) = <(f <(z)over bar>)over bar> for all z is an element of D. It is shown that H-R(infinity) is a coherent ring.

Redistribution Mechanisms for Assignment of Heterogeneous Objects

There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. When the objects are identical, this problem has been solved which we refer as WCO mechanism. We measure the performance of such mechanisms by the redistribution index. We first prove an impossibility theorem which rules out linear rebate functions with non-zero redistribution index in heterogeneous object assignment. Motivated by this theorem,we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with non-zero redistribution index are possible when the valuations for the objects have a certain type of relationship and we design a mechanism with linear rebate function that is worst case optimal. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed. We extend the rebate functions of the WCO mechanism to heterogeneous objects assignment and conjecture them to be worst case optimal.

Solving linear programming problems exactly

A linear programming problem in an inequality form having a bounded solution is solved error-free using an algorithm that sorts the inequalities, removes the redundant ones, and uses the p-adic arithmetic. (C) Elsevier Science Inc., 1997

The complexity of certain incremental code generation problems

This paper looks at the complexity of four different incremental problems. The following are the problems considered: (1) Interval partitioning of a flow graph (2) Breadth first search (BFS) of a directed graph (3) Lexicographic depth first search (DFS) of a directed graph (4) Constructing the postorder listing of the nodes of a binary tree. The last problem arises out of the need for incrementally computing the Sethi-Ullman (SU) ordering [1] of the subtrees of a tree after it has undergone changes of a given type. These problems are among those that claimed our attention in the process of our designing algorithmic techniques for incremental code generation. BFS and DFS have certainly numerous other applications, but as far as our work is concerned, incremental code generation is the common thread linking these problems. The study of the complexity of these problems is done from two different perspectives. In [2] is given the theory of incremental relative lower bounds (IRLB). We use this theory to derive the IRLBs of the first three problems. Then we use the notion of a bounded incremental algorithm [4] to prove the unboundedness of the fourth problem with respect to the locally persistent model of computation. Possibly, the lower bound result for lexicographic DFS is the most interesting. In [5] the author considers lexicographic DFS to be a problem for which the incremental version may require the recomputation of the entire solution from scratch. In that sense, our IRLB result provides further evidence for this possibility with the proviso that the incremental DFS algorithms considered be ones that do not require too much of preprocessing.