Non-fungible tokens (NFTs) have emerged as a transformative innovation in art and technology, relying heavily on social networks for promotion and revenue generation. The value of NFTs is profoundly influenced by their scarcity, rarity, and unique breeding mechanisms, which present novel challenges for viral marketing strategies. In this paper, we introduce a new research problem of NFT Revenue Maximization (NRM), which focuses on maximizing revenue from the perspective of NFT marketplaces by optimally selecting users for viral marketing campaigns (NFT airdrops) and determining the ideal quantities of NFTs to release. We prove the hardness of NRM and propose an approximation algorithm named Quantity and Offspring-Oriented Airdrops (QOOA). Our algorithm leverages the concepts of Scarcity-Conscious Revenue and Valuation-based Quantity Inequality to prune suboptimal airdrops and quantities at an early stage. To further enhance revenue through NFT breeding, QOOA identifies and incentivizes Rare Trait Collectors to acquire multiple NFTs with rare traits, facilitating the breeding of high-value offspring. Experimental results demonstrate that QOOA significantly outperforms baselines, achieving up to 3.8 times higher revenue in large-scale social networks.

In this paper, we address the problem of revenue maximization (RM) for multi-grade products in social networks by considering pricing, seed selection, and coupon distribution. Previous works on RM often focus on a single product and neglect the use of coupons for promotion. We propose a new optimization problem,Revenue Maximization of Multi-Grade Product(RMMGP), to simultaneously determine pricing, seed selection, and coupon distribution for multi-grade products with both promotional and competitive relationships between grades in order to maximize revenue through viral marketing. We prove the hardness and inapproximability of RMMGP and show that the revenue function is not monotone or submodular. To solve RMMGP, we design an approximation algorithm, namelyData-Dependent Revenue Maximization (DDRM), and propose thePricing-Seeding-Coupon allocation (PriSCa)algorithm, which uses the concepts of Worth Receiving Probability, Pricing-Promotion Alternating Framework, and Independent/Holistic Customer-Grade Determinant sets. Our experiments on real social networks, using valuation distributions from Amazon.com, demonstrate that PriSCa and DDRM achieve on average 1.5 times higher revenue than state-of-the-art approaches. Additionally, PriSCa is efficient and scalable on large datasets.

The problem of maximizing submodular set functions has received increasing attention in recent years, and significant improvements have been made, particularly in relation to objective functions that satisfy monotonic submodularity. However, in practice, the objective function may not be monotonically submodular. While greedy algorithms have strong theoretical guarantees for maximizing submodular functions, their performance is barely guaranteed for non-submodular functions. Therefore, in this paper, we investigate the problem of maximizing non-monotone non-submodular functions under knapsack constraints based on the problem of infectious diseases and provides a more sophisticated analysis through the idea of segmentation. Since our definition characterizes the function more elaborately, a better bound, i.e., a tighter approximation guarantee, is achieved. Finally, we generalize the relevant results for the more general problems.

Due to the growing need for bandwidth starving Multi-View Videos (MVV) in virtual reality, TV, and education, effectively allocating the resources of next-generation wireless technologies for MVV streams becomes increasingly crucial. To achieve high utility for MVV users, this article proposes a cross-layer resource allocation mechanism to leverage video synthesizing schemes (such as Depth-Image-Based Rendering (DIBR) for efficient MVV streaming with massive MIMO). First, we formulate a new problem,antenna allocation with video synthesis(AAVS), and prove its NP-hardness. Then, we design an approximation algorithm namedUtility-based Multi-View Synthesis(UMVS) with the analytical performance provided, and dynamic scenarios are addressed by augmenting UMVS with deep reinforcement learning. Data-driven simulation results show that UMVS outperforms existing antenna allocation schemes by at least 10%, and the DRL extension provides an additional 6% improvement in system utility under congested scenarios.

Wireless power transfer (WPT) has emerged to enhance the robustness of the energy harvesting Internet of Things (EH-IoT), whereas beamforming has been leveraged to significantly boost the efficiency of far-field WPT. Nevertheless, potential negative impacts due to high electromagnetic fields (EMF) exposure for radiation-susceptible users have not been thoroughly considered in the design of WPT for EH-IoT with IoT application-level requirements (e.g., coverage). In this article, we explore the health-aware beamforming and IoT selection problem under the EH and human safety constraints. First, we formulate a new optimization problem Health-Aware Beamforming and IoT Selection (HABIS) and prove the NP-hardness. Second, we design an approximation algorithm, named Minimum Radiation Exposure and Maximum IoT Coverage (MREMIC), to exploit the EH-health dependency (EHHD) graph for properly addressing the trade-off between EH efficiency and potential EMF radiation exposure to human bodies. We also discover the optimal health-aware beamforming to minimize the total radiation energy absorption of humans. Simulation results show that MREMIC can effectively charge IoT devices and significantly outperforms existing EH approaches by more than 200% regarding human safety.

