Weili Wu

TCS Journal 2025 Journal Article

Efficient algorithm for stochastic rumor blocking problem in social networks during safety accident period

• Jianming Zhu
• Ye Xing
• Runzhi Li
• Smita Ghosh
• Priyanshi Garg
• Weili Wu

Rumor sources spread negative information throughout the network, which may cause unbelievable results in real society especially for social safety field. Propagating positive information from several “protector” users is an effective method for rumor blocking once the rumor is detected. Based on the probability of each user being a rumor, “protector” nodes need to be selected in order to prepare for rumor blocking. Given a social network G = ( V, E, P, Q ), where P ( u, v ) is the probability that v is activated by u after u is activated, and Q is the weight function on node set V, Q v is the probability that v will be a rumor source. Stochastic Rumor Blocking (SRB) problem is to select k nodes as “protector” such that the expected eventually influenced users by rumor is minimized. SRB will be proved to be NP-hard and the objective function is supermodular. We present a Compound Reverse Influence Set sampling method for estimation of the objective value which can be represented as a compound set function. A randomized greedy algorithm with theoretical analysis will be presented and other two different “protector” selection strategies will be proposed for comparison. Finally, we evaluate our algorithm on real world data sets and do comparison among different strategies.

TCS Journal 2023 Journal Article

Profit maximization in social networks and non-monotone DR-submodular maximization

• Shuyang Gu
• Chuangen Gao
• Jun Huang
• Weili Wu

In this paper, we study the non-monotone DR-submodular function maximization over integer lattice. Functions over integer lattice have been defined submodular property that is similar to submodularity of set functions. DR-submodular is a further extended submodular concept for functions over the integer lattice, which captures the diminishing return property. Such functions find many applications in machine learning, social networks, wireless networks, etc. The techniques for submodular set function maximization can be applied to DR-submodular function maximization, e. g. , the double greedy algorithm has a 1/2-approximation ratio, whose running time is O ( n B ), where n is the size of the ground set, B is the integer bound of a coordinate. In our study, we design a 1/2-approximate binary search double greedy algorithm, and we prove that its time complexity is O ( n log ⁡ B ), which significantly improves the running time. Specifically, we consider its application to the profit maximization problem in social networks with a bipartite model, the goal of this problem is to maximize the net profit gained from a product promoting activity, which is the difference of the influence gain and the promoting cost. We prove that the objective function is DR-submodular over integer lattice. We apply binary search double greedy algorithm to this problem and verify the effectiveness.

TCS Journal 2022 Journal Article

Union acceptable profit maximization in social networks

• Guoyao Rao
• Yongcai Wang
• Wenping Chen
• Deying Li
• Weili Wu

Online social network has deeply changed our lives, such as the style of communication and business, and hence promotes a lot of researches in social influence. The prior works in social influence mainly consider the influence from the view of individuals. However, in many cases, influencing the most of members of an important group such as the board of directors in a company can bring bigger profit than directly influencing the individuals of the company. We call such high profit group which obeys the vote rule as an union, different from existed targeted influence model, we consider such scenarios to make union acceptable and propose the union acceptable profit problem (UAPM) to choose seeds to maximize the union-acceptable profit, i. e. , maximize the probability of the union being acceptable. The objective of profit in UAPM is #P-hard, and not submodularity or supmodularity. To solve the problem, we propose an efficient estimation method for the objective and design a heuristic algorithm and further a data-driven β ( 1 − 1 ϵ ) -approximation algorithm where β is the data-driven parameter which is related to the input data. At last we evaluate the performance of the algorithms we proposed on effectiveness and efficiency by the experiments in real-world social network datasets.

TCS Journal 2021 Journal Article

A constrained two-stage submodular maximization

• Ruiqi Yang
• Shuyang Gu
• Chuangen Gao
• Weili Wu
• Hua Wang
• Dachuan Xu

In this paper, we investigate the two-stage submodular maximization problem, where there is a collection F = { f 1, .. ., f m } of m submodular functions which are defined on the same element ground set Ω. The goal is to select a subset S ⊆ Ω of size at most ℓ such that 1 m ∑ f ∈ F max T ⊆ S, T ∈ I ⁡ f ( T ) is maximized, where I denotes a specifically-defined independence system. We consider the two-stage submodular maximization with a P-matroid constraint and present a ( 1 / ( P + 1 ) ) ( 1 − 1 / e ( P + 1 ) ) -approximation algorithm. Furthermore, we extend the algorithm to the two-stage submodular maximization with a more generalized P-exchange system constraint and show the approximation ratio can be maintained with slightly modifications of the algorithm.

