Weidong Li

In this paper, we consider a network optimization interdiction problem, called the [Formula: see text]-matching interdiction problem on undirected trees with unit edge weights. Given an undirected tree [Formula: see text], each vertex [Formula: see text] has a capacity [Formula: see text], the [Formula: see text]-matching of [Formula: see text] is an edge subset [Formula: see text] such that the number of edges in [Formula: see text] incident to [Formula: see text] is at most [Formula: see text] for each [Formula: see text]. A maximum [Formula: see text]-matching is a [Formula: see text]-matching that contains the largest number of edges among all possible [Formula: see text]-matchings. In this paper, we consider two problems: (1) The [Formula: see text]-matching edge interdiction problem. Each edge of [Formula: see text] has an interdiction cost. Each vertex of [Formula: see text] has a capacity. There is also an interdiction budget. The goal is to remove a subset of the edges constrained to a budget such that the size of maximum [Formula: see text]-matching in the resulting graph is minimized. (2) The [Formula: see text]-matching vertex interdiction problem. Each vertex of [Formula: see text] has an interdiction cost and a capacity. There is also an interdiction budget. The goal is to remove a subset of the vertices constrained to a budget such that the size of maximum [Formula: see text]-matching in the resulting graph is minimized. We first show that both problems are NP-hard. Then, we propose several pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for both problems.

Identifying the most influential communicators as an issue of maximizing influence has become one of the most notable topics in social network analysis, as it has achieved success in viral marketing. Only by understanding our opponent's way of thinking can we effectively defend against or attack them. We particularly focus on one type of such attacks called the weight stable set attack problem with budget constraint. Given a social network, each node has a weight and removal cost. This problem is to remove a subset of the nodes whose total removal cost does not exceed a given threshold, such that the maximum weight stable set in the resulting graph is minimized. We first propose a 2$\alpha$-approximation algorithm for this problem on the graph without odd cycles, where $\alpha$ is the approximation ratio for the algorithm of the minimum knapsack problem. Interestingly, this algorithm can be extended to general graphs. We also design a genetic algorithm for general graphs. Finally, we conducted many experiments on both artificial networks and real-world networks. For the graph without odd cycles, the results show that our performance ratio is less than 1.21. For general graphs, we compare the algorithm that extends the idea of graphs without odd cycles with the genetic algorithm. The results show that this algorithm is better than the genetic algorithm in some settings.

Mobile crowdsensing services (MCSs) have long been a popular research topic in service computing. An MCS provider recruits users to complete data collection tasks, with an incentive mechanism employed to achieve greater utility. However, most existing studies have assumed that data collected by different users in the same area have the same value, which is not consistent with reality and reduces the quality of service. For example, noise or air quality data collected from different locations within the same area may differ considerably. In this paper, a distance factor is innovatively integrated into the MCS task allocation problem to more accurately represent real situations. Specifically, we transform the distance-sensitive online MCS task allocation problem into an integer programming model with budget constraints and ordered submodular characteristics. Additionally, we design a reverse auction mechanism based on reinforcement learning (RL) to solve the winner determination and payment problems. Unlike existing machine learning-based mechanisms, the proposed algorithms can strictly guarantee the economic characteristics of the auction mechanism, such as its individual rationality, truthfulness, and budget feasibility, through weight replacement and equilibrium pricing strategies. In experimental evaluations, we compare our algorithm with the offline optimal (OPT) algorithm, the advanced monotonic discrete online TDMC algorithm and the FULL SP-RL algorithm as benchmarks. The results indicate that our approach can enable service providers to obtain higher values with lower payments.

Mobile edge computing (MEC) transforms the network edge into an intelligent computing platform by deploying heterogeneous servers near end users. However, allocating resources to diverse users in MEC faces several challenges: wireless access may be limited by access point range, user demands often mismatch heterogeneous server configurations, and both computing and communication resources are constrained. Fair and efficient multi-resource allocation can promote sharing while utilizing idle capacity for high-workload users. To address this, we propose LMM-TSF, a Lexicographically Max-Min Task Share Faireness allocation mechanism that accounts for server access and external wireless resource constraints. Theoretically, LMM-TSF satisfies several desirable properties including envy-freeness, Pareto optimality, sharing incentives, and strategy-proofness. Large-scale simulations using Alibaba cluster traces show that LMM-TSF outperforms state-of-the-art fair allocation mechanisms in resource utilization and upholds the sharing incentive property.

Rapid advances in technology have endowed intelligent vehicles with increasing computing power and rich perception abilities. In this paper, we address the problem of computation offloading and resource sharing in vehicle computing, where the vehicle provides computing and sensing resources to users. Since sensing devices capture the same data at any given moment, multiple users can simultaneously share the sensing resources of the same vehicle. Building on this, we propose a novel resource-sharing model that, while allocating computing resources only to users, allows users to monopolize or share sensing resources. By serving more users, this resource-sharing model results in savings on vehicle costs. The proposed mechanism comprises three types of auctions: one-to-many, many-to-one, and one-to-one. While the one-to-many auction allocates resources of one vehicle to multiple users, the many-to-one auction allocates resources of multiple vehicles to one user. The one-to-one auction, on the contrary, restricts allocation of resources of one vehicle to one user. While being truthful for both users and vehicles, this mechanism also contributes to individual rationality, budget balance, and consumer sovereignty. Finally, simulation results confirm the efficiency of the mechanism, which achieves high performance while facilitating additional utility.

Mobile edge computing (MEC) has powerful computing capabilities, and intelligent vehicles have abundant sensing resources; thus, integrating them can leverage their respective advantages to provide broader services. Motivated by this, we develop the edge-assisted vehicle computing system, in which MEC servers and vehicles are responsible for data processing and collection, respectively. Since the sensor data collected by the same sensor device in the vehicle is identical at any given time, we propose a resource-sharing model in which multiple users share the sensing resources, with the vehicle's cost shared among the serviced users. However, the strategic operations by a single user or group of users may harm the interests of the system and other participants. Therefore, we aim to design a strategyproof mechanism to drive the system into an equilibrium. We propose a cost-sharing mechanism and show that it achieves both strategyproofness and group strategyproofness. A design method for the strategyproof mechanism is proposed. We show that the proposed mechanism achieves individual rationality, budget balance, and consumer sovereignty. Furthermore, we analyze the approximate ratio of the proposed mechanism. Experimental results demonstrated that the proposed mechanism performs well across different scenarios.