We study a variant of set cover on the real line, where elements are points, sets are intervals, and each point has an integer demand; a point is fully covered when it is contained in at least its demand many chosen intervals. The objective is to select the fewest intervals that fully cover at least a specified number of points. We present the first polynomial-time approximation scheme (PTAS) for the unweighted version of this problem and show that a natural weighted generalization is NP-complete.

In this paper, we present the first constant-approximation algorithm forbudgeted sweep coverage problem(BSC). The BSC involves designing routes for a number of mobile sensors (a.k.a. robots) to periodically collect information as much as possible from points of interest (PoIs). To approach this problem, we propose to first examine themulti-orienteering problem(MOP). The MOP aims to find a set of$m$vertex-disjoint paths that cover as many vertices as possible while adhering to a budget constraint$B$. We develop a constant-approximation algorithm for MOP and utilize it to achieve a constant-approximation for BSC. Our findings open new possibilities for optimizing mobile sensor deployments and related combinatorial optimization tasks.

The problem of finding a minimum cardinality/weight connected dominating set (CDS) of a given graph has been studied extensively, because of its wide applications in wireless sensor networks (WSNs). Existing studies typically assume that the underlying network structure is fixed and preknown. However, given the inherent instability of mobile wireless devices, the network structure may be considered a random variable. Furthermore, determining the state of a node (active or inactive) often requires probing its local neighborhood. This motivates us to study the stochastic connected dominating set problem whose goal is to identify a connected dominating set within the graph comprised of active nodes while minimizing the probing cost. In this paper, we study the unweighted stochastic CDS problem, and present an$\left ({{\frac {1}{\delta }(H (\Delta -1)+1)+1}}\right)$-approximation algorithm in expectation, where$H(\gamma)=\sum _{i=1}^{\gamma }1/i$is the$\gamma $th Harmonic number,$\Delta $is the maximum degree of the graph, and$\delta $is the minimum probability that a node is active.

Vision-Language Models (VLMs) play a crucial role in the advancement of Artificial General Intelligence (AGI). As AGI rapidly evolves, addressing security concerns has emerged as one of the most significant challenges for VLMs. In this paper, we present extensive experiments that expose the vulnerabilities of conventional adaptation methods for VLMs, highlighting significant security risks. Moreover, as VLMs grow in size, the application of traditional adversarial adaptation techniques incurs substantial computational costs. To address these issues, we propose a parameter-efficient adversarial adaptation method called AdvLoRA based on Low-Rank Adaptation. We investigate and reveal the inherent low-rank properties involved in adversarial adaptation for VLMs. Different from LoRA, we enhance the efficiency and robustness of adversarial adaptation by introducing a novel reparameterization method that leverages parameter clustering and alignment. Additionally, we propose an adaptive parameter update strategy to further bolster robustness. These innovations enable our AdvLoRA to mitigate issues related to model security and resource wastage. Extensive experiments confirm the effectiveness and efficiency of AdvLoRA.

While the potential applications of the consortium blockchain are becoming increasingly evident, the fault tolerance of systems in complex and changeable real environments has become an increasingly important factor. In recent years, many blockchain-oriented fault tolerance testing tools have been proposed. However, the selected fault sets cannot cover all kinds of problems that the consortium blockchain may encounter in real scenarios. Moreover, a rationality analysis of test results is often missing from these tools. In addition, it is also worth considering how to optimize system performance in the fault continuous stage. In this paper, we propose a general full-stack fault injection platform that can support the orderly injection of different kinds of Byzantine and non-Byzantine failures in a distributed scenario. Regarding the unclear underlying principles affecting system performance due to faults, we conduct an attribution analysis of various faults' influences on the consortium blockchain. Based on conclusions drawn form the attribution analysis, we design and implement the test-driven optimization strategy. The experimental results show that the optimization strategy can shorten the system average delay to less than one-third of that before optimization by reducing the throughput by about 15% in most fault scenarios.

Consider a graph with nonnegative node weight. A vertex subset is called a CDS (connected dominating set) if every other node has at least one neighbor in the subset and the subset induces a connected subgraph. Furthermore, if every other node has at least m neighbors in the subset, then the node subset is called a [Formula: see text]CDS. The minimum-weight [Formula: see text]CDS problem aims at finding a [Formula: see text]CDS with minimum total node weight. In this paper, we present a new polynomial-time approximation algorithm for this problem, which improves previous ratio by a factor of 2/3. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grant U20A2068] and the National Science Foundation [Grant III-1907472]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0306 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0306 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