TCS Journal 2021 Journal Article

Matching influence maximization in social networks

• Guoyao Rao
• Yongcai Wang
• Wenping Chen
• Deying Li
• Weili Wu

Influence maximization (IM) is a widely studied problem in social networks, which aims at finding a seed set with limited size that can maximize the expected number of influenced users. However, existing studies haven't considered the matching relationship, which refers to such scenarios that influenced users seek matched partners among the influenced users, such as time matching with friends to watch movie, or matching for opposite sex in the blind date. In this paper, we investigate different matching scenarios and propose online-matching (offline-matching), in which the matching and influence propagation are simultaneous (asynchronous). For the matching result, we introduce two matched types ‘s- m a t c h e d ’, i. e. , i → j and ‘d- m a t c h e d ’, i. e. , i ↔ j. Then, we formulate the matching influence maximization (MM) problem to optimize a limited seed set that maximizes the expected number of matched users. We prove that the MM problem is NP-hard and the computation of the matching influence is #P-hard. Next, we analyze the submodularity of the matching influence. To address the problem, we propose efficient methods OPMM (SAMM) to solve the MM in online-matching (offline-matching) with ( 1 − 1 / e − ϵ ) -approximation ( β ( 1 − 1 / e − ϵ ) -approximation) guarantee. Experiments on the real-world datasets show our algorithms outperform state of the art algorithms in terms of more accurate matching propagation results.

TCS Journal 2021 Journal Article

Mixed-case community detection problem in social networks: Algorithms and analysis

• Yapu Zhang
• Jianxiong Guo
• Wenguo Yang
• Weili Wu

The problem of detecting communities is one of the essential problems in the study of social networks. To devise the algorithms of community detection, one should first define high-quality communities. In fact, there are no agreed methods to measure the quality of the community. In this paper, we consider a novel objective function of this problem. Our goal is to maximize not only the average of the sum of edge weights within communities (i. e. , average-case) but also the sum of edge weights within the minimum community (i. e. , worst-case). To balance both the average-case and worst-case problems, we introduce a parameter into our objective function and call it the mixed-cased community detection problem. For the worst-case, we devise several approximation algorithms, such as the Greedy, Semi-Sandwich Approximation, and Local Search algorithms. For the average-case, an efficient Terminal-based algorithm is proposed. We prove that the best solution between the average-case and worst-case problems still can provide an approximate guarantee for any mixed-case community detection problem. Moreover, we devise a heuristic algorithm for our problem. Finally, we conduct the experiments in three networks. The experimental results indicate that our proposed methods can form a high-quality community partition.

TCS Journal 2021 Journal Article

Optimal wireless charger placement with individual energy requirement

• Xingjian Ding
• Jianxiong Guo
• Deying Li
• Weili Wu

Supply energy to battery-powered sensor devices by deploying wireless chargers is a promising way to prolong the operation time of wireless sensor networks, and has attracted much attention recently. Existing works focus on maximizing the total received charging power of the network. However, this may face the unbalanced energy allocation problem, which is not beneficial to prolong the operation time of wireless sensor networks. In this paper, we consider the individual energy requirement of each sensor node, and study the problem of minimum charger placement. That is, we focus on finding a strategy for placing wireless chargers from a given candidate location set, such that each sensor node's energy requirement can be met, meanwhile the total number of used chargers can be minimized. We deal with the problem under both omnidirectional and directional charging models, and prove its NP-hardness. For the omnidirectional charging case, we present two approximation algorithms which are based on greedy scheme and relax rounding scheme, respectively. We prove that both of the two algorithms have performance guarantees. For the directional charging case, we first extract the candidate orientation set for each candidate location to reduce the search space from infinite to a limited set, and then propose a greedy algorithm that also has a proved performance guarantee. Finally, we validate the performance of our algorithms by performing extensive numerical simulations. Simulation results show the effectiveness of our proposed algorithms.

TCS Journal 2021 Journal Article

Optimizing flight trajectory of UAV for efficient data collection in wireless sensor networks

• Chuanwen Luo
• Wenping Chen
• Deying Li
• Yongcai Wang
• Hongwei Du
• Lidong Wu
• Weili Wu

