Computing input multiplicity in anonymous synchronous networks with dynamic faults

We consider the following problem: Each processor of the network has assigned a (not necessarily unique) input value. Determine the multiplicity of each input value. Solving this problem means any input-symmetric function (i.e., function not sensitive to permutations of its input values) can be computed. We consider an anonymous synchronous network of arbitrary topology, in which dynamic link faults [P. Fraigniaud, C. Peyrat, Inform. Process. Lett. 71 (1999) 115–119; N. Santoro, P. Widmayer, in: Proc. SIGAL'90, Tokyo, 1990, in: LNCS, Springer, Berlin, 1990, pp. 358–369] may occur.

An instance of this problem has been stated as an open problem by N. Santoro at the rump session of SIROCCO'98: Is it possible to distributively compute parity function (XOR) on anonymous hypercubes with dynamic faults?

We show that if the network size N (the number of processors) is known, the multiplicity of inputs (and thus any input-symmetric function) can be computed on any connected network. The time complexity depends on the details of the model and the amount of topological information, but it is always a low polynomial in N.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

On optimization of continuous-time Markov networks in distributed computing

The paper presents a new stochastic model for studying the optimization of functioning rules in distributed computing. In this model a network is represented by a finite number of continuous-time homogeneous Markov processes which are connected by relations between entries of their intensity matrices. Good functioning rules are those optimizing a guide function defined according to the context. Two specific optimization problems are studied: a problem of resource allocation with conflicts between processes, and a problem of access to shared resources. The latter is a linearly constrained nonconvex problem with an objective function which is a sum of ratios of linear functions of special form.     

Relay placement for fault tolerance in wireless networks in higher dimensions

In this paper we consider the problem of adding the smallest number of additional (relay) nodes to a network of static nodes with limited communication range so that the induced communication graph is 2-connected (we consider both edge and vertex connectivity). The problem is NP-hard. We develop algorithms that find close to optimal solutions for both edge and vertex connectivity. We prove the algorithms have an approximation ratio of 2M for nodes distributed in a d-dimensional Euclidean space, where M is the maximum node degree of a Minimum Spanning Tree in d dimensions using Euclidean metrics. In addition, our methods extend with the same approximation guarantees to a generalization when the locations of relays are required to avoid certain polygonal regions (obstacles).     

On the size of identifying codes in binary hypercubes

In this paper, we consider identifying codes in binary Hamming spaces Fn, i.e., in binary hypercubes. The concept of (r,??)-identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks.Let us denote by the smallest possible cardinality of an (r,??)-identifying code in Fn. In 2002, Honkala and Lobstein showed for ?=1 that

     

Infinite-horizon deterministic dynamic programming in discrete time: a monotone convergence principle and a penalty method

We consider infinite-horizon deterministic dynamic programming problems in discrete time. We show that the value function of such a problem is always a fixed point of a modified version of the Bellman operator. We also show that value iteration converges increasingly to the value function if the initial function is dominated by the value function, is mapped upward by the modified Bellman operator and satisfies a transversality-like condition. These results require no assumption except for the general framework of infinite-horizon deterministic dynamic programming. As an application, we show that the value function can be approximated by computing the value function of an unconstrained version of the problem with the constraint replaced by a penalty function.     

Lagrange multipliers for regular and singular problems in the calculus of variations

A Lagrange multiplier rule is presented for a variational problem of Bolza type under hypotheses that allow certain components of the coefficient matrices involved in the functional being minimized to fail to be integrable near an endpoint of the interval on which the relevant functions are defined. The problem is also addressed when all coefficients are of classL ², but not necessarily bounded. Applications are made to ascertain properties of functions providing equality to certain singular and regular integral inequalities appearing in the literature.     

A monotone iterative technique for stationary and time dependent problems in Banach spaces

An abstract monotone iterative method is developed for operators between partially ordered Banach spaces for the nonlinear problem Lu=Nu and the nonlinear time dependent problem u^′=(L+N)u. Under appropriate assumptions on L and N we obtain maximal and minimal solutions as limits of monotone sequences of solutions of linear problems. The results are illustrated by means of concrete examples.     

A model for speculation in a dynamic economy

The paper deals with speculation strategies in a dynamic economy, where “speculation” means participating in a market with the intention to gain a reward by first buying an item and thereafter selling it at a possibly higher price. By assuming that the states of the economy form a Markov chain the problem is modeled as a discrete time Markov decision process. The optimal strategies (which are pairs of stopping times) are identified. Under quite general conditions the optimal rule for the selling process turns out to be a control limit policy in both state of economy and time. Techniques for the computation of optimal strategies are presented; some numerical examples are also discussed. For a static economy closed-form solutions are given     

A criterion for time aggregation in intertemporal dynamic models

Nonlinear intertemporal general equilibrium models are hard to solve because of the dimensionality of the optimization problem involved. The computation of intertemporal general equilibria therefore calls for time-aggregation assumptions. A question then immediately arises: what criterion should one use to choose a sequence of possibly unequal time intervals in order to reduce the dimensionality of the optimization problem, yet keep under control the errors resulting from the numerical approximation of a continuous time process by a discrete time process? We propose one such criterion based on the current value of capital, which exploits near steady-state optimal dynamics. We show, using a parameterized version of the standard Ramsey—Koopmans—Cass model of optimal growth, that it outperforms alternative criterions used in the literature.     

On extension results for n-cyclically monotone operators in reflexive Banach spaces

In this paper we provide some extension results for n-cyclically monotone operators in reflexive Banach spaces by making use of the Fenchel duality. In this way we give a positive answer to a question posed by Bauschke and Wang (2007) [4].     

Exact communication costs for consensus and leader in a tree

We continue the study of communication costs of Consensus and Leader initiated in a previous paper. We deal with all scenarios with linear complexity in a tree topology, and prove exact (as opposed to asymptotic) tight bounds for the bit and message complexities. A particular scenario depends on whether the tree size or the size parity is known to the processors.     

On the eigenvalue problem for perturbed nonlinear maximal monotone operators in reflexive Banach spaces

Let be a real reflexive Banach space with dual and open and bounded and such that  Let be maximal monotone with and and with and A general and more unified eigenvalue theory is developed for the pair of operators  Further conditions are given for the existence of a pair such that

The ``implicit" eigenvalue problem, with in place of is also considered.  The existence of continuous branches of eigenvectors of infinite length is investigated, and a Fredholm alternative in the spirit of Necas is given for a pair of homogeneous operators No compactness assumptions have been made in most of the results.  The degree theories of Browder and Skrypnik are used, as well as the degree theories of the authors involving densely defined perturbations of maximal monotone operators.  Applications to nonlinear partial differential equations are included.

     

A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problems

The problem of scheduling n jobs with known process times on m identical parallel machines with an objective of minimizing weighted flow time is NP-hard. However, when job weights are identical, it is well known that the problem is easily solved using the shortest processing time rule. In this paper, we show that a generalization of the shortest processing time rule minimizes weighted flow time in a class of problems where job weights are not identical.     

On regular 4-coverings and their application for lattice coverings in normed planes

It is well known that the famous covering problem of Hadwiger is completely solved only in the planar case, i.e.: any planar convex body can be covered by four smaller homothetical copies of itself. Lassak derived the smallest possible ratio of four such homothets (having equal size), using the notion of regular 4-covering. We will continue these investigations, mainly (but not only) referring to centrally symmetric convex plates. This allows to interpret and derive our results in terms of Minkowski geometry (i.e., the geometry of finite dimensional real Banach spaces). As a tool we also use the notion of quasi-perfect and perfect parallelograms of normed planes, which do not differ in the Euclidean plane. Further on, we will use Minkowskian bisectors, different orthogonality types, and further notions from the geometry of normed planes, and we will construct lattice coverings of such planes and study related Voronoi regions and gray areas. Discussing relations to the known bundle theorem, we also extend Miquel’s six-circles theorem from the Euclidean plane to all strictly convex normed planes.     

Lower bound for the mean project completion time in dynamic PERT networks

We apply the stochastic dynamic programming to obtain a lower bound for the mean project completion time in a PERT network, where the activity durations are exponentially distributed random variables. Moreover, these random variables are non-static in that the distributions themselves vary according to some randomness in society like strike or inflation. This social randomness is modelled as a function of a separate continuous-time Markov process over the time horizon. The results are verified by simulation.     

Neural net versus classical models for the detection and localization of leaks in pipelines

Four models of a pipeline are compared in the paper: a nonlinear distributed-parameter model, a linear distributed-parameter model, a simplified lumped-parameter model and an extended neural-net-based model. The transcendental transfer function of the linearized model is obtained by a Laplace transformation and corresponding initial and boundary conditions. The lumped-parameter model is obtained by a Taylor series extension of the transencdental transfer function. Based on the experience of linear models the structure of the neural net model, as an addendum to the nonlinear distributed-parameter model, is obtained. All four models are tested on a real pipeline data with an artificially generated leak.     

On changing the spaces in Lagrange multiplier rules for the optimal control of non-linear operator equations

In this paper it is shown, how Lagrange multiplier rules for nonlinear optimal control problems in Banach spaces can be transferred by a simple device from the initial space to a more useful Banach space, in order to avoid unhandy dual spaces. The method is applied to state-equations of the type x-K(x,u)= 0, where the Fréchet-derivative of K has a certain smoothing property which is typical for integral operators.