The virtual reality (VR) market is expected to reach 202.7 billion dollars by 2028, at a compound annual growth rate of 24.74% over the forecast period 2023–2028. It motivates innovative VR services in touring, E-commerce, and social activities, and effective VR video streaming becomes essential. However, VR services are envisaged to consume a large amount of bandwidth, but current research primarily focuses on multimedia streaming for each individual user without considering the opportunity of view synthesis for multicast to reduce wireless resource consumption further. In this article, we formulate a new optimization problem VR Content Sharing and Multicasting (VCSM) and prove the NP-hardness. Then, we propose an approximation algorithm, named Efficient View Synthesis and Multicasting (EVSM), to select multicast views and their Modulation and Coding Schemes (MCS) for wireless VR services. Afterward, we extend EVSM to support dynamic user behaviors and increase scalability with distributed mobile edge computing. We also explore the intrinsic properties of view selections to find the optimal solution for regular user deployment. Experiment results show that EVSM can effectively reduce bandwidth consumption for VR services by more than 50$\%$.

The potential impact of epidemics, e.g., COVID-19, H1N1, and SARS, is severe on public health, the economy, education, and society. Before effective treatments are available and vaccines are fully deployed, combining Non-Pharmaceutical Interventions (NPIs) and vaccination strategies is the main approaches to contain the epidemic or live with the virus. Therefore, research for deciding the best containment operations to contain the epidemic based on various objectives and concerns is much needed. In this paper, we formulate the problem of Containment Operation Optimization Design (COOD) that optimizes the epidemic containment by carefully analyzing contacts between individuals. We prove the hardness of COOD and propose an approximation algorithm, named Multi-Type Action Scheduling (MTAS), with the ideas of Infected Ratio, Contact Risk, and Severity Score to select and schedule appropriate actions that implement NPIs and allocate vaccines for different groups of people. We evaluate MTAS on real epidemic data of a population with real contacts and compare it against existing approaches in epidemic and misinformation containment. Experimental results demonstrate that MTAS improves at least 200% over the baselines in the test case of sustaining public health and the economy. Moreover, the applicability of MTAS to various epidemics of different dynamics is demonstrated, i.e., MTAS can effectively slow down the peak and reduce the number of infected individuals at the peak.

Flow consolidation has been proposed for merging multiple flows from different services into an aggregate flow to remedy the state explosion problem in software-defined networks (SDN). However, we observe that the Quality of Service (QoS) requirements are no longer sustained in aggregate flows since the bandwidth decided by TCP is usually different from the desired rate of each service. Therefore, this article explores an idea to control the rates of only a few service flows so that the rates of all uncontrolled flows allocated by TCP will meet their QoS requirements. We design a new architecture, called Scalable Per-Flow Rate Allocation (SPFRA), and formulate a new optimization problem, termed Scalable Rate Allocation for Aggregate Flows (SRAF), to find a minimum number of controlled flows to increase the scalability of SDN with diverse service requirements. We prove the NP-hardness and inapproximability of SRAF. To solve the problem, we design an algorithm, named Aggregate Flow Selection and Flow Release (AFSFR), to achieve the tightest bound and extend it to support distributed computation and dynamic traffic for instant services. Simulations and implementation on an SDN testbed manifest that AFSFR performs nearly optimally in real networks, and the number of controlled flows can be effectively reduced by 50 percent.

Viral marketing on social networks, also known as Influence Maximization (IM), aims to select k users for the promotion of a target item by maximizing the total spread of their influence. However, most previous works on IM do not explore the dynamic user perception of promoted items in the process. In this paper, by exploiting the knowledge graph (KG) to capture dynamic user perception, we formulate the problem of Influence Maximization based on Dynamic Personal Perception (IMDPP) that considers user preferences and social influence reflecting the impact of relevant item adoptions. We prove the hardness of IMDPP and design an approximation algorithm, named Dynamic perception for seeding in target markets (Dysim), by exploring the concepts of dynamic reachability, target markets, and substantial influence to select and promote a sequence of relevant items. We evaluate the performance of Dysim in comparison with the state-of-the-art approaches using real social networks with real KGs. The experimental results show that Dysim effectively achieves at least 6 times of influence spread in large datasets over the state-of-the-art approaches.