Unmanned Aerial Vehicles (UAVs) are expected to be important components in the upcoming wireless communication field, which are increasingly used as data collectors to gather sensory data from Wireless Sensor Networks (WSNs) due to their high mobility, flexible deployment. Since the storage capacity and lifetime of sensors are increasing with the development of science and technology, sensors can store more and more sensing data about the monitoring area. However, due to the energy limitation of UAVs and a large amount of data carried by sensors, we can not collect all data from WSN within the limited time. Therefore, in this paper, we investigate two problems: (1) without the energy limitation of UAV, how to optimize the trajectory of UAV to minimize the sum of traveling time and data transmission time of UAV while guaranteeing the amount of data collected from each sensor reaches to a certain proportion of the original data, which is called the Minimizing Transportation and Communication Latency (MTCL) problem; (2) given the limited budget of UAV, how to find the optimal trajectory of UAV to maximize the minimum ratio of the collected data to the stored data among all sensors, which is called the Maximizing Data Collection Proportion (MDCP) problem. We first prove that both the problems are NP-Complete. Then we study a special case of the MTCL problem, which is called the MTCL-disjoint problem, in which any pair of data collection areas are disjoint, and we propose an approximation algorithm to solve the MTCL-disjoint problem. Based on the MTCL-disjoint problem, we propose an approximation algorithm for the general MTCL problem. Afterward, an approximation algorithm for the MDCP problem is proposed on the basis of the algorithm for the MTCL problem. Finally, we present numerical results in different scenarios to assess the effectiveness of the proposed algorithms.

TCS Journal 2020 Journal Article

A random algorithm for profit maximization in online social networks

• Tiantian Chen
• Bin Liu
• Wenjing Liu
• Qizhi Fang
• Jing Yuan
• Weili Wu

Given a social network G and a positive integer k, the influence maximization problem seeks for k nodes in G that can influence the largest number of nodes. This problem has found important applications, and a large amount of works have been devoted to identifying the few most influential users. But most of existing works only focus on the diffusion of a single idea or product in social networks. However, in reality, one company may produce multiple kinds of products and one user may also have multiple adoptions. For multiple kinds of different products with different activation costs and profits, it is crucial for the company to distribute the limited budget among multiple products in order to achieve profit maximization. The Profit Maximization with Multiple Adoptions (PM2A) problem aims to seek for a seed set within the budget to maximize the overall profit. In this paper, a Randomized Modified Greedy (RMG) algorithm based on the Reverse Influence Sampling (RIS) technique is presented for the PM2A problem, which could achieve a ( 1 − 1 / e − ε ) -approximate solution with high probability and is also the best performance ratio of the PM2A problem. Comprehensive experiments on three real-world social networks are conducted, and the results demonstrate that our RMG algorithm outperforms the algorithm proposed in [16] and other heuristics in terms of profit maximization, and could better allocate the budget.

TCS Journal 2020 Journal Article

A semantic relatedness preserved subset extraction method for language corpora based on pseudo-Boolean optimization

• Luobing Dong
• Qiumin Guo
• Weili Wu
• Meghana N. Satpute

As language corpora have been playing an increasingly important role in the field of Artificial Intelligence (AI) research, lots of extremely large corpora are created. However, a larger corpora size not only increases power and accuracy but also brings redundancy. Therefore, researchers began to emphasize the study of appropriate subset extraction methods. Due to the trade-off between data sufficiency and redundancy, a group of interesting and challenging problems are emerged that are studied in this paper: (1) How to make the resulting subset include as much data as possible under some necessary constraints? (2) How to preserve the potential useful semantic relatedness included in the original corpora while reducing the size of the corpora? For these two problems, existing work mainly focuses on the methods to construct particular subsets for special usage. These methods are limited in their focus. In this paper, we try to address the problems listed above. First, considering the cubic and binary semantic relatedness among tokens, we construct a general system model and formulate the mix problem as a cubic pseudo-Boolean optimization problem. Then, by analyzing the characteristics of the objective function, we transfer the problem into the maximum flow problem of a corresponding graph. Third, we propose a new algorithm by introducing discrete Lagrangian iteration method. We prove that the objective function is supermodular, which allows us to use fast minimum cut algorithms in each iteration step to propose another fast algorithm. Finally, we experimentally validate our new algorithms on several randomly created corpora.

TCS Journal 2020 Journal Article

Community-based rumor blocking maximization in social networks: Algorithms and analysis

• Qiufen Ni
• Jianxiong Guo
• Chuanhe Huang
• Weili Wu

