Author name cluster

Yongcai Wang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers

2 author rows

AAAI Conference 2026 Conference Paper

Mem4D: Decoupling Static and Dynamic Memory for Dynamic Scene Reconstruction

Xudong Cai
Shuo Wang
Peng Wang
Yongcai Wang
Zhaoxin Fan
Wanting Li
Tianbao Zhang
Jianrong Tao

Reconstructing dense geometry for dynamic scenes from a monocular video is a critical yet challenging task. Recent memory-based methods enable efficient online reconstruction, but they fundamentally suffer from a Memory Demand Dilemma: The memory representation faces an inherent conflict between the long-term stability required for static structures and the rapid, high-fidelity detail retention needed for dynamic motion. This conflict forces existing methods into a compromise, leading to either geometric drift in static structures or blurred, inaccurate reconstructions of dynamic objects. To address this dilemma, we propose Mem4D, a novel framework that decouples the modeling of static geometry and dynamic motion. Guided by this insight, we design a dual-memory architecture: 1) The Transient Dynamics Memory (TDM) focuses on capturing high-frequency motion details from recent frames, enabling accurate and fine-grained modeling of dynamic content; 2) The Persistent Structure Memory (PSM) compresses and preserves long-term spatial information, ensuring global consistency and drift-free reconstruction for static elements. By alternating queries to these specialized memories, Mem4D simultaneously maintains static geometry with global consistency and reconstructs dynamic elements with high fidelity. Experiments on challenging benchmarks demonstrate that our method achieves state-of-the-art or competitive performance while maintaining high efficiency.

PDF Details DOI

AAAI Conference 2026 Conference Paper

MonoDream: Monocular Vision-Language Navigation with Panoramic Dreaming

Shuo Wang
Yongcai Wang
Zhaoxin Fan
Yucheng Wang
Maiyue Chen
Kaihui Wang
Zhizhong Su
Wanting Li

Vision-Language Navigation (VLN) tasks often leverage panoramic RGB and depth inputs to provide rich spatial cues for action planning, but these sensors can be costly or less accessible in real-world deployments. Recent approaches based on Vision-Language Action (VLA) models achieve strong results with monocular input, yet they still lag behind methods using panoramic RGB-D information. We present MonoDream, a lightweight VLA framework that enables monocular agents to learn a Unified Navigation Representation (UNR). This shared feature representation jointly aligns navigation-relevant visual semantics (e.g., global layout, depth, and future cues) and language-grounded action intent, enabling more reliable action prediction. MonoDream further introduces Latent Panoramic Dreaming (LPD) tasks to supervise the UNR, which train the model to predict latent features of panoramic RGB and depth observations at both current and future steps based on only monocular input. Experiments on multiple VLN benchmarks show that MonoDream consistently improves monocular navigation performance and significantly narrows the gap with panoramic-based agents.

PDF Details DOI

NeurIPS Conference 2025 Conference Paper

Aux-Think: Exploring Reasoning Strategies for Data-Efficient Vision-Language Navigation

Shuo Wang
Yongcai Wang
Wanting Li
Xudong Cai
Yucheng Wang
Maiyue Chen
Zhizhong Su
Deying Li

Vision-Language Navigation is a critical task for developing embodied agents that can follow natural language instructions to navigate in complex real-world environments. Recent advances by finetuning large pretrained models have significantly improved generalization and instruction grounding compared to traditional approaches. However, the role of reasoning strategies in navigation—an action-centric, long-horizon task—remains underexplored, despite Chain-of-Thought reasoning's demonstrated success in static tasks like question answering and visual reasoning. To address this gap, we conduct the first systematic evaluation of reasoning strategies for VLN, including No-Think (direct action prediction), Pre-Think (reason before action), and Post-Think (reason after action). Surprisingly, our findings reveal the Inference-time Reasoning Collaps issue, where inference-time reasoning degrades navigation accuracy, highlighting the challenges of integrating reasoning into VLN. Based on this insight, we propose Aux-Think, a framework that trains models to internalize structured reasoning patterns through CoT supervision during training, while preserving No-Think inference for efficient action prediction. To support this framework, we release R2R-CoT-320k, a large-scale Chain-of-Thought annotated dataset. Empirically, Aux-Think significantly reduces training effort without compromising performance.