ABSTRACT Given a set of points on a line, a set of intervals along the line and an integer , each point is associated with a covering requirement , the goal of the minimum interval partial multi‐cover (MinIPMC) problem is to select the minimum number of intervals to fully cover at least points, where a point is fully covered if it belongs to at least selected intervals. This paper presents a 2‐approximation algorithm for the MinIPMC problem.

Adaptive influence maximization is an important research problem in computational social networks, which is also a typical problem in the study of adaptive processing of information and adaptive construction of objects. In this paper, we propose a new method that reduces the adaptive influence maximization problem into a nonadaptive one in a different social network, so that an adaptive optimization can be solved by those methods for nonadaptive optimization. In addition, we provide a new approximation algorithm for the submodular maximization problem with a knapsack constraint, which runs in [Formula: see text] time and has performance ratio [Formula: see text], where n is the number of nodes in the network. The ratio is better than the best known previous one with the same running time. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This research is supported in part by the National Natural Science Foundation of China [Grant U20A2068].

Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a global simple multiobjective evolutionary algorithm (GSEMO) and apply it on a minimum weight general cover problem, which is general enough to subsume many important problems including the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is nonsubmodular. We show that GSEMO yields theoretically guaranteed approximation ratios matching those achievable by a greedy algorithm in expected polynomial time when the potential function g is polynomial in the input size and the minimum gap between different g-values is a constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by National Natural Science Foundation of China [11771013, U20A2068]; Zhejiang Provincial Natural Science Foundation of China [LD19A010001].

Abstract Given a graph G, the minimum Connected-k-Subgraph Cover problem (MinCkSC) is to find a minimum vertex subset C of G such that every connected subgraph of G on k vertices has at least one vertex in C. If furthermore the subgraph of G induced by C is connected, then the problem is denoted as MinCkSC $_{con}$ . In this paper, we first present a PTAS for MinCkSC on an H-minor-free graph, where H is a graph with a constant number of vertices. Then, we design an $O((\omega+1)(2(k-1)(\omega+2))^{3\omega+3})|V|$ -time FPT algorithm for MinCkSC $_{con}$ on a graph with treewidth $\omega$ , based on which we further design an $O(2^{O(\sqrt{t}\log t)}|V|^{O(1)})$ time subexponential FPT algorithm for MinCkSC $_{con}$ on an H-minor-free graph, where t is an upper bound of solution size.

Today, blockchain ledgers utilize concurrent deterministic execution schemes to scale up. However, ordering fairness is not preserved in these schemes: although they ensure all replicas achieve the same serial order, this order does not always align with the fair, consensus-established order when executing smart contracts with runtime-determined accesses. To preserve ordering fairness, an intuitive method is to concurrently execute transactions and re-execute any order-violating ones. This in turn increases unforeseen conflicts, leading to scaling bottlenecks caused by numerous costly aborts under contention. To address these issues, we propose Spectrum, a novel deterministic execution scheme for smart contract execution on blockchain ledgers. Spectrum preserves the consensus-established serial order (so-called strict determinism) with high performance. Specifically, we leverage a speculative deterministic concurrency control to execute transactions in speculation and enforce an agreed-upon serial order by aborting and re-executing any mis-speculated ones. To overcome the scaling bottleneck, we present two key optimizations based on speculative processing: operation-level rollback and predictive scheduling, for reducing both the overhead and the number of mis-speculations. We evaluate Spectrum by executing EVM-based smart contracts on popular benchmarks, showing that it realizes fair smart contract execution by preserving ordering fairness and outperforms competitive schemes in contended workloads by 1.4x to 4.1x.

The study focuses on achieving full view coverage in a camera sensor network to effectively monitor moving objects from multiple perspectives. Three key issues are addressed: camera direction selection, location selection, and moving object monitoring. There are three steps to maximize coverage of moving targets. The first step involves proposing the Maximum Group Set Coverage (MGSC) algorithm, which selects the camera sensor direction for traditional target coverage. In the second step, a composed target merged from a set of fixed directional targets represents multiple views of a moving object. Building upon the MGSC algorithm, the Maximum Group Set Coverage with Composed Targets (MGSC-CT) algorithm is presented to determine camera sensor directions that cover subsets of fixed directional targets. Additionally, a constraint on the number of cameras is imposed for camera location selection, leading to the study of the Maximum Group Set Coverage with Size Constraint (MGSC-SC) algorithm. Each of these steps formulates a problem on group set coverage and provides an algorithmic solution. Furthermore, improved versions of MGSC-CT and MGSC-SC are developed to enhance the coverage speed. Computer simulations are employed to demonstrate the significant performance of the algorithms.