Social networks provide us a convenient platform to communicate and share information or ideas with each other, but it also causes many negative effects at the same time, such as, the spread of misinformation or rumor in social networks may cause public panic and even serious economic or political crisis. In this paper, we propose a Community-based Rumor Blocking Problem (CRBMP), i. e. , selecting a set of seed users from all communities as protectors with the constraint of budget b such that the expected number of users eventually not being influenced by rumor sources is maximized. We consider the community structure in social networks and solve our problem in two stages, in the first stage, we allocate budget b for all the communities, this sub-problem whose objective function is proved to be monotone and DR-submodular, so we can use the method of submodular function maximization on an integer lattice, which is different from most of the existing work with the submodular function over a set function. Then a greedy community budget allocation algorithm is devised to get an 1 − 1 / e approximation ratio; we also propose a speed-up greedy algorithm which greatly reduces the time complexity for the community budget allocation and can get an 1 − 1 / e − ϵ approximation guarantee meanwhile. Next we solve the Protector Seed Selection (PSS) problem in the second stage after we obtained the budget allocation vector for communities, we greedily choose protectors for each community with the budget constraints to achieve the maximization of the influence of protectors. The greedy algorithm for PSS problem can achieve a 1/2 approximation guarantee. We also consider a special case where the rumor just originates from one community and does not spread out of its own community before the protectors are selected, the proposed algorithm can reduce the computational cost than the general greedy algorithm since we remove the uninfected communities. Finally, we conduct extensive experiments on three real world data sets, the results demonstrate the effectiveness of the proposed algorithm and its superiority over other methods.

TCS Journal 2020 Journal Article

Delivery Route Optimization with automated vehicle in smart urban environment

• Chuanwen Luo
• Deying Li
• Xingjian Ding
• Weili Wu

As a part of the smart urban construction, automated driving is introduced to improve the utilization efficiency of cars and roads, which not only reduces the incidence of traffic accidents, but also improves the environment quality. With the development of the smart urban, it is predictable that, in the city of the future, the service of package pickup and delivery or takeout will be supported mainly by automated vehicles. However, the existing works mainly focus on the variants of the Vehicle Routing Problem (VRP), in which they either take no account of service time of automated vehicle for customers when the automated vehicle arrives at the locations of customers or ignore the impact of rewards gained from customers on path planning of the automated vehicles. In this paper, we also extend a variant of VRP where an automated vehicle is used to package delivery or distribution of food in the smart urban environment, which is called the Delivery Reward Maximization (DRM) problem. The problem aims at designing a route of the automated vehicle while considering the service time for customers before their deadlines and the impact of rewards of the automated vehicle on path planning. We first prove that the DRM problem is NP-hard. Then we study two special cases of the DRM problem, which are called Linear DRM (LDRM) problem and Two-dimensional DRM (TDRM) problem, respectively. In the LDRM and TDRM problems, all customers have the same visiting deadlines and are deployed on the one-dimensional line and two-dimensional plane, respectively. Then we prove that the LDRM and TDRM problems are also NP-hard and propose a constant approximation algorithm for each of them. Afterward, we propose a greedy algorithm to solve the DRM problem, and give the analysis by counterexample.

TCS Journal 2020 Journal Article

Information coverage maximization for multiple products in social networks

• Qiufen Ni
• Jianxiong Guo
• Chuanhe Huang
• Weili Wu

Different from most existing work which is focus on maximizing the influence of a single product in viral marketing, we study the k kinds of products information coverage maximization problem (k-PICMP). Since a company usually produces different products for different people and the active node set cannot completely represent the coverage of the products information propagation due to the neglect for informed users, our problem has its practical significance. The target of the k-PICMP is to choose M users to maximize the information coverage of k kinds of products. To give a high-quality solution for the proposed problem under the IC model, we formulate the k-PICMP as two different problems: k-PICMTP with total size constraint and k-PICMIP with individual size constraint. Then we prove that the objective function we want to solve is a k-submodular function, it aims at maximizing the value of the function by selecting k disjoint seed sets with cardinality constraint. Next, we present greedy algorithms under the total size constraint and individual size constraint to solve the k-PICMTP and k-PICMIP, respectively. Extensive experiments on three real-world datasets verify the performance of our proposed algorithms.

TCS Journal 2020 Journal Article

Interaction-aware influence maximization and iterated sandwich method

• Chuangen Gao
• Shuyang Gu
• Ruiqi Yang
• Jiguo Yu
• Weili Wu
• Dachuan Xu

