Arrow Research search

Author name cluster

Deying Li

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.

30 papers
1 author row

Possible papers

30

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

YNIMG Journal 2025 Journal Article

Iterative prior-guided parcellation (iPGP) for capturing inter-subject and inter-nuclei variability in thalamic mapping

  • Chaohong Gao
  • Xia Wu
  • Liang Ma
  • Deying Li
  • Yufan Wang
  • Changlu Guo
  • Wen Li
  • Haiyan Wang

The thalamus, a critical relay station in the brain, consists of multiple nuclei that play essential roles in various brain circuits. Identifying these nuclei is crucial for understanding how thalamic structures influence cognitive functions. However, genetic and environmental factors introduce substantial variability in thalamic parcellation patterns, posing both challenges and opportunities for individualized mapping of thalamic function. This study proposes an iterative prior-guided parcellation (iPGP) framework to construct individualized thalamic parcellations. The iPGP method utilizes the Morel histological atlas as prior guidance, incorporates spatially constrained local diffusion characteristics as features, and employs an iterative framework to optimize an individual-specific parcellation model. As a result, iPGP automatically adapts to individual thalamic contrast variations, producing personalized and anatomically consistent parcellations. Through test-retest assessments, iPGP demonstrated a high degree of intra-subject reproducibility. By evaluating inter-subject and inter-nuclei variability, iPGP exhibited strong adaptability across different age groups while capturing subject-specific and region-specific variability. Furthermore, thalamic parcellations generated by iPGP showed significant associations with adolescent age and adult behavioral-cognitive scores. Our findings suggest that iPGP effectively captures inter-subject and inter-nuclei variability in thalamic parcellation, highlighting its potential for advancing thalamic mapping in exploring brain function.

Details DOI

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

YNIMG Journal 2024 Journal Article

Neuro-immune communication at the core of craving-associated brain structural network reconfiguration in methamphetamine users

  • Yanyao Du
  • Jiaqi Zhang
  • Dan Cao
  • Wenhan Yang
  • Jin Li
  • Deying Li
  • Ming Song
  • Zhengyi Yang

Methamphetamine (MA) use disorder is a chronic neurotoxic brain disease characterized by a high risk of relapse driven by intense cravings. However, the neurobiological signatures of cravings remain unclear, limiting the effectiveness of various treatment methods. Diffusion MRI (dMRI) scans from 62 MA users and 57 healthy controls (HC) were used in this study. The MA users were longitudinally followed up during their period of long-term abstinence (duration of long-term abstinence: 347. 52±99. 25 days). We systematically quantified the control ability of each brain region for craving-associated state transitions using network control theory from a causal perspective. Craving-associated structural alterations (CSA) were investigated through multivariate group comparisons and biological relevance analysis. The neural mechanisms underlying CSA were elucidated using transcriptomic and neurochemical analyses. We observed that long-term abstinence-induced structural alterations significantly influenced the state transition energy involved in the cognitive control response to external information, which correlated with changes in craving scores (r ∼ 0. 35, P <0. 01). Our causal network analysis further supported the crucial role of the prefrontal cortex (PFC) in craving mechanisms. Notably, while the PFC is central to the craving, the CSAs were distributed widely across multiple brain regions (PFDR <0. 05), with strong alterations in somatomotor regions (PFDR <0. 05) and moderate alterations in high-level association networks (PFDR <0. 05). Additionally, transcriptomic, chemical compounds, cell-type analyses, and molecular imaging collectively highlight the influence of neuro-immune communication on human craving modulation. Our results offer an integrative, multi-scale perspective on unraveling the neural underpinnings of craving and suggest that neuro-immune signaling may be a promising target for future human addiction therapeutics.

Details DOI

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

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

TCS Journal 2023 Journal Article

Trajectory optimization of laser-charged UAV to minimize the average age of information for wireless rechargeable sensor network

  • Chuanwen Luo
  • Ning Liu
  • Yunan Hou
  • Yi Hong
  • Zhibo Chen
  • Deying Li