PDF Details

ICRA Conference 2025 Conference Paper

Is Discretization Fusion All You Need for Collaborative Perception?

Kang Yang
Tianci Bu
Lantao Li
Chunxu Li
Yongcai Wang
Deying Li 0001

Collaborative perception in multi-agent system enhances overall perceptual capabilities by facilitating the exchange of complementary information among agents. Current mainstream collaborative perception methods rely on discretized feature maps to conduct fusion, which however, lacks flexibility in extracting and transmitting the informative features and can hardly focus on the informative features during fusion. To address these problems, this paper proposes a novel Anchor-Centric paradigm for Collaborative Object detection (ACCO). It avoids grid precision issues and allows more flexible and efficient anchor-centric communication and fusion. ACCO is composed by three main components: (1) Anchor featuring block (AFB) that targets to generate anchor proposals and projects prepared anchor queries to image features. (2) Anchor confidence generator (ACG) is designed to minimize communication by selecting only the features in the confident anchors to transmit. (3) A local-global fusion module, in which local fusion is anchor alignment-based fusion (LAAF) and global fusion is conducted by spatial-aware cross-attention (SACA). LAAF and SACA run in multilayers, so agents conduct anchor-centric fusion iteratively to adjust the anchor proposals. Comprehensive experiments are conducted to evaluate ACCO on OPV2V and Dair-V2x datasets, which demonstrate ACCO's superiority in reducing the communication volume, and in improving the perception range and detection performances. Code can be found at: https://github.com/sidiangongyuan/ACCO.

Details

TCS Journal 2025 Journal Article

Maximum core spanning tree maintenance for large dynamic graphs

Xiaowei Lv
Yongcai Wang
Deying Li

With the increase in network scale and online applications, the maintenance problem of cohesive structures in large graphs has attracted great attention. The Maximum Core Spanning Tree (MCST) is a representative cohesive structure generated based on k-core, which is the maximum edge weight spanning tree indicating the “staired coreness hierarchy” in each connected component. The edge weight here is defined as w u v = min ⁡ { c o r e ( u ), c o r e ( v ) }, and c o r e ( x ) is the corness of vertex x. Unlike the maintenance problem of Maximum Spanning Tree (MST) which has known efficient algorithms, MCST maintenance raises special challenges, which is mainly due to the cascaded vertex coreness changes after single-edge insertion or deletion. In this paper, we show a series properties of MCST and MCST maintenance problems and propose an OrderPassed method and a LoopFree method to maintain the MCST efficiently. In particular, the time complexity for MCST maintenance for edge insertion and deletion is bounded by O ( | E ⁎ | + | V | ) and O ( | E ⁎ | + ∑ i = 1 K | O i | ) respectively, where E ⁎ is the edge set whose edge weight changes after insertion/deletion and | O i | denotes the number of edges whose edge weight is i. Through extensive evaluations, we show the proposed MCST maintenance algorithms have good efficiency, scalability and stability on real-world datasets.

Details DOI

TCS Journal 2025 Journal Article

Sequential decision based learning method for influence maximization

Zizhen Zhang
Deying Li
Yongcai Wang
Wenping Chen
Yuqing Zhu

Influence maximization (IM) involves choosing an initial group of users within a social network to optimize the expected spread of influence across other users. Recently, learning-based combinatorial optimization (CO) methods have been developed to learn generalized policies for specific CO problems on graphs. However, current learning-based algorithms struggle with diverse diffusion patterns, which restricts their generalization ability. In this paper, we apply reverse influence sampling to simplify the IM problem, reducing it to a stochastic maximum coverage problem using hyperedges. We then model this as a Markov decision process and propose two sequential decision-based learning methods. These methods leverage the symmetry of solutions with respect to sequence order and utilize the submodular reward function. By jointly training on multiple graphs, our approach learns a transferable seed selection policy that generalizes effectively to previously unseen test graphs. Extensive experiments demonstrate that our method outperforms recent learning-based approaches as well as traditional methods on both real and synthetic datasets for the IM problem.