Effective incentive mechanisms are invaluable in crowdsensing to stimulate the enthusiasm of strategic users. However, existing work focusing on multi-task allocation with the objective of purely maximizing the social utility may result in the problem of unbalanced allocation, which may damage the social fairness. This motivates us to introduce proportional fairness into the design of a novel fairness-aware incentive mechanism for the first time. Specifically, we first model the interaction of multi-task allocation in crowdsensing as a multi-requester multi-worker Stackelberg game, and then transform the fairness-aware multi-task allocation problem into a fairness-aware incentive mechanism design problem. Next, we prove that there is a unique Stackelberg equilibrium, and also show that it can be efficiently derived through cautiously proposed algorithms. Since the existing equilibrium may not be optimal, we further design a secondary allocation rule to maximize both social utility and system performance, while achieving proportional fairness at a minimum cost. Finally, extensive experiments using both synthetic and real-world datasets demonstrate the superiority of our proposed mechanism compared to the state of the arts.

Permissioned blockchains are being widely applied to solve the trust problem in enterprise collaboration. However, most of these systems suffer from low throughput and flexibility lacking issues. In this paper, we present a blockchain system SChain with scalable concurrent execution based on a flexible architecture. SChain separates the functionality of a complete "node" into three sub-functions and assigns them to different peers within every organization. Then each organization can scale each sub-function flexibly with no need for negotiation between organizations. Based on this architecture, SChain explores scalable concurrent execution from two levels. First, SChain takes the advantage of multiple peers to execute transactions collectively, while promising they make the same results as one peer does serially. Second, SChain enables concurrent transaction execution across blocks to utilize the resources of peers fully, breaking up the block-by-block process manner, based on a pipelined workflow. The extensive evaluation results demonstrate that SChain significantly outperforms the serial execution and other competing systems-level approaches.

The emergence of digital asset applications, driven by Web 3.0 and powered by blockchain technology, has led to a growing demand for blockchain-specific graph analytics to unearth the insights. However, current blockchain data analytics systems are unable to perform efficient ad-hoc graph analytics over both live and past time windows due to their inefficient data synchronization and slow graph snapshots retrieval capability. To address these issues, we propose ChainDash, a blockchain data analytics system that dedicates a highly-parallelized data synchronization component and a retrieval-optimized temporal graph store. By leveraging these techniques, ChainDash supports efficient ad-hoc graph analytics of smart contract activities over arbitrary time windows. In the demonstration, we showcase the interactive visualization interfaces of ChainDash, where attendees will execute customized queries for ad-hoc graph analytics of blockchain data.

More and more IoT data is being traded online in cloud-based data marketplaces due to the fast-growing market demand. Within the current data selling mechanisms, data consumers have difficulties in making purchasing decisions due to uncertain IoT data quality and inflexible pricing interface. To resolve these issues, potential solutions could be to launch data demonstrations and release free sampling data to reduce the uncertainty about data quality, and to charge based on the volume of data actually used to enable flexible pricing. However, there is still no clear understanding of economic benefits of these mechanisms. In this paper, we design the optimal data selling mechanisms for IoT data exchange, and derive the following two results. First, whether to deploy a data demonstration and how much free sampling data to release depend on the extent of data consumers' inaccuracy perceptions for data quality, which varies over a wide range in IoT applications. We found that the data vendor has no incentive to conduct these strategies if data consumers extremely overestimate data quality. Second, although flexible data pricing mechanisms provide convenience for real-time and streaming IoT data exchange, it brings less economic benefits to the data vendor compared with the fixed pricing scheme, which sells the whole data set with a fixed price. We evaluate the optimal selling mechanisms on a real-world Taxi GPS data set, and evaluation results verify the insights derived from our theoretical analysis.

In the minimum cost submodular cover problem (MinSMC), we are given a monotone nondecreasing submodular function $f\colon 2^V \rightarrow \mathbb{Z}^+$, a linear cost function $c: V\rightarrow \mathbb R^{+}$, and an integer $k\leq f(V)$, the goal is to find a subset $A\subseteq V$ with the minimum cost such that $f(A)\geq k$. The MinSMC can be found at the heart of many machine learning and data mining applications. In this paper, we design a parallel algorithm for the MinSMC that takes at most $O(\frac{\log (km)\log k(\log m+\log\log (mk))}{\varepsilon^4})$ adaptive rounds, and it achieves an approximation ratio of $\frac{H(\min\{\Delta,k\})}{1-5\varepsilon}$ with probability at least $1-3\varepsilon$, where $\Delta=\max_{v\in V}f(v)$, $H(\cdot)$ is the Harmonic number, $m=|V|$, and $\varepsilon$ is a constant in $(0,\frac{1}{5})$.