Influence maximization problem has been studied extensively with the development of online social networks. Most of the existing works focus on the maximization of influence spread under the assumption that the number of influenced users determines the success of a product promotion. However, the profit of some products such as online game depends on the interactions among users besides the number of users. In this paper, we take both the number of active users and the user-to-user interactions into account and propose the interaction-aware influence maximization problem. To address this practical issue, we analyze its complexity and modularity, propose the sandwich theory which is based on decomposing the non-submodular objective function into the difference of two submodular functions and design two iterated sandwich algorithms which are guaranteed to get data dependent approximation solution. Through real data sets, we verify the effectiveness of our proposed algorithms.

TCS Journal 2020 Journal Article

Profit Maximization problem with Coupons in social networks

• Bin Liu
• Xiao Li
• Huijuan Wang
• Qizhi Fang
• Junyu Dong
• Weili Wu

Viral marketing has become one of the most effective marketing strategies. In the process of real commercialization, in order to let some seed individuals know the products, companies can provide free samples to them. However, for some companies, especially famous ones, they are more willing to offer coupons than give samples. In this paper, we consider the Profit Maximization problem with Coupons (PM-C) in our new diffusion model named the Independent Cascade Model with Coupons and Valuations (IC-CV). To solve this problem, we propose the PMCA algorithm which can return a ( 1 3 − ε ) -approximate solution with at least 1 − 2 n − l probability, and runs in O ( log ⁡ ( n p ) ⋅ m n 3 log ⁡ n ( l log ⁡ n + n log ⁡ 2 ) / ε 3 ) expected time. Furthermore, during the analysis we provide a method to estimate the non-monotone submodular function.

TCS Journal 2020 Journal Article

Viral marketing of online game by DS decomposition in social networks

• Chuangen Gao
• Hai Du
• Weili Wu
• Hua Wang

In social networks, the spread of influence has been studied extensively, but most efforts in existing literature are made on the product used by a single person. This paper attempts to address the product which is used by many persons such as the online game. When multiple people participate in one game, interaction between users is accompanied by browsing and clicking on advertisements, and operators can also earn certain advertising revenues. All these revenues are related to information interaction between people involved in one game. We use game profit to represent all of the revenues gained from players involved in one game and model the game profit maximization problem in social networks, which finds a seed set to maximize the game profit between players who are influenced to buy the game. We prove that the problem is NP-hard and the objective function is neither submodular nor supermodular. To solve it, we decompose it into the Difference between two Submodular functions (DS decomposition) and propose four heuristic algorithms. To address the complexity of computing objective function, we design a new sampling method based on reverse reachable set technology. Experiment results on real datasets show that our approaches perform well.

NeurIPS Conference 2018 Conference Paper

On Misinformation Containment in Online Social Networks

• Amo Tong
• Ding-Zhu Du
• Weili Wu

The widespread online misinformation could cause public panic and serious economic damages. The misinformation containment problem aims at limiting the spread of misinformation in online social networks by launching competing campaigns. Motivated by realistic scenarios, we present the first analysis of the misinformation containment problem for the case when an arbitrary number of cascades are allowed. This paper makes four contributions. First, we provide a formal model for multi-cascade diffusion and introduce an important concept called as cascade priority. Second, we show that the misinformation containment problem cannot be approximated within a factor of $\Omega(2^{\log^{1-\epsilon}n^4})$ in polynomial time unless $NP \subseteq DTIME(n^{\polylog{n}})$. Third, we introduce several types of cascade priority that are frequently seen in real social networks. Finally, we design novel algorithms for solving the misinformation containment problem. The effectiveness of the proposed algorithm is supported by encouraging experimental results.

TCS Journal 2016 Journal Article

Approximation algorithm for the balanced 2-connected k-partition problem

• Di Wu
• Zhao Zhang
• Weili Wu