Details DOI

NeurIPS Conference 2025 Conference Paper

STAR: Spatial-Temporal Tracklet Matching for Multi-Object Tracking

Xuewei Bai
Yongcai Wang
Deying Li
Haodi Ping
LI Chunxu

Existing tracking-by-detection Multi-Object Tracking methods mainly rely on associating objects with tracklets using motion and appearance features. However, variations in viewpoint and occlusions can result in discrepancies between the features of current objects and those of historical tracklets. To tackle these challenges, this paper proposes a novel Spatial-Temporal Tracklet Graph Matching paradigm (STAR). The core idea of STAR is to achieve long-term, reliable object association through the association of ``tracklet clips (TCs)". TCs are segments of confidently associated multi-object trajectories, which are linked through graph matching. Specifically, STAR initializes TCs using a Confident Initial Tracklet Generator (CITG) and constructs a TC graph via Tracklet Clip Graph Construction (TCGC). In TCGC, each object in a TC is treated as a vertex, with the appearance and local topology features encoded on the vertex. The vertices and edges of the TC graph are then updated through message propagation to capture higher-order features. Finally, a Tracklet Clip Graph Matching (TCGM) method is proposed to efficiently and accurately associate the TCs through graph matching. STAR is model-agnostic, allowing for seamless integration with existing methods to enhance their performance. Extensive experiments on diverse datasets, including MOTChallenge, DanceTrack, and VisDrone2021-MOT, demonstrate the robustness and versatility of STAR, significantly improving tracking performance under challenging conditions.

PDF Details

ICRA Conference 2024 Conference Paper

DroneMOT: Drone-based Multi-Object Tracking Considering Detection Difficulties and Simultaneous Moving of Drones and Objects

Peng Wang 0106
Yongcai Wang
Deying Li 0001

Multi-object tracking (MOT) on static platforms, such as by surveillance cameras, has achieved significant progress, with various paradigms providing attractive performances. However, the effectiveness of traditional MOT methods is significantly reduced when it comes to dynamic platforms like drones. This decrease is attributed to the distinctive challenges in the MOT-on-drone scenario: (1) objects are generally small in the image plane, blurred, and frequently occluded, making them challenging to detect and recognize; (2) drones move and see objects from different angles, causing the unreliability of the predicted positions and feature embeddings of the objects. This paper proposes DroneMOT, which firstly proposes a Dual-domain Integrated Attention (DIA) module that considers the fast movements of drones to enhance the drone-based object detection and feature embedding for small-sized, blurred, and occluded objects. Then, an innovative Motion-Driven Association (MDA) scheme is introduced, considering the concurrent movements of both the drone and the objects. Within MDA, an Adaptive Feature Synchronization (AFS) technique is presented to update the object features seen from different angles. Additionally, a Dual Motion-based Prediction (DMP) method is employed to forecast the object positions. Finally, both the refined feature embeddings and the predicted positions are integrated to enhance the object association. Comprehensive evaluations on VisDrone2019-MOT and UAVDT datasets show that DroneMOT provides substantial performance improvements over the state-of-the-art in the domain of MOT on drones. The code will be available at https://github.com/PenK1nG/DroneMOT.

Details

ICRA Conference 2024 Conference Paper

Parameter-efficient Prompt Learning for 3D Point Cloud Understanding

Hongyu Sun 0006
Yongcai Wang
Wang Chen
Haoran Deng
Deying Li 0001

