On the Convergence of Multicast Games in Directed Networks

We investigate the convergence of the price of anarchy after a limited number of moves in the classical multicast communication game when the underlying communication network is directed. Namely, a subset of nodes of the network are interested in receiving the transmission from a given source node and can share the cost of the used links according to fixed cost sharing methods. At each step, a single receiver is allowed to modify its communication strategy, that is to select a communication path from the source, and assuming a selfish or rational behavior, it will make a best response move, that is it will select a solution yielding the minimum possible payment or shared cost. We determine lower and upper bounds on the price of anarchy, that is the highest possible ratio among the overall cost of the links used by the receivers and the minimum possible cost realizing the required communications, after a limited number of moves under the fundamental Shapley cost sharing method. In particular, assuming that the initial set of connecting paths can be arbitrary, we show an $O(r\sqrt{r})We investigate the convergence of the price of anarchy after a limited number of moves in the classical multicast communication game when the underlying communication network is directed. Namely, a subset of nodes of the network are interested in receiving the transmission from a given source node and can share the cost of the used links according to fixed cost sharing methods. At each step, a single receiver is allowed to modify its communication strategy, that is to select a communication path from the source, and assuming a selfish or rational behavior, it will make a best response move, that is it will select a solution yielding the minimum possible payment or shared cost. We determine lower and upper bounds on the price of anarchy, that is the highest possible ratio among the overall cost of the links used by the receivers and the minimum possible cost realizing the required communications, after a limited number of moves under the fundamental Shapley cost sharing method. In particular, assuming that the initial set of connecting paths can be arbitrary, we show an O(r?r)O(r\sqrt{r}) upper bound on the price of anarchy after 2 rounds, during each of which all the receivers move exactly once, and a matching lower bound, that we also extend to W(r^k?{r})\Omega(r\sqrt[k]{r}) for any number k≥2 rounds, where r is the number of receivers. Similarly, exactly matching upper and lower bounds equal to r are determined for any number of rounds when starting from the empty state in which no path has been selected. Analogous results are obtained also with respect to other three natural cost sharing methods considered in the literature, that is the egalitarian, path-proportional and egalitarian-path proportional ones. Most results are also extended to the undirected case in which the communication links are bidirectional.     

A network of pyramidal neurons is sensitive to the timing of its excitatory inputs

The transmission of excitatory inputs by a network of coupled pyramidal cells is investigated by means of numerical simulations. The pyramidal cell models are coupled by excitatory synapses and each one receives an excitatory pulse at a random time extracted from a Gaussian distribution. Moreover, each cell model is injected with a noisy current. It was found that the excitatory coupling promotes the transmission of the synaptic inputs on a time scale of a few ms.     

The phase behavior of n-alkane systems

Normal alkanes show very complicated phase transition kinetics and macroscopic phase equilibrium behavior. This paper focuses on the phase stability and equilibrium of complicated mixtures like n-alkanes and on the enabling global optimization technologies needed to gather problem knowledge. The new ideas contained in this paper include:

(1) novel level set methods for gathering encoded knowledge;

(2) the differential geometry for uncovering pathways to more subtle knowledge;

(3) all supporting non-linearly constrained optimization techniques;

(4) all data handling needed to unravel complex solution structure.

These new ideas are incorporated within the integral path methodology or terrain methods recently developed by Lucia, A., & Yang, F. (2003) [Lucia, A., & Yang F. (2003). Multivariable terrain methods. AIChE Journal 49, 2553] and Lucia, DiMaggio, and Depa (2004) [Lucia, A., DiMaggio, P.A., & Depa, P. (2004). A geometric terrain methodology for global optimization. Journal of Global Optimization 29, 297]. This framework provides global knowledge for understanding solution structure, like the complex solution structure of n-alkanes. In particular, it is shown that knowledge of the Newton and tangent vector fields, Gauss curvature, integral path bifurcation points, and non-differentiable manifolds provides a deterministic way of finding additional solutions, saddle points, and other information that might otherwise go undetected.It is shown that the optimization tools developed in this work provide all knowledge of interest on the appropriate hypothetical single-phase or composite surface (i.e., minima, saddle points, singular points, and integral paths) in phase stability applications. This knowledge can be obtained by solving the phase stability problem exactly once, in a pre-processing step, and used to reliably initialize any multi-phase equilibrium calculation for any feed. This removes the need to repeatedly solve the phase stability problem as the feed composition changes and greatly increases computational efficiency. Numerical examples and geometric illustrations are used to elucidate key ideas and to show how the proposed approach can be used to unravel the complicated phase behavior of n-alkane mixtures.     