It has been an open question for some time whether there exists a polynomial-time constant approximation for the lifetime scheduling problem of p-percent coverage. In this paper, we give a positive answer to this question.

Critical energy infrastructure (CEI) systems are vital to underpin the national economy and social development, but vulnerable to cyber attack and data privacy leakage when distributed machine learning technologies are deployed on them. Although federated learning (FL) has promoted distributed collaborative learning while keeping natural compliance with the privacy protection, it is tremendously difficult to schedule edge nodes of CEI collaboratively when asynchronous FL tasks are applied in CEI system, since the CEI system must make an irrevocable immediate decision on whether to hire a participant who arrives and departs dynamically without knowing future information. In this article, we tackle this issue by designing fairness-aware and time-sensitive task allocation mechanisms in asynchronous FL for CEI. First, we design an optimal multidimensional contract to guarantee the reliability, honesty, and fairness, and maximize the learning accuracy for the fixed deadline scenario. Second, we design a multimetric participant recruitment mechanism to control time consumption for the limited budget scenario, prove that the problem of optimizing this mechanism is NP-hard, and propose an$e$-approximation algorithm accordingly. Finally, extensive experiments using both real-world data and simulated data further demonstrate the effectiveness and efficiency of our proposed mechanisms compared to the state-of-the-art approaches.

Although mobile crowdsensing (MCS) has become a green paradigm of collecting, analyzing, and exploiting massive amounts of sensory data, existing incentive mechanisms are not effective to stimulate users’s active participation and service contribution in multi-service exchange in MCS due to its specific features: a large number of heterogeneous users have asymmetric service requirements, workers have the freedom to choose sensing tasks as well as participation levels, and multiple sensing tasks have heterogeneous values which may be untruthful declared by the corresponding requesters. To address this issue, this article develops a green Stackelberg-game incentive mechanism to achieve selective fairness, truthfulness, and bounded efficiency while reducing the burden on the platform. First, we model the multi-service exchange problem as a Stackelberg multi-service exchange game consisting of multi-leader and multi-follower, in which each requester as a leader first chooses the reward declaration strategy and thus the payment for each sensing task, each worker as a follower then chooses the sensing plan strategy to maximize her own utility. We next introduce the concept of virtual currency to maintain the selective fairness to balance service request and service provision between users, in which a user earns/consumes virtual currency for providing/receiving services, and thus no one can always get services without providing services. Then, we present two novel algorithms to compute the unique Nash equilibrium for the sensing plan determination game and the reward declaration determination game, respectively, which together forms a unique Stackelberg equilibrium for the proposed game. Afterwards, we theoretically prove that the proposed green Stackelberg-game incentive mechanism achieves the desirable properties of selective fairness, truthfulness, bounded efficiency. Finally, extensive evaluation results are provided to support the validity and effectiveness of our mechanism compared with both baseline and theoretical optimal approaches.

Abstract The unstable link quality in wireless sensor networks (WSNs) directly affects the success rate of data transmission. The retransmission mechanism is one of the commonly used methods to solve this problem. However, too many retransmissions could lower the communication efficiency. Therefore, to reduce retransmissions while guaranteeing the communication reliability in WSNs, this study introduces the NarrowBand Internet of Things (NB‐IoT) technology, and builds a network including both sensor and NB‐IoT nodes. The NB‐IoT node is designed to support both the radio frequency and the NarrowBand communication modes; thus it can communicate with both sensor nodes and NB‐IoT base stations. Further, the communication reliability metrics considering both the link quality and the number of retransmissions in different communication modes are defined, based on which, an adaptive communication reliability algorithm is proposed to switch the communication modes of nodes. The simulation results verify that the proposed algorithm can achieve higher success rate with less end‐to‐end delay and flexibly control the cost on NB‐IoT communication.

Given an element set E of order n, a collection of subsets [Formula: see text], a cost cSon each set [Formula: see text], a covering requirement refor each element [Formula: see text], and an integer k, the goal of a minimum partial set multicover problem (MinPSMC) is to find a subcollection [Formula: see text] to fully cover at least k elements such that the cost of [Formula: see text] is as small as possible and element e is fully covered by [Formula: see text] if it belongs to at least resets of [Formula: see text]. This problem generalizes the minimum k-union problem (MinkU) and is believed not to admit a subpolynomial approximation ratio. In this paper, we present a [Formula: see text]-approximation algorithm for MinPSMC, in which [Formula: see text] is the maximum size of a set in S. And when [Formula: see text], we present a bicriteria algorithm fully covering at least [Formula: see text] elements with approximation ratio [Formula: see text], where [Formula: see text] is a fixed number. These results are obtained by studying the minimum density subcollection problem with (or without) cardinality constraint, which might be of interest by itself.