This paper presents a parameter-efficient prompt tuning method, named PPT, to adapt a large multi-modal model for 3D point cloud understanding. Existing strategies are quite expensive in computation and storage, and depend on timeconsuming prompt engineering. We address the problems from three aspects. Firstly, a PromptLearner module is devised to replace hand-crafted prompts with learnable contexts to automate the prompt tuning process. Then, we lock the pre-trained backbone instead of adopting the full fine-tuning paradigm to substantially improve the parameter efficiency. Finally, a lightweight PointAdapter module is arranged near target tasks to enhance prompt tuning for 3D point cloud understanding. Comprehensive experiments are conducted to demonstrate the superior parameter and data efficiency of the proposed method. Meanwhile, we obtain new records on 4 public datasets and multiple 3D tasks, i. e. , point cloud recognition, few-shot learning, and part segmentation. The implementation is available at https://github.com/auniquesun/PPT.

Details

NeurIPS Conference 2024 Conference Paper

Point-PRC: A Prompt Learning Based Regulation Framework for Generalizable Point Cloud Analysis

Hongyu Sun
Qiuhong Ke
Yongcai Wang
Wang Chen
Kang Yang
Deying Li
Jianfei Cai

This paper investigates the 3D domain generalization (3DDG) ability of large 3D models based on prevalent prompt learning. Recent works demonstrate the performances of 3D point cloud recognition can be boosted remarkably by parameter-efficient prompt tuning. However, we observe that the improvement on downstream tasks comes at the expense of a severe drop in 3D domain generalization. To resolve this challenge, we present a comprehensive regulation framework that allows the learnable prompts to actively interact with the well-learned general knowledge in large 3D models to maintain good generalization. Specifically, the proposed framework imposes multiple explicit constraints on the prompt learning trajectory by maximizing the mutual agreement between task-specific predictions and task-agnostic knowledge. We design the regulation framework as a plug-and-play module to embed into existing representative large 3D models. Surprisingly, our method not only realizes consistently increasing generalization ability but also enhances task-specific 3D recognition performances across various 3DDG benchmarks by a clear margin. Considering the lack of study and evaluation on 3DDG, we also create three new benchmarks, namely base-to-new, cross-dataset and few-shot generalization benchmarks, to enrich the field and inspire future research. Code and benchmarks are available at \url{https: //github. com/auniquesun/Point-PRC}.

PDF Details DOI

ICRA Conference 2024 Conference Paper

VOLoc: Visual Place Recognition by Querying Compressed Lidar Map

Xudong Cai
Yongcai Wang
Zhe Huang
Yu Shao
Deying Li 0001

The availability of city-scale Lidar maps enables the potential of city-scale place recognition using mobile cameras. However, the city-scale Lidar maps generally need to be compressed for storage efficiency, which increases the difficulty of direct visual place recognition in compressed Lidar maps. This paper proposes VOLoc, an accurate and efficient visual place recognition method that exploits geometric similarity to directly query the compressed Lidar map via the real-time captured image sequence. In the offline phase, VOLoc compresses the Lidar maps using a Geometry-Preserving Compressor (GPC), in which the compression is reversible, a crucial requirement for the downstream 6DoF pose estimation. In the online phase, VOLoc proposes an online Geometric Recovery Module (GRM), which is composed of online Visual Odometry (VO) and a point cloud optimization module, such that the local scene structure around the camera is online recovered to build the Querying Point Cloud (QPC). Then the QPC is compressed by the same GPC, and is aggregated into a global descriptor by an attentionbased aggregation module, to query the compressed Lidar map in the vector space. A transfer learning mechanism is also proposed to improve the accuracy and the generality of the aggregation network. Extensive evaluations show that VOLoc provides localization accuracy even better than the Lidar-toLidar place recognition, setting up a new record for utilizing the compressed Lidar map by low-end mobile cameras. The code are publicly available at https://github.com/Master-cai/VOLoc.

Details

TCS Journal 2023 Journal Article

A fault diagnosis method to defend scapegoating attack in network tomography

Xiaojia Xu
Yongcai Wang
Yu Zhang
Deying Li

The scapegoating attack can cause persistent and inconspicuous performance degradation in network tomography. Defense of scapegoating attack is therefore a critical problem. Theoretically, the ideal defending scheme is to add monitoring paths to make all the links in the network be identifiable. This requires very high monitoring cost, which is unaffordable. To overcome this problem, this paper proposes a diagnosis-based defending scheme for scapegoating attack, which diagnoses scapegoating attack when problematic links are detected by network tomography. The latent fact is that a scapegoating attack can be launched only when the link set manipulated by the attacker cuts the probing paths going through the scapegoat links and is not traversed by any monitoring path. This cut set is called unobserved cut set (UCS). To defense, we propose to find the UCS and add the minimum number of probing paths to traverse the UCS, so that the condition of scapegoating attack is broken and the attacking links can be detected if any scapegoating attack exists. A minimum set cover model is proposed to select the least number of defense links to cover the UCS, and a polynomial time algorithm is proposed to generate the least number of probing paths to go through the selected defense links. Evaluations on various network dataset show the effectiveness of the proposed attack and defense strategies.

Details DOI

TCS Journal 2023 Journal Article

A robust map matching method by considering memorized multiple matching candidates

Wanting Li
Yongcai Wang
Deying Li
Xiaojia Xu

Map matching is to track the positions of vehicles on the road network based on the positions provided by GPS (Global Positioning System) devices. Balancing localization accuracy and computation efficiency is a key problem in map matching. Existing methods mainly use Hidden Markov Model (HMM) or historical transportation data to learn the transitional probabilities among road segments. Although the roads to explore can be remarkably reduced by the Markov assumption, miss-of-match and matching breaks may occur if the GPS data is highly noisy, and the transitional model needs to be learned offline. To address these problems, this paper presents Multiple Candidate Matching (MCM) to improve the robustness of map matching. MCM doesn't need to pre-train the transitional model nor the historical transportation information. MCM memorizes multiple historical matching candidates in the map matching process. It votes among historical matchings and current matchings, but generates limited number of road candidates in real-time to restrict the computation complexity. MCM for both online map matching and offline map matching are presented and their properties are analyzed theoretically and experimentally. Numerical experiments in large-scale data sets show that MCM is very promising in terms of accuracy, computational efficiency, and robustness. The matching break and miss-of-match problems can be resolved effectively when compared with the state-of-the-art map matching methods. Codes are outsourced at https: //github. com/lindalee-inlab/MCM.

Details DOI

ICRA Conference 2023 Conference Paper

ViPFormer: Efficient Vision-and-Pointcloud Transformer for Unsupervised Pointcloud Understanding

Hongyu Sun 0006
Yongcai Wang
Xudong Cai
Xuewei Bai
Deying Li 0001

Recently, a growing number of work design unsupervised paradigms for point cloud processing to alleviate the limitation of expensive manual annotation and poor transferability of supervised methods. Among them, CrossPoint follows the contrastive learning framework and exploits image and point cloud data for unsupervised point cloud understanding. Although the promising performance is presented, the unbalanced architecture makes it unnecessarily complex and inefficient. For example, the image branch in CrossPoint is ~8. 3x heavier than the point cloud branch leading to higher complexity and latency. To address this problem, in this paper, we propose a lightweight Vision-and-Pointcloud Transformer (ViPFormer) to unify image and point cloud processing in a single architecture. ViPFormer learns in an unsupervised manner by optimizing intra-modal and cross-modal contrastive objectives. Then the pretrained model is transferred to various downstream tasks, including 3D shape classification and semantic segmentation. Experiments on different datasets show ViPFormer surpasses previous state-of-the-art unsupervised methods with higher accuracy, lower model complexity and runtime latency. Finally, the effectiveness of each component in ViPFormer is validated by extensive ablation studies. The implementation of the proposed method is available at https://github.com/auniquesun/ViPFormer.

Details

TCS Journal 2022 Journal Article

Self-stabilizing spanner topology control solutions in wireless ad hoc networks

Xiujuan Zhang
Yongcai Wang
Deying Li
Wenping Chen
Xingjian Ding

Large-scale, self-organizing wireless ad hoc network deployments are being driven by recent developments of the Internet of Things (IoT) to collect information from a vast area or harsh environment efficiently. How to ensure fast routing in sparse topology and after node failure how to ensure that the network keeps topology properties are challenging problems. In this paper, we propose a Self-stabilizing dIrected t-Spanner for Autonomous nodes problem (SISA) and give intuitive solutions in both 2D and 3D space. In the topology construction phase, sparse directed t-spanner topologies, without substantially degrading the path connecting any pair of nodes in the original network, are constructed with a minimum number of messages. In the topology maintenance phase, the self-stabilizing algorithms run in the background to update locally for keeping t-spanner property when some nodes fail. In particular, our solutions have not any central daemon and are completely distributed. Our experimental results demonstrate the effectiveness and efficiency of our proposed solutions.

Details DOI

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.

Details DOI

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.

Details DOI

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.

Details DOI

TCS Journal 2020 Journal Article

Community based acceptance probability maximization for target users on social networks: Algorithms and analysis

Ruidong Yan
Yuqing Zhu
Deying Li
Yongcai Wang

Different from previous social influence problems such as Influence Maximization (IM), we in this paper first propose the Acceptance Probability Maximization (APM) problem, i. e. , we select a seed set S with a budget b such that the acceptance probability of the target user set T is maximized. Then we employ the classical Independent Cascade (IC) model as the information diffusion model. Based on the IC model, we prove that the APM problem is NP-hard and the objective function is monotone non-decreasing and submodular. Considering community components of the social network, we convert the APM problem to the Maximum Weight Hitting Set (MWHS) problem. Next we develop a pipage rounding algorithm whose approximation ratio is ( 1 − 1 / e ). Furthermore, we also propose a basic greedy algorithm and a heuristic algorithm as comparison methods. Finally, we conduct extensive simulations on synthetic and real-life social networks to evaluate the efficacy and efficiency of our algorithms. Empirical evaluation results validate the superiority of proposed algorithms in both effectiveness and efficiency compared with a few baseline comparison methods.

Details DOI

TCS Journal 2020 Journal Article

Efficient scheduling of a mobile charger in large-scale sensor networks

Xingjian Ding
Wenping Chen
Yongcai Wang
Deying Li
Yi Hong

Schedule a mobile charger to replenish energy to sensor nodes for the wireless sensor networks has attracted great attention recently, due to its efficiency and flexibility. Some existing works study the mobile charger scheduling problem by considering that only the depot can recharge or replace the battery for the mobile charger. However, for large-scale wireless sensor networks, the mobile charger is energy inefficient or even may run out of energy during the travel for charging. In this paper, we consider the scenario that there are some service stations in the network area which can be used to replace the battery for the mobile charger, and we study the problem of minimizing the number of used batteries for a mobile charger to charge a wireless sensor network (MBA). We first consider a special case of the MBA problem, in which the depot is the only service station, and we present an approximation algorithm to address it. Then we propose an approximation algorithm for the MBA problem with the assumption that the distance of any two service stations is limited. And finally, we consider the general MBA problem and propose an approximation algorithm. We validate the performance of our algorithms by extensive simulations, and the results show that our proposed algorithms are promising.

Details DOI

TCS Journal 2020 Journal Article

Target users' activation probability maximization with different seed set constraints in social networks

Ruidong Yan
Hongwei Du
Yi Li
Wenping Chen
Yongcai Wang
Yuqing Zhu
Deying Li

Influence Maximization (IM) over the online social networks have been widely explored in recent years, which selects a seed set from nodes in the network using a limited budget such that the expected number of nodes influenced by the seed set is maximized. However, how to activate a considered set of targeting users T, e. g. , selling a product to a specific target group, is a more practical problem. To address this problem, we respectively propose the Target Users' Activation Probability Maximization with Constraint (TUAPM-WC) problem and the Target Users' Activation Probability Maximization without Constraint (TUAPM-WOC) problem, i. e. , to select a seed set S with/without size constraints such that the activation probabilities of the target users in T are maximized. Considering that the influence will decay during information propagation, we propose a novel and practical Influence Decay Model (IDM) as the information diffusion model. Based on the IDM, we show that the TUAPM-WC and the TUAPM-WOC problems are NP-hard. We also prove that the objective functions of TUAPM-WC and TUAPM-WOC problems are monotone non-decreasing and submodular. On one hand, we employ a Double Greedy Algorithm (DGA) to guarantee a (1/3)-approximation ratio for TUAPM-WOC problem when | S | is unconstrained. On the other hand, we propose a series of algorithms to solve the TUAPM-WC when | S | ≤ b, where b is a positive integer. More specifically, we provide a ( 1 − 1 / e )-approximation Basic Greedy Algorithm (BGA). Furthermore, a speed-up Scalable Algorithm (SA) is proposed for online large social networks. Finally, we run our algorithms by simulations on synthetic and real-life social networks to evaluate the effectiveness and efficiency of the proposed algorithms. Experimental results validate our algorithms' superior to the comparison algorithms.

Details DOI

AAAI Conference 2017 Conference Paper

Efficient Online Model Adaptation by Incremental Simplex Tableau

Zhixian Lei
Xuehan Ye
Yongcai Wang
Deying Li
Jia Xu

Online multi-kernel learning is promising in the era of mobile computing, in which a combined classiﬁer with multiple kernels are ofﬂine trained, and online adapts to personalized features for serving the end user precisely and smartly. The online adaptation is mainly carried out at the end-devices, which requires the adaptation algorithms to be light, efﬁcient and accurate. Previous results focused mainly on efﬁciency. This paper proposes an novel online model adaptation framework for not only efﬁciency but also optimal online adaptation. At ﬁrst, an online optimal incremental simplex tableau (IST) algorithm is proposed, which approaches the model adaption by linear programming and produces the optimized model update in each step when a personalized training data is collected. But keeping online optimal in each step is expensive and may cause over-ﬁtting especially when the online data is noisy. A Fast-IST approach is therefore proposed, which measures the deviation between the training data and the current model. It schedules updating only when enough deviation is detected. The efﬁciency of each update is further enhanced by running IST only limited iterations, which bounds the computation complexity. Theoretical analysis and extensive evaluations show that Fast-IST saves computation cost greatly, while achieving speedy and accurate model adaptation. It provides better model adaptation speed and accuracy while using even lower computing cost than the state-of-theart.

PDF Details

IJCAI Conference 2015 Conference Paper

On the Balance of Meter Deployment Cost and NILM Accuracy

Xiaohong Hao
Bangsheng Tang
Yongcai Wang

Non-Intrusive Load Monitoring (NILM) uses one smart meter at the power feed to disaggregate the states of a set of appliances. Multiple NILM meters are deployed to achieve high monitoring accuracy in large-scale power systems. Our work studies the tradeoff between monitoring accuracy and meter deployment, in a quantitative and extensible way. In particular, we introduce a clearness function as an abstract indicator of expected monitoring accuracy given any NILM method, and then showcase two concrete constructions. With the notation of a clearness function, we propose solutions to the smart meter deployment problem (SMDP), that is, the problem of finding a deployment scheme with minimum number of meters while attaining a required monitoring accuracy. Theoretically, SMDP is shown NP-hard and a polynomial-time approximation scheme (PTAS) is proposed in this paper. For evaluation, we show that our proposed scheme is efficient and effective in terms of approximation ratio and running time. On real and simulated datasets, our proposed framework achieves a higher monitoring accuracy at a much lower cost, outperforming common baseline algorithms.

PDF Details