Minimize the Maximum Duty in Multi-interface Networks

We consider devices equipped with multiple wired or wireless interfaces. By switching of various interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider two basic networking problems in the field of multi-interface networks. The first one, known as the Coverage problem, requires to establish the connections defined by a network. The second one, known as Connectivity problem, requires to guarantee a connecting path between any pair of nodes of a network. Both are subject to the constraint of keeping as low as possible the maximum cost set of active interfaces at each single node. We study the problems of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges in the first case, or to ensure connectivity in the second case. We prove that the Coverage problem is NP-hard for any fixed Δ≥5 and k≥16, with Δ being the maximum degree, and k being the number of different interfaces among the network. We also show that, unless P=NP, the problem cannot be approximated within a factor of ηln?Δ, for a certain constant η. We then provide a general approximation algorithm which guarantees a factor of O((1+b)ln?Δ), with b being a parameter depending on the topology of the input graph. Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented. Concerning the Connectivity problem, we prove that it is NP-hard for any fixed Δ≥3 and k≥10. Also for this problem, the inapproximability result holds, that is, unless P=NP, the problem cannot be approximated within a factor of ηln?Δ, for a certain constant η. We then provide approximation and exact algorithms for the general problem and for special cases, respectively.     

High‐quality pagination for publishing

The problem of line breaking consists of finding the best way to split paragraphs into lines. It has been cleverly addressed by the total‐fit algorithm exposed by Knuth and Plass in a well‐known paper. Similarly, page‐breaking algorithms break the content flow of a document into page units. Formatting languages—such as the World Wide Web Consortium standard Extensible Stylesheet Language Formatting Objects (XSL‐FO)—allow users to set which content should be kept in the same page and how many isolated lines are acceptable at the beginning/end of each page. The strategies most formatters adopt to meet these requirements, however, are not satisfactory for many publishing contexts as they very often generate unpleasant empty areas. In that case, typographers are required to manually craft the results in order to completely fill pages. This paper presents a page‐breaking algorithm that extends the original Knuth and Plass line‐breaking approach and produces high‐quality documents without unwanted empty areas. The basic idea consists of delaying the definitive choice of breaks in the line‐breaking process in order to provide a larger set of alternatives to the actual pagination step. The algorithm also allows users to decide the set of properties to be adjusted for pagination and their variation ranges. An application of the algorithm to XSL‐FO is also presented, with an extension of the language that allows users to drive the pagination process. The tool, named FOP+, is a customized version of the open‐source Apache Formatting Objects Processor formatter. Copyright © 2011 John Wiley & Sons, Ltd.     

Mechanical sensorless speed control of permanent-magnet AC motors driving an unknown load

A new sensorless scheme for high-performance speed control of permanent-magnet ac motors (PMACMs) driving an unknown load is proposed. This scheme uses an extended nonlinear reduced-order observer to estimate the induced electromotive force (EMF) and load torque. From the estimated variables, the rotor position, the rotor speed, and the position derivative of flux are calculated and are used to close the control loop. In order to improve the drive performance, the estimated load torque is incorporated as a feedforward signal in the closed control loop. In addition, the proposed sensorless PMACM drive allows the torque-ripple and copper-loss minimization for motors with an arbitrary EMF waveform. Simulation and experimental results to validate the proposal are presented in this paper.