The influence of the social relationships of an individual on the individual's opinions (about a topic, a product, or whatever else) is a well known phenomenon and it has been widely studied. This paper considers a network of positive (i.e. trusting) or negative (distrusting) social relationships where every individual has an initial positive or negative opinion (about a topic, a product, or whatever else) that changes over time, at discrete time-steps, due to the influences each individual gets from its neighbors. Here, the influence of a trusted neighbor is consistent with the neighbor's opinion, while the influence of a distrusted neighbor is opposite to the neighbor's opinion. At any time, an individual gets one of the two opinions if, at that time, the majority of its neighbors influences the individual to behave so. Given an initial opinion configuration for all the individual, natural questions in this setting are if a given arrival opinion configuration or an equilibrium opinion configuration will ever be reached or if all individuals in a given set will ever get the same (positive) opinion at the same time. All such questions will be proved to result in problems that are tractable if all the relationships are symmetric (that is, the underlying signed graph is undirected), and that are PSpace-complete if the underlying graph is directed even when all the relationships are positive.

Summary form only given. We introduce the weighted version of the range assignment problem in which the cost a station s pays to transmit to another station depends on the distance between the stations and on the energy cost of station s. Most of the algorithm results for the unweighted range assignment problem can not be applied to the weighted version. We thus provide a set of algorithmic results for this version and discuss some interesting related open questions.

Switching networks are the core of many communication and multiprocessor systems. In these systems, a set of entities (communication equipment or processors) communicate through the switching network by exchanging messages. Simultaneous transmission or reception of two 01 more different messages through an input or output port results in the corruption of the messages (also called collision), which are useless and must be retransmitted later. This causes a performance degradation. Collisions can be avoided only by a proper scheduling of the messages. The same problem also arises in single-hop purely optical WDM systems, where simultaneous reception or transmission over the same wavelength channel results in a collision. In this paper, we study the problem of minimum length scheduling of a set of messages subject to precedence constraints. We show that the decision version of the problem is NP-complete even in very restricted cases. This means that the optimization problem cannot be solved in polynomial time, unless P=NP. Since the problem cannot be optimally solved by fast algorithms, we then investigate the existence of polynomial time approximation algorithms, by first proving that approximation algorithms cannot exist with performance ratio bounded by 4/3 or smaller and successively presenting an /spl epsiv/-approximation algorithm with /spl epsiv/<2 for the case of two precedence classes of messages. Finally, we assess the existence of an asymptotically optimal schedule in the general case of an unrestricted number of precedence classes.

Problems related to message communication and traffic control have been assuming more and more importance due the massive use of computer networks. Scheduling a set of messages in a store and forward network means assigning to them network resources in order to deliver each message to its respective destination. The goal of typical scheduling problems is to devise strategies of assignments that minimize the delivery time of all messages or, alternatively, their total end-to-end delay. Both problems have been proven to be network performance (NP)-hard even under very restrictive hypothesis. We study the computational complexity of approximating the minimum end-to-end delay. Unfortunately, it turns out that finding an approximated solution with approximation ratio smaller than k/sup 1/10/ is as difficult as finding the optimal solution (where k is the number of messages in the network). More precisely, approximating the optimum delay is NP-hard even when a nonconstant approximation ratio is allowed. This result holds also in the case of layered networks. We then prove that if we consider a particular class of local schedules (i.e., distributed strategies that can only use information about limited regions of the network) then the approximation error cannot be bounded by any sublinear function in k. Such results also provide a lower bound on the approximation of the minimum delivery time problem. Thus, if the attention is restricted to polynomial-time algorithms, the only possibility is designing heuristics that behave well on average. As a first step to this aim, we evaluate the expected approximation error of some simple heuristics using several experimental tests.

Store and forward networks are a convenient model to represent problems in the areas of message communication and traffic control. The goal of a typical scheduling problem is to devise an optimal strategy to send messages from their source sites into their sink ones following paths in the network. In this paper the computational complexity of such a problem is analyzed in the cases of fixed and dynamically variable paths. Unfortunately, it turns out that both of the versions of the considered problem are NP-complete even under very restrictive hypothesis. Moreover, they are not approximable, that is, they can be solved only by polynomial-time heuristic algorithms such that the distance between the exact and the approximate solution is not bounded by any fixed value.>