Although crowdsourcing has emerged as a paradigm for leveraging human intelligence and activity to solve a wide range of tasks, strategic workers will find enticement in their self-interest to free-ride and attack in a crowdsourcing contest dilemma game. Existing incentive mechanisms are not effective to avoid socially undesirable equilibrium due to the following features of competitive crowdsourcing: in the presence of imperfect monitoring, heterogeneous workers with competing interest tend to beat their opponents for larger self-profit, and the fact that they can freely and frequently change their opponents makes the situation much more complicated. Taking these features into consideration, this article proposes a mechanism design problem to enforce cooperation and extort selfish works simultaneously, with the objective of maximizing the requester's utility. To solve the problem, we integrate binary ratings with differential pricing to develop a novel rating protocol. By establishing a mathematical model for the problem and quantifying necessary and sufficient conditions for a sustainable social norm, we provide design guidelines for optimal rating protocols and design a low-complexity algorithm to select optimal design parameters. Finally, extensive evaluation results demonstrate the performance of our proposed rating protocol and reveal how intrinsic parameters impact on design parameters.

Resourced‐constrained task allocation is a fundamental research problem in wireless sensor networks. While existing approaches mainly allocate the task to a single sensor node, this study proposes a novel algorithm, in which tasks are allocated to a pair of collaboratively working sensor nodes based on their intimacy. Specifically, the intimacy level of two nodes is modelled based on their link quality and preference degree. This basic idea is that each node pair should be allocated with a task whose task level (e.g. measured by the computing intensity) could match with the intimacy level of this node pair, so that each task can be executed collaboratively and efficiently. Considering that a node connecting with multiple nodes, it may be allocated with redundant tasks (tasks with the same task level), and these tasks need to be adjusted to avoid redundant task execution. Simulation results show that the proposed algorithm not only can improve the task allocation efficiency but also can balance the network energy consumption.

Macrotasking crowdsourcing systems (MCSs), such as Google Helpouts and Elance have emerged as an effective paradigm for improving human intelligence and activity to solve a wide variety of tasks. Requesters often post tasks to the MCS and competitive workers solve the tasks to earn the reward. However, rational and selfish workers in the MCS aim to strategically maximize their own benefit by exhibiting malicious behaviors, thereby decreasing the efficiency of systems. Herein, we present a novel game-theoretic mechanism to incentivize the competitive and selfish workers to provide high-quality solutions in the MCS. We first formulate the crowdsourcing problem as a multiplayer iterated game with incomplete information, where each worker has certain private information (such as solution quality), but does not know what other workers do. Subsequently, we propose an incentive mechanism in terms of zero-determinant (ZD) strategies aiming to improve the social welfare of the MCS, which serves to incentivize the competitive selfish workers toward high-quality solutions. Moreover, we find the conditions for reaching the maximum social welfare of the MCS. Numerical illustrations demonstrate a high and stable social welfare of the MCS with the proposed ZD strategies mechanism.

Online Social networks (OSNs) are now one of the main resources for people to keep abreast of current news and to exchange opinions about new products and social trends, etc. However, unethical use of OSNs also provides a convenient conduit to the diffusion of malicious rumors and misinformation, thus it is of significant importance to discover rumor diffusion and detect the rumor source. This is a very challenging task, as shown in many existing works, e.g., even in the regular tree graphs, the accuracy of detecting the information source from a diffusion snapshot cannot exceed 31%. To overcome this issue, in this work, we propose a novel system framework for information source detection in OSNs and investigate a new rumor source detection problem, called k-Minimum Distance Rumor Source Detection (k-MDRSD). Specifically, given a rumor spreading snapshot, our target is to find a small set of rumor candidates which can be used as initial seeds for further iterative query or investigation. To this end, we introduce a notion, called distance error, for rumor candidate sets and formulate the k-MDRSD problem. Resorting to methods from Combinatorics, we develop a near optimal algorithm for k-MDRSD. By experimental simulation, we show that the proposed k-MDRSD significantly improves the likelihood of detecting rumor sources or trend-setters in OSNs.