For two positive integers m, k and a connected graph G = ( V, E ) with a nonnegative vertex weight function w, the balanced m-connected k-partition problem, denoted as BC m P k, is to find a partition of V into k disjoint nonempty vertex subsets ( V 1, V 2, …, V k ) such that each G [ V i ] (the subgraph of G induced by V i ) is m-connected, and min 1 ≤ i ≤ k ⁡ { w ( V i ) } is maximized. The optimal value of BC m P k on graph G is denoted as β m ⁎ ( G, k ), that is, β m ⁎ ( G, k ) = max ⁡ min 1 ≤ i ≤ k ⁡ { w ( V i ) }, where the maximum is taken over all m-connected k-partition of G. In this paper, we study the BC 2 P k problem on interval graphs, and obtain the following results. (1) For k = 2, a 4/3-approximation algorithm is given for BC 2 P 2 on 4-connected interval graphs. (2) In the case that there exists a vertex v with weight at least W / k, where W is the total weight of the graph, we prove that the BC 2 P k problem on a 2k-connected interval graph G can be reduced to the BC 2 P k − 1 problem on the ( 2 k − 1 ) -connected interval graph G − v. In the case that every vertex has weight at most W / k, we prove a lower bound β 2 ⁎ ( G, k ) ≥ W / ( 2 k − 1 ) for 2k-connected interval graph G. (3) Assuming that weight w is integral, a pseudo-polynomial time algorithm is obtained. Combining this pseudo-polynomial time algorithm with the above lower bound, a fully polynomial time approximation scheme (FPTAS) is obtained for the BC 2 P k problem on 2k-connected interval graphs.

TCS Journal 2014 Journal Article

Mining hidden links in social networks to achieve equilibrium

• Huan Ma
• Zaixin Lu
• Deying Li
• Yuqing Zhu
• Lidan Fan
• Weili Wu

Although more connections between individuals in a social network can be identified with the development of high techniques, to obtain the complete relation information between individuals is still hard due to complex structure and individual privacy. However, the social networks have communities. In our work, we aim at mining the invisible or missing relations between individuals within a community in social networks. We propose our algorithm according to the fact that the individuals exist in communities satisfying Nash equilibrium, which is borrowed from game-theoretic concepts often used in economic researches. Each hidden relation is explored through the individual's loyalty to their community. To the best of our knowledge, this is the first work that studies the problem of mining hidden links from the aspect of Nash equilibrium. Eventually we confirm our approach's superiority from extensive experiments over real-world social networks.

TCS Journal 2013 Journal Article

Algebraic data retrieval algorithms for multi-channel wireless data broadcast

• Xiaofeng Gao
• Zaixin Lu
• Weili Wu
• Bin Fu

Wireless data broadcast is an important data dissemination method for distributing public information to mobile users. Due to the exponentially increasing number of mobile network users, it is necessary to develop efficient data retrieval protocols for end users to download data items effectively. In this paper, we concentrate on investigating scheduling algorithms for retrieving a set of data items from a multichannel wireless data broadcast system. As we know, the most important issues in mobile computing are energy efficiency and query response efficiency. However, in data broadcast the objectives of reducing access latency and energy cost can be contradictive to each other. Consequently, we define a new problem named Minimum Constraint Data Retrieval Problem (MCDR). We prove that MCDR is NP-hard, and then show a fixed parameter tractable algorithm which can balance two factors together. It has computational time O ( 2 k ( h n t ) O ( 1 ) ), where n is the number of channels, k is the number of required data items, t is the maximal time slot, and h is the maximal number of channel switches.

TCS Journal 2012 Journal Article

Preface

• Weili Wu
• Ovidiu Daescu

TCS Journal 2011 Journal Article

DNA library screening, pooling design and unitary spaces

• Suogang Gao
• Zengti Li
• Jiangchen Yu
• Xiaofeng Gao
• Weili Wu

Pooling design is an important research topic in bio-informatics due to its wide applications in molecular biology, especially DNA library screening. In this paper, with unitary spaces over finite fields, we present two new constructions whose efficiency ratio, i. e. , the ratio between the number of tests and the number of items, is smaller than some of the existing constructions.

TCS Journal 2011 Journal Article

New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

• Feng Zou
• Yuexuan Wang
• Xiao-Hua Xu
• Xianyue Li
• Hongwei Du
• Pengjun Wan
• Weili Wu

Given a node-weighted graph, the minimum-weighted dominating set (MWDS) problem is to find a minimum-weighted vertex subset such that, for any vertex, it is contained in this subset or it has a neighbor contained in this set. And the minimum-weighted connected dominating set (MWCDS) problem is to find a MWDS such that the graph induced by this subset is connected. In this paper, we study these two problems on a unit disk graph. A (4 + ε )-approximation algorithm for an MWDS based on a dynamic programming algorithm for a Min-Weight Chromatic Disk Cover is presented. Meanwhile, we also propose a (1 + ε )-approximation algorithm for the connecting part by showing a polynomial-time approximation scheme for a Node-Weighted Steiner Tree problem when the given terminal set is c-local and thus obtain a (5 + ε )-approximation algorithm for an MWCDS.