This paper considers the laser-charged Unmanned Aerial Vehicle (UAV) assisted Wireless Rechargeable Sensor Network (WRSN), where rechargeable sensors are deployed in surveillance environment to monitor information, a UAV is not only used as aerial wireless mobile collector for gathering data from sensors but also used as mobile charger to replenish energy for sensors, Laser Beam Directors (LBDs) are uniformly deployed in the monitoring environment to charge UAV by emitting laser beams. In such network, we study the average Age of Information Optimization (AoIO) problem whose objective is to minimize the average AoI of data collected from sensors such that all data of the network are transported to the base station and the remaining energy of any sensor exceeds a certain threshold. We prove that the AoIO problem is NP-hard. To solve the AoIO problem, we first study the Total Flight Time Minimizing of UAV (TFTM) problem, which aims at finding an optimal charging solution of UAV to minimize the flight time of UAV based on the order of sensors visited by UAV. Then we prove that the TFTM problem is also NP-hard. Afterwards, we propose a heuristic algorithm to solve the TFTM problem by optimizing flight path, data collection, energy power transfer and laser charging of UAV. Based on the solution for the TFTM problem, we propose an approximation algorithm to solve the AoIO problem. Finally, we conduct extensive simulation experiments to verify the effectiveness of the proposed algorithm.

Details DOI

TCS Journal 2022 Journal Article

Energy efficiency optimization for multiple chargers in Wireless Rechargeable Sensor Networks

  • Yi Hong
  • Chuanwen Luo
  • Deying Li
  • Zhibo Chen
  • Xiyun Wang
  • Xiao Li

To guarantee the continuous coverage of the rechargeable sensors, Wireless Rechargeable Sensor Networks (WRSNs) has emerged with the advantages of high charging efficiency and reliable charging timeliness. Charging planning is an important problem in theoretical research and practical applications, and it faces more difficulties and challenges for multiple mobile chargers. In this paper, we introduce a charging planning problem for multiple chargers, namely Charging Energy Efficiency Maximization problem for Multi-Chargers in WRSNs (CEEM-MC Problem), and prove its NP-hardness. The problem aims to maximize the charging energy efficiency of the charging process by assigning the charging amount and planning the charging path. To balance the charging consumption among multiple chargers, we propose two algorithms which are different on the charging path planning, Ring-Wandering Algorithm and Eight-Wandering Algorithm. To evaluate the performance on energy efficiency, we perform a series of simulations and the results verify the effectiveness of the proposed algorithms.

Details DOI

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

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.

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

Balanced-flow algorithm for path network planning in hierarchical spaces

  • Yi Hong
  • Jiandong Liu
  • Deying Li
  • Chuanwen Luo
  • Mengjie Chang

Path planning is an important and classical problem in theoretical research and practical applications. In the complex and hierarchical space scenarios, path planning faces more difficulties and challenges due to the structural particularity. Considering the directivity of paths in hierarchical spaces, it is more important to guarantee the fluency and efficiency of the paths in hierarchical spaces. In this paper, we introduce a path network planning problem from multi-source to multi-destination in hierarchical spaces, namely Balanced-Flow Path Network Planning (BF-PNP) problem, and prove its NP-completeness. To balance the flow rate among the layers in the space, we propose a batch scheduling algorithm with the objective of minimizing the scheduling time consumption. To evaluate the performance on efficiency and time complexity, we perform a series of simulations and the results indicate the advantages of the proposed algorithm.

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

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.

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 classifier with multiple kernels are offline 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, efficient and accurate. Previous results focused mainly on efficiency. This paper proposes an novel online model adaptation framework for not only efficiency but also optimal online adaptation. At first, 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-fitting 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 efficiency 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

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.

Details DOI

TCS Journal 2013 Journal Article