Finding a connected dominating set (CDS) in a given graph is a fundamental problem and has been studied intensively for a long time because of its application in computer science and operations research, e.g., connected facility location and wireless networks. In some cases, fault-tolerance is desirable. Taking wireless networks as an example, since wireless nodes may fail due to accidental damage or energy depletion, it is desirable that the virtual backbone has some fault-tolerance. Such a problem can be modeled as finding a minimum k-connected m-fold dominating set ((k, m)-CDS) of a graph G = (V, E), which is a node set D such that every node outside of D has at least m neighbors in D and the subgraph of G induced by D is k-connected. In this paper, we study the minimum weight (1, m)-CDS problem ((1, m)-MWCDS), and present an (H(δ + m) + 2H(δ − 1))-approximation algorithm, where δ is the maximum degree of the graph and H(·) is the Harmonic number. Notice that the state-of-the-art algorithm achieves O(l...

Modern computing systems typically use a large number of independent, non-identical computing nodes to perform a set of coordinated computations in parallel. The computing system and its constituent computing nodes often exhibit more than two performance levels or states corresponding to different computing powers. This paper models and evaluates performability of largescale multi-state computing systems, which is the probability that a computing system performs at a particular performance level. The heterogeneity in the constituent components of different nodes (due to factors such as different model generations, model suppliers, and operating environments) makes performability analysis difficult and challenging. In this paper a specification method for system performance level (SPL) is first introduced. A multi-valued decision diagram (MDD) based approach is then proposed for performability analysis of multi-state computing systems consisting of nodes with different state occupation probabilities, which encompasses novel and efficient MDD model generation procedures. Example and benchmark studies are performed to show that the proposed approach can offer efficient performability analysis of large-scale computing systems.

Despite the increasing popularity and successful examples of crowdsourcing, it is stripped of aureole when collective efforts are derailed or severely hindered by elaborate sabotage. A service exchange dilemma arises when there is non-cooperation among self-interested users, and zero social welfare is obtained at myopic equilibrium. Traditional rating protocols are not effective to overcome the inefficiency of the socially undesirable equilibrium due to specific features of crowdsourcing: a large number of anonymous users having asymmetric service requirements, different service capabilities, and dynamically joining/leaving a crowdsourcing platform with imperfect monitoring. In this paper, we develop the first game-theoretic design of the two-sided rating protocol to stimulate cooperation among self-interested users, which consists of a recommended strategy and a rating update rule. The recommended strategy recommends a desirable behavior from three predefined plans according to intrinsic parameters, while the rating update rule involves the update of ratings of both users, and uses differential punishments that punish users with different ratings differently. By quantifying necessary and sufficient conditions for a sustainable social norm, we formulate the problem of designing an optimal two-sided rating protocol that maximizes the social welfare among all sustainable protocols, provide design guidelines for optimal two-sided rating protocols and a low-complexity algorithm to select optimal design parameters in an alternate manner. Finally, evaluation results show the validity and effectiveness of our protocol designed for service exchange dilemma in crowdsourcing.

In this paper, we investigate a largely extended version of classical MAB problem, called networked combinatorial bandit problems. In particular, we consider the setting of a decision maker over a networked bandits as follows: each time a combinatorial strategy, e.g., a group of arms, ischosen, and the decision maker receives a rewardresulting from her strategy and also receives a side bonusresulting from that strategy for each arm's neighbor. This is motivated by many real applications such as on-line social networks where friends can provide their feedback on shared content, therefore if we promote a product to a user, we can also collect feedback from her friends on that product. To this end, we consider two types of side bonus in this study: side observation and side reward. Upon the number of arms pulled at each time slot, we study two cases: single-play and combinatorial-play. Consequently, this leaves us four scenarios to investigate in the presence of side bonus: Single-play with Side Observation, Combinatorial-play with Side Observation, Single-play with Side Reward, and Combinatorial-play with Side Reward. For each case, we present and analyze a series of zero regret polices where the expect of regret over time approaches zero as time goes to infinity. Extensive simulations validate the effectiveness of our results.

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).

To save energy and alleviate interference, connected dominating set (CDS) was proposed to serve as a virtual backbone of wireless sensor networks (WSNs). Because sensor nodes may fail due to accidental damages or energy depletion, it is desirable to construct a fault tolerant virtual backbone with high redundancy in both coverage and connectivity. This can be modeled as a k-connected m-fold dominating set (abbreviated as (k, m)-CDS) problem. A node set C ⊆ V (G) is a (k, m)-CDS of graph G if every node in V(G)\C is adjacent with at least m nodes in C and the subgraph of G induced by C is k-connected. Constant approximation algorithm is known for (3, m)-CDS in unit disk graph, which models homogeneous WSNs. In this paper, we present the first performance guaranteed approximation algorithm for (3, m)-CDS in a heterogeneous WSN. In fact, our performance ratio is valid for any topology. The performance ratio is at most γ, where γ = α + 8 + 2 ln(2α - 6) for α ≥ 4 and γ = 3α +2 ln 2 for α <; 4, and α is the performance ratio for the minimum (2, m)-CDS problem. Using currently best known value of α, the performance ratio is ln δ +o(ln δ), where δ is the maximum degree of the graph, which is asymptotically best possible in view of the non-approximability of the problem. Applying our algorithm on a unit disk graph, the performance ratio is less than 27, improving previous ratio 62.3 by a large amount for the (3, m)-CDS problem on a unit disk graph.