TCS Journal 2009 Journal Article

Algorithms for connected set cover problem and fault-tolerant connected set cover problem

• Zhao Zhang
• Xiaofeng Gao
• Weili Wu

Given a set V of elements, S a family of subsets of V, and G a connected graph on vertex set S, a connected set cover (CSC) is a subfamily R of S such that every element in V is covered by at least one set of R, and the subgraph G [ R ] of G induced by R is connected. If furthermore G [ R ] is k -connected and every element in V is covered by at least m sets in R, then R is a ( k, m ) -CSC. In this paper, we present two approximation algorithms for the minimum CSC problem, and one approximation algorithm for the minimum ( 2, m ) -CSC problem. Performance ratios are analyzed. These are the first approximation algorithms for CSC problems in general graphs with guaranteed performance ratios.

TCS Journal 2009 Journal Article

Construction of strongly connected dominating sets in asymmetric multihop wireless networks

• Deying Li
• Hongwei Du
• Peng-Jun Wan
• Xiaofeng Gao
• Zhao Zhang
• Weili Wu

Consider an asymmetric wireless network represented by a digraph G = ( V, E ). A subset of vertices U is called a strongly connected dominating set (SCDS) if the subgraph induced by U is strongly connected and every vertex not in U has both an in-neighbor in U and an out-neighbor in U. SCDS plays an important role of the virtual backbone in asymmetric wireless networks. Motivated by the construction of a small virtual backbone, we study the problem Minimum SCDS, which seeks a smallest SCDS of a digraph. For any constant 0 < ρ < 1, there is no polynomial-time ρ ln n -approximation for Minimum SCDS unless N P ⊆ D T I M E ( n o ( ln n ) ), where n is the number of nodes. However, none of the polynomial-time heuristics for Minimum SCDS proposed in the literature are logarithmic approximations. In this paper, we present a polynomial-time ( 3 H ( n − 1 ) − 1 ) -approximation algorithm for Minimum SCDS, where H is the harmonic function. The approximation ratio of this algorithm is thus within a factor of 3 from the best possible approximation ratio achievable by any polynomial-time algorithm.

TCS Journal 2009 Journal Article

PTAS for connected vertex cover in unit disk graphs

• Zhao Zhang
• Xiaofeng Gao
• Weili Wu

This paper gives the first polynomial time approximation scheme for the connected vertex cover problem in unit disk graphs.

TCS Journal 2008 Journal Article

Lower bounds and new constructions on secure group communication schemes

• Scott C.-H. Huang
• Frances Yao
• Minming Li
• Weili Wu

This paper presents both the theoretical and practical aspects of secure group communication schemes. We pointed out that multiple revocation is a fundamentally time-consuming task in secure group communication, by establishing lower bounds for broadcast encryption and group key distribution schemes. We showed that they are O ( n ) for BE and O ( n / m ) for GKD respectively, where m is storage requirement and n is the number of users. Thus, they are clearly far more costly than the ideal log bound. In practice, we designed a new broadcast encryption scheme RBE that actually achieves these lower bounds. RBE is shown to outperform most efficient BE schemes in mass revocation. We discuss the influence of join as well as the feasibility of adding it in BE schemes by means of performing full updating or overprovisioning.

TCS Journal 2008 Journal Article

On approximate optimal dual power assignment for biconnectivity and edge-biconnectivity

• Chen Wang
• Myung-Ah Park
• James Willson
• Yongxi Cheng
• Andras Farago
• Weili Wu

Topology control is one of the major approaches to achieve energy efficiency as well as fault tolerance in wireless networks. In this paper, we study the dual power assignment problem for 2-edge connectivity and 2-vertex connectivity in the symmetric graphical model. The problem has arisen from the following practical origin. In a wireless ad hoc network where each node can switch its transmission power between high-level and low-level, how can we establish a fault-tolerant connected network topology in the most energy-efficient way? Specifically, the objective is to minimize the number of nodes assigned with high power and yet achieve 2-edge connectivity or 2-vertex connectivity. Note that to achieve a minimum number of high-power nodes is harder than an optimization problem in the same model whose objective is to minimize the total power cost. We first address these two optimization problems (2-edge connectivity and 2-vertex connectivity version) under the general graph model. Due to the NP-hardness, we propose an approximation algorithm, called prioritized edge selection algorithm, which achieves a 4-ratio approximation for 2-edge connectivity. After that, we modify the algorithm to solve the problem for 2-vertex connectivity and also achieve the same approximation ratio. We also show that the 4-ratio is tight for our algorithms in both cases.