Approximation algorithms for minimum latency data aggregation in wireless sensor networks with directional antenna

  • Hui Liu
  • Zewen Liu
  • Deying Li
  • Xianling Lu
  • Hongwei Du

Real-time data aggregation is one of the most important issues in wireless sensor networks. Using directional antenna to transmit data can save energy and reduce interference. In this paper, we study the minimum latency data aggregation problem with the given two directional antenna models (the steering beam and the switch beam) under protocol interference model. We propose an approximation directional data aggregation algorithm to schedule data transmissions under two directional antenna models, respectively. At last, we evaluate the proposed schedule algorithms through simulations, and simulation results show that the proposed schedule’s latency is close to the depth of BFS tree, which is the lower bound of schedule latency, and the proposed schedules achieve extremely good performance.

Details DOI

TCS Journal 2013 Journal Article

Minimum energy multicast/broadcast routing with reception cost in wireless sensor networks

  • Deying Li
  • Zewen Liu
  • Yi Hong
  • Wenping Chen
  • Huan Ma

In this paper, we study the minimum energy multicast/broadcast problem with reception cost in wireless sensor networks. Suppose there are n sensors in the network. Each node v has l ( v ) transmission power levels to choose and its reception cost is B ( v ) if it receives a message. The problem of our concern is: given a multicast (broadcast) request, how to find a multicast (broadcast) tree such that the total energy cost of the multicast tree including transmitting cost and reception cost is minimized. There are two cases for reception cost: one is that for any node v, the reception cost of v only relies on v itself and is irrelevant with its transmitting node, the other is that the reception cost of v relies on not only itself but also its transmitting node. For the first case, we firstly propose a general approximation algorithm MEB-R-G for the broadcast problem. Moreover, for the multicast problem, we propose a general algorithm MEM-R-G and prove its approximation ratio, we also present a greedy algorithm. For the second case, we also propose a general approximation algorithm MEM-RT-G, and prove its approximation ratio.

Details DOI

TCS Journal 2012 Journal Article

Constrained surface-level gateway placement for underwater acoustic wireless sensor networks

  • Deying Li
  • Zheng Li
  • Wenkai Ma
  • Hong Chen
  • Wenping Chen

One approach to guarantee the performance of underwater acoustic sensor networks is to deploy multiple Surface-level Gateways (SGs) at the surface. This paper addresses the connected (or survivable) Constrained Surface-level Gateway Placement (C-SGP ) problem for 3-D underwater acoustic sensor networks. Given a set of underwater sensor nodes (USNs) which are floated at different depths to perform collaborative monitoring tasks over a given region, and a set of candidate locations where SGs may be placed, our objective is to place minimum number of SGs at a subset of candidate locations such that it is connected (or k -connected) from any USN to the base station. We first propose a general algorithm for the connected C-SGP problem and prove its approximation ratio. We also give a constant ratio approximation algorithm for the problem. Second, for the survivable C-SGP problem we also propose a general algorithm and prove its approximation ratio. Finally, we give a constant ratio approximation algorithm for the 2-connected C-SGP problem.

Details DOI

TCS Journal 2011 Journal Article

Fault-tolerant routing: k -inconnected many-to-one routing in wireless networks

  • Deying Li
  • Yuexuan Wang
  • Qinghua Zhu
  • Huiqiang Yang

This paper addresses the problem of fault-tolerant many-to-one routing in static wireless networks with asymmetric links, which is important in both theoretical and practical aspects. The problem is to find a minimum energy subgraph for a given subset and a destination node such that there are k node-disjoint paths from each node in the subset to the destination node in the subgraph. Firstly, we prove that the problem is NP-hard, and then propose two approximation algorithms: the minimum weight k node-disjoint paths based (MWkNDPB) algorithm and the minimum energy k node-disjoint paths based (MEkNDPB) algorithm. Extensive simulations have been conducted to show that proposed algorithms are efficient.

Details DOI

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.

Details DOI
v2026.09.13