Polynomial time solution to minimum forwarding set problem in wireless networks under disk coverage model

In this paper, we consider a practical problem, called Minimum Forwarding Set Problem (MFSP), that emerges within the context of implementing (energy efficient) communication protocols for wireless ad hoc or sensor networks. For a given node v, MFSP asks for a minimum cardinality subset of 1-hop neighbors of v to cover v’s 2-hop neighbors. MFSP problem is also known as multi-point relay (MPR) problem. It is shown to be an NP-complete problem for its general case that does not consider the coverage characteristics of wireless transmissions. In this paper, we present two polynomial time algorithms to solve the MFSP problem under disk coverage model for wireless transmissions. In our earlier work, we presented a polynomial time algorithm for this problem under unit disk coverage model. In the current work, we present several observations on the geometric characteristics of wireless transmissions under disk coverage model and build two alternative dynamic programming based solutions with different run time and space complexities to the problem. Disk coverage model is a more general model because it allows nodes to use arbitrary power levels for transmissions. As a result, the presented algorithms provide a more practical solution that can be used as a building block for energy efficient communication protocols designed for wireless ad hoc and sensor networks.     

A Polynomial Time Solution to Minimum Forwarding Set Problem in Wireless Networks under Unit Disk Coverage Model

Network-wide broadcast (simply broadcast) is a frequently used operation in wireless ad hoc networks (WANETs). One promising practical approach for energy-efficient broadcast is to use localized algorithms to minimize the number of nodes involved in the propagation of the broadcast messages. In this context, the minimum forwarding set problem (MFSP) (also known as multipoint relay (MPR) problem) has received a considerable attention in the research community. Even though the general form of the problem is shown to be NP-complete, the complexity of the problem has not been known under the practical application context of ad hoc networks. In this paper, we present a polynomial time algorithm to solve the MFSP for wireless network under unit disk coverage model. We prove the existence of some geometrical properties for the problem and then propose a polynomial time algorithm to build an optimal solution based on these properties. To the best of our knowledge, our algorithm is the first polynomial time solution to the MFSP under the unit disk coverage model. We believe that the work presented in this paper will have an impact on the design and development of new algorithms for several wireless network applications including energy-efficient multicast, broadcast, and topology control protocols for WANETs and sensor networks.     

Are Propositional Attitudes Mental States?

Minds and Machines - I present an argument that propositional attitudes are not mental states. In a nutshell, the argument is that if propositional attitudes are mental states, then only minded...     

Semi-online two-level supply chain scheduling problems

We consider two-level supply chain scheduling problems where customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. Processed jobs are grouped into batches, which are delivered to the customers as single shipments. The objective is to minimize the total cost which is the sum of the total flow time and the total delivery cost. Such problems have been considered in the off-line environment where future jobs are known, and in the online environment where at any time there is no information about future jobs. It is known that the best possible competitive ratio for an online algorithm is 2. We consider the problem in the semi-online environment, assuming that a lower bound P for all processing times is available a priori, and present a semi-online algorithm with competitive ratio \(\frac{2D}{D+P}\) where D is the cost of a delivery. Also, for the special case where all processing times are equal, we prove that the algorithm is \(1.045\sqrt{\frac{2-u}{u}}\)-competitive, where u is the density of the instance.