TCS Journal 2008 Journal Article

On the complexity of non-unique probe selection

• Yongxi Cheng
• Ker-I Ko
• Weili Wu

We investigate the computational complexity of some basic problems regarding non-unique probe selection using separable matrices. In particular, we prove that the minimal d ̄ -separable matrix problem is DP -complete, and the d ̄ -separable submatrix with reserved rows problem, which is a generalization of the decision version of the minimum d ̄ -separable submatrix problem, is Σ 2 P -complete.

TCS Journal 2007 Journal Article

Non-unique probe selection and group testing

• Feng Wang
• Hongwei David Du
• Xiaohua Jia
• Ping Deng
• Weili Wu
• David MacCallum

A minimization problem that has arisen from the study of non-unique probe selection with group testing technique is as follows: Given a binary matrix, find a d -disjunct submatrix with the minimum number of rows and the same number of columns. We show that when every probe hybridizes to at most two viruses, i. e. , every row contains at most two 1s, this minimization is still MAX SNP-complete, but has a polynomial-time approximation with performance ratio 1 + 2 / ( d + 1 ). This approximation is constructed based on an interesting result that the above minimization is polynomial-time solvable when every probe hybridizes to exactly two viruses.

TCS Journal 2006 Journal Article

Minimum connected dominating sets and maximal independent sets in unit disk graphs

• Weili Wu
• Hongwei Du
• Xiaohua Jia
• Yingshu Li
• Scott C.-H. Huang

In ad hoc wireless networks, a connected dominating set can be used as a virtual backbone to improve the performance. Many constructions for approximating the minimum connected dominating set are based on the construction of a maximal independent set. The relation between the size mis ( G ) of a maximum independent set and the size cds ( G ) of a minimum connected dominating set in the same graph G plays an important role in establishing the performance ratio of those approximation algorithms. Previously, it is known that mis ( G ) ⩽ 4 · cds ( G ) + 1 for all unit disk graphs G. In this paper, we improve it by showing mis ( G ) ⩽ 3. 8 · cds ( G ) + 1. 2.

TCS Journal 2004 Journal Article

A greedy approximation for minimum connected dominating sets

• Lu Ruan
• Hongwei Du
• Xiaohua Jia
• Weili Wu
• Yingshu Li
• Ker-I Ko

Given a graph, a connected dominating set is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum connected dominating set is such a vertex subset with minimum cardinality. In this paper, we present a new one-step greedy approximation with performance ratio ln δ + 2 where δ is the maximum degree in the input graph. The interesting aspect is that the greedy potential function of this algorithm is not supmodular while all previously known one-step greedy algorithms with similar performance have supmodular potential functions.

TCS Journal 2003 Journal Article

Super link-connectivity of iterated line digraphs

• Xiaoyan Cheng
• Xiufeng Du
• Manki Min
• Hung Q. Ngo
• Lu Ruan
• Jianhua Sun
• Weili Wu

Many interconnection networks can be constructed with line digraph iterations. A digraph has super link-connectivity d if it has link-connectivity d and every link-cut of cardinality d consists of either all out-links coming from a node, or all in-links ending at a node, excluding loop. In this paper, we show that the link-digraph iteration preserves super link-connectivity.

TCS Journal 2001 Journal Article

Optimal placement of data replicas in distributed database with majority voting protocol

• Shashi Shekhar
• Weili Wu

In a distributed database system, data replicas are placed at different locations of a network to achieve the high data availability in presence of link failure. Optimal placements of data replicas have been studied extensively in the literature for various protocol. In this paper, we present a sufficient and necessary condition for optimality of a placement of odd number of data replicas in a ring network with majority voting protocol. As a corollary, we give a proof of a recent conjecture of Hu et al. (manuscript, 1999). Moreover, we also give a simple algorithm to find optimal placements in tree network with majority voting protocol.

TCS Journal 1998 Journal Article

Approximations for subset interconnection designs

• Xiufeng Du
• Weili Wu
• Dean F. Kelley

Given a complete weighted graph on vertex set X and subsets X 1…, X m of X, we consider the problem of finding a minimum total weight subgraph G such that for every i = 1, …, m, G contains a spanning tree for X i. The NP-hardness of this problem was established in 1985 under Ronald V. Book's supervision. In this note, we present some results about its polynomial-time approximation.