Using a connected dominating set (CDS) to serve as a virtual backbone of a wireless sensor network is an effective way to save energy and alleviate broadcasting storm. Since nodes may fail due to accidental damage or energy depletion, it is desirable to construct a fault tolerant CDS, which can be modeled as a k-connected m-fold dominating set ((k, m)-CDS for short). A subset of nodes C ⊆ V(G) is a (k, m)-CDS of G if every node in V(G)\C is adjacent with at least m nodes in C and the subgraph of G induced by C is k-connected. In this paper, we present an approximation algorithm for the minimum (3, m)-CDS problem with m > 3, which has size at most γ times that of an optimal solution, where γ = α + 8 + 21n(2α - 6) for α > 4 and γ = 3α + 2 In 2 for α <; 4, and α is the approximation ratio for the minimum (2, m)-CDS problem. This is the first performance-guaranteed algorithm for the minimum (3, m)-CDS problem in a general wireless network, and improves previous performance ratio in a homogeneous wireless sensor network by a large amount.

We wonder that in a competitive environment, how an influence uses the minimum cost to choose seeds such that its influence spread can reach a desired threshold under thwarting from its competitors. At first we take a simple fact into account: the information arriving first has heavy impact, and present Competitive — Independent Cascade (C-IC) model to characterize how different influences competing with others in a social network. We have found that a specific influence's spread is monotone and submodular, and these nice properties make algorithm performance tractable. We then propose Minimum Cost Seed Set problem (MinSeed) to answer our original concern and give a greedy algorithm. We analyze the ratio of greedy algorithm, and give result significantly better than similar ones analyzed by others. Noticing that the computation of real information spread is hard to compute and simple greedy is too time consuming, we design an effective method for estimating information spread in C-IC model, and devise scalable algorithm applying for large social networks. Through simulation on real world datasets, we confirm that, our scalable algorithm outputs seed set with small total cost comparable to that given by simple greedy, with very fast computation.

In a network system, a propagated failure (PF) is a failure originating from a network component that can cause extensive damages to other network components or even the failure of the entire system. Existing works on PFs have mostly assumed the deterministic effect from a component PF, i.e., a fixed subset of system components is affected whenever the PF occurs. However, in many real-world systems, the components may have different levels of protection, and the effect of damage from a component PF can be dependent upon the status of other components within the same system or the occurrence order of component failures. This paper proposes a new analytical method based on multi-valued decision diagrams (MDDs) for the reliability analysis of network systems with dependent propagation effects. Particularly, new MDD modeling procedures are proposed for considering different types of dependent PF effects introduced by different protection levels. After the system MDD is generated using a new MDD combination algorithm to efficiently handle the dependent PF effects, methods for computing the network reliability and component importance measures are presented. The detailed analysis of an example network system subjected to dependent PFs is presented to illustrate the basics and application of the proposed method. It is shown that the proposed MDD-based method generates smaller model size and thus presents lower computational complexity in the model generation and evaluation than the existing Markov method and separable method.

Energy efficiency is an important issue in the study of wireless sensor networks. Given a set of targets and a set of sensors with bounded lifetime, the maximum lifetime k-coverage problem is to schedule active/sleeping status of sensors to maximize the time period during which every target is covered by at least k active sensors. Previously, it was known that when the sensing ranges are uniform, this problem has a polynomial time (4+ε)-approximation for k = 1 and (6+ε)-approximation for k = 2. In this paper, we make significant progress by showing that for any positive integer k, there exists a polynomial-time (3 + ε)-approximation.

Energy efficiency is an important issue in the study of wireless sensor networks. Given a homogeneous set of sensors with unit lifetime and a set of target points, find an active/sleeping schedule for sensors to maximize the lifetime of k-coverage, i.e., the time period during which every target point is covered by at least k active sensors. This is a well known problem in wireless sensor networks concerning with energy efficiency. When k = 1, it is called the maximum lifetime coverage problem which has been proved to have a polynomial-time (4 + ε)-approximation. When k ≥ 2, it is the maximum lifetime fault-tolerant coverage problem. Previous to this work, only in the case k = 2, a polynomial-time (6 + ε)-approximation is found. In this paper, we will make a significant progress by showing that for any positive integer k, there exists a polynomial-time (4 + ε)-approximation, and for k = 1,2, the performance ratio can be improved to (3 + ε).

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.

