Many practical problems emphasize the importance of not only knowing whether an element is selected but also deciding to what extent it is selected, which imposes a challenge on submodule optimization. In this study, we consider the monotone, nondecreasing, and non-submodular maximization on the integer lattice with a cardinality constraint. We first design a two-pass streaming algorithm by refining the estimation interval of the optimal value. For each element, the algorithm not only decides whether to save the element but also gives the number of reservations. Then, we introduce the binary search as a subroutine to reduce the time complexity. Next, we obtain a one-pass streaming algorithm by dynamically updating the estimation interval of optimal value. Finally, we improve the memory complexity of this algorithm.

In recent years, due to the wide implementation of mobile agents, the Internet-of-Things (IoT) networks have been applied in several real-life scenarios, servicing applications in the areas of public safety, proximity-based services, and fog computing. Meanwhile, when more complex tasks are processed in IoT networks, demands on identity authentication, certifiable traceability, and privacy protection for services in IoT networks increase. Building a blockchain system in IoT networks can greatly satisfy such demands. However, the blockchain building in IoT brings about new challenges compared with that in the traditional full-blown Internet with reliable transmissions, especially in terms of achieving consensus on each block in complex wireless environments, which directly motivates our work. In this study, we fully considered the challenges of achieving a consensus in a blockchain system in IoT networks, including the negative impacts caused by contention and interference in wireless channel, and the lack of reliable transmissions and prior network organizations. By proposing a distributed consensus algorithm for blockchains on multi-hop IoT networks, we showed that it is possible to directly reach a consensus for blockchains in IoT networks, without relying on any additional network layers or protocols to provide reliable and ordered communications. In our theoretical analysis, we showed that our consensus algorithm is asymptotically optimal on time complexity and is energy saving. The extensive simulation results also validate our conclusions in the theoretical analysis.