Due to the growing need for Multi-View Videos (MVV) in advertisement, TV, and education, effectively allocating the resources of next-generation wireless technologies to provide MVV streams is challenging. To achieve the high utility for MVV users, this paper proposes a cross-layer resource allocation mechanism to leverage video synthesizing schemes (such as Depth-Image-Based Rendering (DIBR)) for efficient MVV streaming with massive MIMO. We formulate a new problem Antenna Allocation with Video Synthesizing (AAVS) and prove its NP-hardness. Then, we design an algorithm, named Marginal Utility-Based Iteration (MUBI). The performance is evaluated by the data-driven simulations, and the results manifest that MUBI outperforms the baselines regarding the total utility of users.

Existing research on social networks manifests two crucial criteria to improve activity engagement of users: (1) user interests in the activity topics and (2) opportunities of making new friends with some acquaintances. However, current online platforms still involve massive manual selection for activity attendees and contents without proper recommendations. In this paper, therefore, we formulate a new activity organization problem, named Social Knowledge Group Query (SKGQ), to recommend attendees and topic-related contents simultaneously. We prove that SKGQ is NP-hard and design an approximation algorithm, named Social cOntent Knowledge Exploration (SOKE), to jointly choose the activity attendees and topic-related contents according to social-oriented and topic- oriented strategies. Simulation results manifest that the solution acquired by SOKE is close to the optimal solution and outperforms various baselines.

Online social networks have become the medium for efficient viral marketing exploiting social influence in information diffusion. However, the emerging application Social Coupon (SC) incorporating social referral into coupons cannot be efficiently solved by previous researches which do not take into account the effect of SC allocation. The number of allocated SCs restricts the number of influenced friends for each user. In the paper, we investigate not only the seed selection problem but also the effect of SC allocation for optimizing the redemption rate which represents the efficiency of SC allocation. Accordingly, we formulate a problem named Seed Selection and SC allocation for Redemption Maximization (S3CRM) and prove the hardness of S3CRM. We design an effective algorithm with a performance guarantee, called Seed Selection and Social Coupon allocation algorithm. For S3CRM, we introduce the notion of marginal redemption to evaluate the efficiency of investment in seeds and SCs. Moreover, for a balanced investment, we develop a new graph structure called guaranteed path, to explore the opportunity to optimize the redemption rate. Finally, we perform a comprehensive evaluation on our proposed algorithm with various baselines. The results validate our ideas and show the effectiveness of the proposed algorithm over baselines.

One model for viral marketing is the positive influence. In this model, an inactive node is changed into active if and only if at least half of its neighbors are already in active state. The positive influence model can be viewed as a special case of a general threshold model, in which the threshold function at each node has value one if at least a certain fraction of neighbors are in active state, and value 0 otherwise. This function can be proved to be monotonically increasing and nonsubmodular for any predefined fraction. Therefore, given a seed set, the number of influenced nodes is not submodular with respect to the size of the seed set. This fact makes those optimization problems related with positive influence very hard, including the minimum partial positive influence seeding problem: Given a social network G = (V, E) and a number 02H ([pn]))-approximation algorithm for the minimum partial positive influence seeding problem, where n is the number of nodes, and H(·) is the Harmonic number.

In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-tolerant. A fault-tolerant virtual backbone can be modeled as a k-connected m-fold dominating set ((k, m)-CDS for short). In this paper, we present a constant approximation algorithm for the minimum weight (k, m)-CDS problem in unit disk graphs under the assumption that k and m are two fixed constants with m ≥ k. Prior to this paper, constant approximation algorithms are known for k = 1 with weight and 2 ≤ k ≤ 3 without weight. Our result is the first constant approximation algorithm for the (k, m)-CDS problem with general k, m and with weight. The performance ratio is (α+5ρ) fork ≥ 3 and (α+2.5ρ) for k = 2, where α is the performance ratio for the minimum weight m-fold dominating set problem and ρ is the performance ratio for the subset k-connected subgraph problem (both problems are known to have constant performance ratios).

In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-tolerant. Such a consideration leads to the problem of finding a minimum weight k-connected m-fold dominating set ((k, m)-MWCDS for short). In this paper, we give an (α + 2.5ρ)-approximation for (2, m)-MWCDS with m ≥ 2 in unit disk graph, where α is the performance ratio for the minimum weight m-fold dominating set problem, and ρ is the performance ratio for the {0,1,2}-Steiner Network Design problem. In view of currently best known ratios for α and ρ, (2, m)-MWCDS has a (9 + ε)-approximation for m ≥ 3 and a (8 + ε)-approximation for m =2, where ε is an arbitrary positive real number.