In this paper, we study the problem of computing quality fault-tolerant virtual backbone in homogeneous wireless network, which is defined as the$k$-connected$m$-dominating set problem in a unit disk graph. This problem is NP-hard, and thus many efforts have been made to find a constant factor approximation algorithm for it, but never succeeded so far with arbitrary$k\geq 3$and$m\geq 1$pair. We propose a new strategy for computing a smaller-size 3-connected$m$-dominating set in a unit disk graph with any$m\geq 1$. We show the approximation ratio of our algorithm is constant and its running time is polynomial. We also conduct a simulation to examine the average performance of our algorithm. Our result implies that while there exists a constant factor approximation algorithm for the$k$-connected$m$-dominating set problem with arbitrary$k\leq 3$and$m\geq 1$pair, the$k$-connected$m$-dominating set problem is still open with$k>3$.

In this paper, we study the problem of constructing quality fault-tolerant Connected Dominating Sets (CDSs)in homogeneous wireless networks, which can be defined as minimum k-Connected m-Dominating Set ((k,m)-CDS) problem in Unit Disk Graphs (UDGs). We found that every existing approximation algorithm for this problem is incomplete for k ¿3 in a sense that it does not generate a feasible solution in some UDGs. Based on these observations, we propose a new polynomial time approximation algorithm for computing (3,m)-CDSs. We also show that our algorithm is correct and its approximation ratio is a constant.

Abstract An edge set S is a k‐restricted edge cut of a connected graph G if G‐S is no longer connected and every component of G‐S has at least k vertices. The k‐restricted edge connectivity of G, denoted by λk(G), is the cardinality of a minimum k‐restricted edge cut. A graph G with λk(G) = ξk(G) is called λk‐optimal, where ξk(G) = min{∣U,Ū∣ ∣ U ⊂ V(G),∣U∣ = k and GU is connected}, ∣U,Ū∣ is the number of edges between U and Ū, GU is the subgraph of G induced by U. In this article, we give a sufficient condition for a graph to be λk‐optimal: for any integer k ≥ 3, every graph G with girth g ≥ 5, minimum degree δ ≥ k, and diameter D ≤ g ‐ 4 when g is even and D ≤ g ‐ 3 when g is odd is λk‐optimal. Furthermore, if δ ≥ 2k ‐ 3, the diameter condition can be relaxed a little to D ≤ g ‐ 3 no matter whether g is even or odd. This generalizes a result of Balbuena et al. [Sufficient conditions for λ′‐optimality in graphs with girth g, J Graph Theory 52 (2006) 73–86], and improves a result of Fàbrega and Fiol in a sense [On the extraconnectivity of graphs, Discrete Math 155 (1996) 49–57]. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

A Virtual Backbone (VB) of a wireless network is a subset of nodes such that only VB nodes are responsible for routing-related tasks. Since a smaller VB causes less overhead, size is the primary quality factor of VB. Frequently, Unit Disk Graphs (UDGs) are used to model 2D homogeneous wireless networks, and the problem of finding minimum VBs in the networks is abstracted as Minimum Connected Dominating Set (MCDS) problem in UDGs. In some applications, the altitude of nodes can be hugely different and UDG cannot abstract the networks accurately. Then, Unit Ball Graph (UBG) can replace UDG. In this paper, we study how to construct quality CDSs in UBGs in distributed environments. We first give an improved upper bound of the number of independent nodes in a UBG, and use this result to analyze the Performance Ratio (PR) of our new centralized algorithm C-CDS-UBG, which computes CDSs in UBGs. Next, we propose a distributed algorithm D-CDS-UBG originated from C-CDS-UBG and analyze its message and time complexities. Our theoretical analysis shows that the PR of D-CDS-UBG is 14.937, which is better than current best, 22. Our simulations also show that D-CDS-UBG outperforms the competitor, on average.

In a distributed database system, data replicas are placed at different locations to achieve high data availability in the presence of link failures. With majority voting protocol, a location is survived for read/write operations if and only if it is accessible to more than half of the replicas. The problem is to find out the optimal placements for a given number of data replicas in a ring network. When the number of replicas is odd, it was conjectured by Hu et al. that every uniform placement is optimal, which is proved by Shekhar and Wu later. However, when the number of replicas is even, it was pointed out by Hu et al. that uniform placements are not optimal and the optimal placement problem may be very complicated. In this paper, we study the optimal placement problem in a ring network with majority voting protocol and even number of replicas, and give a complete characterization of optimal placements when the number of replicas is not too large compared with the number of locations.