Arrow Research search

Author name cluster

Xiaofeng Gao

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.

24 papers
1 author row

Possible papers

24

AAAI Conference 2026 Conference Paper

ProCAST: A Projection Framework for Coupled Aggregation Constrained Multivariate Time Series Forecasting

  • Jiaqi Xue
  • Hongji Dong
  • Yucen Gao
  • Xiaofeng Gao
  • Guihai Chen

Aggregated time series are widely used in business and economics, where top-level sequences (e.g., category sales) aggregated from underlying sequences (e.g., individual items) often exhibit clearer trends and are therefore typically the primary focus of forecasting tasks. However, treating top-level sequences as ordinary multivariate time series is inappropriate in the presence of coupled aggregation constraints. The core challenge arises in coupled aggregation structures, where a single underlying sequence contributes to multiple top-level sequences, as simple nonnegativity constraints of underlying sequences induce highly complex constraints among top-level sequences. Existing methods fail to achieve high accuracy while satisfying these constraints. To address this, we propose ProCAST, a projection-based framework that adjusts forecasts from any multivariate base model to satisfy coupled aggregation constraints. By introducing virtual underlying sequences and leveraging orthogonal and oblique projection, our method ensures that the top-level forecasts are feasible without explicitly deriving complex constraints. Theoretically, we prove that the proposed method guarantees improved accuracy under distance-based loss functions. Experiments on real-world datasets show that our method completely eliminates constraint violations while achieving higher accuracy than current state-of-the-art approaches.

TCS Journal 2025 Journal Article

Algorithms for Shortest Path Tour Problem

  • Yucen Gao
  • Zhuoran Li
  • Jingyu He
  • Jun Fang
  • Hui Gao
  • Xiaofeng Gao
  • Guihai Chen

Carpooling route planning becomes an important problem with the growth of low-carbon traffic systems. When each passenger has multiple potential pick-up/drop-off locations, the problem will be more challenging. In the paper, we discussed a simplified carpooling route planning problem, namely the Shortest Path Tour Problem (SPTP), whose aim is to find a single-origin single-destination shortest path through an ordered sequence of disjoint node subsets. We propose Stage Dijkstra and Global Dijkstra algorithms to find the optimal shortest path, with the time complexity of O ( l ( n + m ) log ⁡ n ) and O ( l ( n + m ) log ⁡ ( l n ) ) respectively, where l represents the number of node subsets. To the best of our knowledge, O ( l ( n + m ) log ⁡ n ) is the best time complexity of the exact algorithms for SPTP. Besides, the Stage Dijkstra and Global Dijkstra algorithms both have the linear space complexity, which is highly suitable for resource-constrained environments. Experiments conducted on large-scale road networks and synthetic datasets demonstrate the effectiveness and efficiency of our proposed algorithms in terms of running time and memory consumption.

AAAI Conference 2025 Conference Paper

Enhancing Masked Time-Series Modeling via Dropping Patches

  • Tianyu Qiu
  • Yi Xie
  • Hao Niu
  • Yun Xiong
  • Xiaofeng Gao

This paper explores how to enhance existing masked time-series modeling by randomly dropping sub-sequence level patches of time series. On this basis, a simple yet effective method named DropPatch is proposed, which has two remarkable advantages: 1) It improves the pre-training efficiency by a square-level advantage; 2) It provides additional advantages for modeling in scenarios such as in-domain, cross-domain, few-shot learning and cold start. This paper conducts comprehensive experiments to verify the effectiveness of the method and analyze its internal mechanism. Empirically, DropPatch strengthens the attention mechanism, reduces information redundancy and serves as an efficient means of data augmentation. Theoretically, it is proved that DropPatch slows down the rate at which the Transformer representations collapse into the rank-1 linear subspace by randomly dropping patches, thus optimizing the quality of the learned representations.

NeurIPS Conference 2025 Conference Paper

MM-Agent: LLM as Agents for Real-world Mathematical Modeling Problem

  • Fan Liu
  • Zherui Yang
  • Cancheng Liu
  • Tianrui Song
  • Xiaofeng Gao
  • Hao Liu

Mathematical modeling is a cornerstone of scientific discovery and engineering practice, enabling the translation of real-world problems into formal systems across domains such as physics, biology, and economics. Unlike mathematical reasoning, which assumes a predefined formulation, modeling requires open-ended problem analysis, abstraction, and principled formalization. While Large Language Models (LLMs) have shown strong reasoning capabilities, they fall short in rigorous model construction, limiting their utility in real-world problem-solving. To this end, we formalize the task of LLM-powered real-world mathematical modeling, where agents must analyze problems, construct domain-appropriate formulations, and generate complete end-to-end solutions. We introduce MM-Bench, a curated benchmark of 111 problems from the Mathematical Contest in Modeling (MCM/ICM), spanning the years 2000 to 2025 and across ten diverse domains such as physics, biology, and economics. To tackle this task, we propose MM-Agent, an expert-inspired framework that decomposes mathematical modeling into four stages: open-ended problem analysis, structured model formulation, computational problem solving, and report generation. Experiments on MM-Bench show that MM-Agent significantly outperforms baseline agents, achieving an 11. 88\% improvement over human expert solutions while requiring only 15 minutes and \$0. 88 per task using GPT-4o. Furthermore, under official MCM/ICM protocols, MM-Agent assisted two undergraduate teams in winning the Finalist Award (\textbf{top 2. 0\% among 27, 456 teams}) in MCM/ICM 2025, demonstrating its practical effectiveness as a modeling copilot.

AAAI Conference 2025 Conference Paper

Spatial-Temporal Heterogenous Graph Contrastive Learning for Microservice Workload Prediction

  • Mohan Gao
  • Kexin Xu
  • Xiaofeng Gao
  • Tengwei Cai
  • Haoyuan Ge

With the widely adoption of microservice architecture in the cloud computing industry, accurate prediction of workloads, especially CPU cores, can support reasonable resource allocation, thereby optimizing the resource utilization of the system. However, workload prediction is challenging in two dimensions. In the temporal dimension, workload series 1) has non-stationary characteristics, leading to poor predictability; 2) has a multi-periodic nature with entangled temporal patterns; 3) may be influenced by dynamic system states like response time and number of requests. In the spatial dimension, when regarding microservices as nodes in a distributed system, there is no topology caused by physical connections, but exists complex similarity dependencies. Extracting robust spatial features from these dependencies presents difficulties. To address these, we propose STEAM, a Spatio Temporal Heterogenous Graph Contrastive Learning for Microservice Workload Prediction. STEAM leverages non-stationary decomposition self-attention to extract temporal features from non-stationary and multi-periodic workload series, while the decoupled embedding is used to capture system state information of microservices. By treating microservices as nodes and constructing a similarity graph, STEAM effectively models the similarity relationships between microservices. To reduce the prior interference caused by the similarity threshold and improve the robustness, STEAM constructs two heterogeneous augmentation views and uses contrastive learning to extract the shared consistent spatial features. The multi-scale learning is adopted to model the long- and short-term temporal features, forming a spatio-temporal stacking structure. Experiments on two datasets, including MS dataset obtained from Ant Group, which is one of the world’s largest cloud service providers, demonstrate the superiority of STEAM.

TCS Journal 2024 Journal Article

A new similarity in clustering through users' interest and social relationship

  • Jianxiong Guo
  • Zhehao Zhu
  • Yucen Gao
  • Xiaofeng Gao

Clustering is a basic technology in data mining, and similarity measurement plays a crucial role in it. The existing clustering algorithms, especially those for social networks, pay more attention to users' properties while ignoring the global measurement across social relationships. In this paper, a new clustering algorithm is proposed, which not only considers the distance of users' properties but also considers users' social influence. Social influence can be further divided into mutual influence and self influence. With mutual influence, we can deal with users' interests and measure their similarities by introducing areas and activities, thus better weighing the influence between them in an indirect way. Separately, we formulate a new propagation model, PR-Threshold++, by merging the PageRank algorithm and Linear Threshold model, to model the self influence. Based on that, we design a novel similarity by exploiting users' distance, mutual influence, and self influence. Finally, we adjust K-medoids according to our similarity and use real-world datasets to evaluate their performance in intensive simulations.

NeurIPS Conference 2024 Conference Paper

Mixture of Link Predictors on Graphs

  • Li Ma
  • Haoyu Han
  • Juanhui Li
  • Harry Shomer
  • Hui Liu
  • Xiaofeng Gao
  • Jiliang Tang

Link prediction, which aims to forecast unseen connections in graphs, is a fundamental task in graph machine learning. Heuristic methods, leveraging a range of different pairwise measures such as common neighbors and shortest paths, often rival the performance of vanilla Graph Neural Networks (GNNs). Therefore, recent advancements in GNNs for link prediction (GNN4LP) have primarily focused on integrating one or a few types of pairwise information. In this work, we reveal that different node pairs within the same dataset necessitate varied pairwise information for accurate prediction and models that only apply the same pairwise information uniformly could achieve suboptimal performance. As a result, we propose a simple mixture of experts model Link-MoE for link prediction. Link-MoE utilizes various GNNs as experts and strategically selects the appropriate expert for each node pair based on various types of pairwise information. Experimental results across diverse real-world datasets demonstrate substantial performance improvement from Link-MoE. Notably, Link-Mo achieves a relative improvement of 18. 71% on the MRR metric for the Pubmed dataset and 9. 59% on the Hits@100 metric for the ogbl-ppa dataset, compared to the best baselines. The code is available at https: //github. com/ml-ml/Link-MoE/.

NeurIPS Conference 2023 Conference Paper

Alexa Arena: A User-Centric Interactive Platform for Embodied AI

  • Qiaozi Gao
  • Govind Thattai
  • Suhaila Shakiah
  • Xiaofeng Gao
  • Shreyas Pansare
  • Vasu Sharma
  • Gaurav Sukhatme
  • Hangjie Shi

We introduce Alexa Arena, a user-centric simulation platform to facilitate research in building assistive conversational embodied agents. Alexa Arena features multi-room layouts and an abundance of interactable objects. With user-friendly graphics and control mechanisms, the platform supports the development of gamified robotic tasks readily accessible to general human users, allowing high-efficiency data collection and EAI system evaluation. Along with the platform, we introduce a dialog-enabled task completion benchmark with online human evaluations.

IJCAI Conference 2023 Conference Paper

Curriculum Multi-Level Learning for Imbalanced Live-Stream Recommendation

  • Shuodian Yu
  • Junqi Jin
  • Li Ma
  • Xiaofeng Gao
  • Xiaopeng Wu
  • Haiyang Xu
  • Jian Xu

In large-scale e-commerce live-stream recommendation, streamers are classified into different levels based on their popularity and other metrics for marketing. Several top streamers at the head level occupy a considerable amount of exposure, resulting in an unbalanced data distribution. A unified model for all levels without consideration of imbalance issue can be biased towards head streamers and neglect the conflicts between levels. The lack of inter-level streamer correlations and intra-level streamer characteristics modeling imposes obstacles to estimating the user behaviors. To tackle these challenges, we propose a curriculum multi-level learning framework for imbalanced recommendation. We separate model parameters into shared and level-specific ones to explore the generality among all levels and discrepancy for each level respectively. The level-aware gradient descent and a curriculum sampling scheduler are designed to capture the de-biased commonalities from all levels as the shared parameters. During the specific parameters training, the hardness-aware learning rate and an adaptor are proposed to dynamically balance the training process. Finally, shared and specific parameters are combined to be the final model weights and learned in a cooperative training framework. Extensive experiments on a live-stream production dataset demonstrate the superiority of the proposed framework.

TCS Journal 2023 Journal Article

Optimizing incremental SDN upgrades for load balancing in ISP networks

  • Yunlong Cheng
  • Hao Zhou
  • Xiaofeng Gao
  • Jiaqi Zheng
  • Guihai Chen

Software defined network (SDN) can dynamically and timely reply to the changes of network states, thus enabling advance traffic engineering mechanisms. To enhance the management ability of the network, Internet Service Providers (ISPs) are upgrading traditional network devices to SDN devices incrementally. In this paper, we study the k-LB problem, i. e. , upgrading at most k legacy switches to SDN switches to achieve load balance. We prove that k-LB problem is NP-hard and there is no polynomial time ( N + M ) 1 − ϵ -approximation algorithm for any constant ϵ > 0 unless P = NP, where N (M) is the number of switches (links) in the network. Nevertheless, we propose an effective greedy algorithm and prove that it reaches an approximation guarantee of c a v g c m i n M, where c a v g ( c m i n ) is the average (minimum) link capacity. Furthermore, we show that the greedy algorithm touches the tight lower bound of approximation ratio by extending the inapproximability result. The simulation results from large-scale ISP network topologies illustrate the effectiveness of our algorithm and show that the maximum link utilization can be decreased by 30% on average compared with the SOTA.

AAAI Conference 2022 Conference Paper

Cross-Task Knowledge Distillation in Multi-Task Recommendation

  • Chenxiao Yang
  • Junwei Pan
  • Xiaofeng Gao
  • Tingyu Jiang
  • Dapeng Liu
  • Guihai Chen

Multi-task learning (MTL) has been widely used in recommender systems, wherein predicting each type of user feedback on items (e. g, click, purchase) are treated as individual tasks and jointly trained with a unified model. Our key observation is that the prediction results of each task may contain task-specific knowledge about user’s fine-grained preference towards items. While such knowledge could be transferred to benefit other tasks, it is being overlooked under the current MTL paradigm. This paper, instead, proposes a Cross-Task Knowledge Distillation framework that attempts to leverage prediction results of one task as supervised signals to teach another task. However, integrating MTL and KD in a proper manner is non-trivial due to several challenges including task conflicts, inconsistent magnitude and requirement of synchronous optimization. As countermeasures, we 1) introduce auxiliary tasks with quadruplet loss functions to capture cross-task fine-grained ranking information and avoid task conflicts, 2) design a calibrated distillation approach to align and distill knowledge from auxiliary tasks, and 3) propose a novel error correction mechanism to enable and facilitate synchronous training of teacher and student models. Comprehensive experiments are conducted to verify the effectiveness of our framework in real-world datasets.

IJCAI Conference 2022 Conference Paper

Trading Hard Negatives and True Negatives: A Debiased Contrastive Collaborative Filtering Approach

  • Chenxiao Yang
  • Qitian Wu
  • Jipeng Jin
  • Xiaofeng Gao
  • Junwei Pan
  • Guihai Chen

Collaborative filtering (CF), as a standard method for recommendation with implicit feedback, tackles a semi-supervised learning problem where most interaction data are unobserved. Such a nature makes existing approaches highly rely on mining negatives for providing correct training signals. However, mining proper negatives is not a free lunch, encountering with a tricky trade-off between mining informative hard negatives and avoiding false ones. We devise a new approach named as Hardness-Aware Debiased Contrastive Collaborative Filtering (HDCCF) to resolve the dilemma. It could sufficiently explore hard negatives from two-fold aspects: 1) adaptively sharpening the gradients of harder instances through a set-wise objective, and 2) implicitly leveraging item/user frequency information with a new sampling strategy. To circumvent false negatives, we develop a principled approach to improve the reliability of negative instances and prove that the objective is an unbiased estimation of sampling from the true negative distribution. Extensive experiments demonstrate the superiority of the proposed model over existing CF models and hard negative mining methods.

TCS Journal 2021 Journal Article

A unified task recommendation strategy for realistic mobile crowdsourcing system

  • Zhiyao Li
  • Bosen Cheng
  • Xiaofeng Gao
  • Huai Chen
  • Guihai Chen

A well-designed task recommendation framework aims to protect the data quality as well as increase the task execution results. However, current crowdsourcing systems ignore the fact that there are few duplicate task expectations because of the budget limitation in realistic conditions. Besides, a practical crowdsourcing system needs to recommend new tasks without previous knowledge about the concrete task content due to short task lifespan. Thus, most of the existing studies are not applicable due to the idealized assumptions. In this paper, we formally define the problem and prove it is NP-Hard. For the problem, we design a unified task recommendation system for realistic conditions to address the mentioned problems, Pioneer-Assisted Task RecommendatiON (PATRON) framework. The framework first selects a set of pioneer workers to collect initial knowledge of the new tasks. Then it adopts the k-medoids clustering algorithm to split the workers into subsets based on the worker similarity. Cluster selection and worker pruning provides accurate and efficient recommendations that satisfy the valid recommendation requirements from requesters. Finally, we conducted our experiments based on real datasets from a famous Chinese crowdsourcing platform, Tencent SOHO. The experimental results show the efficiency and accuracy of PATRON compared with three baseline methods from several perspectives, such as recommendation success rate and recommended worker quality.

TCS Journal 2020 Journal Article

Hardness of and approximate mechanism design for the bike rebalancing problem

  • Hongtao Lv
  • Fan Wu
  • Tie Luo
  • Xiaofeng Gao
  • Guihai Chen

Recently arose in the flourishing sharing economy, the bike rebalancing problem is a new challenge that concerns how to incentivize users to park bikes at system-desired locations that better meet bike demands. It can also be generalized to other location-based vehicle or tool sharing problems such as car, truck, drone, and trolley sharing. In this paper, we address this problem using an auction model under a crowdsourcing framework, where users report their original destinations and the bike sharing platform assigns proper relocation tasks to them in order to better balance the bike supply and demand. We first prove two impossibility results: (1) finding an optimal solution to the bike rebalancing problem is NP-hard, and (2) there is no approximate mechanism with bounded approximation ratio that is both truthful and budget-feasible. To overcome this barrier, we introduce two practical constraints and design a two-stage approximate mechanism that satisfies location truthfulness, budget feasibility, individual rationality, and achieves constant approximation ratio. To the best of our knowledge, we are the first to address two dimensional location truthfulness in the regime of mechanism design. In addition, our extensive experiments based on real-world dataset demonstrate that our proposed mechanism can effectively redress the imbalance of bike distribution.

TCS Journal 2020 Journal Article

Pricing and allocation algorithm designs in dynamic ridesharing system

  • Chaoli Zhang
  • Jiapeng Xie
  • Fan Wu
  • Xiaofeng Gao
  • Guihai Chen

Traffic congestion and car pollution are becoming serious plagues nowadays. High travel cost brings a great burden to people and society. A ridesharing system mitigates traffic congestion and car pollution by allowing passengers to share their travel costs with others. Traditional ridesharing platforms usually require passengers to submit their plans in advance and then design schedules for the drivers who would like to offer a ride. Nowadays, with the development of the smartphone technology, dynamic ridesharing systems enable passengers request a car anytime and anywhere. This paper mainly considers the problems of how to allocate passengers to drivers, how to charge the passengers and how to design feasible schedules for the driver in such online environment. The allocation problem is modeled as an online weighted matching problem with the graph changing over time. Firstly, we give a fair pricing method which is easy to be understood and accepted by the passengers. We develop a greedy algorithm called LiqMax_Gre for the purpose of maximizing liquidity and an algorithm called UtiMax for the purpose of maximizing utility. LiqMax_Gre achieves a competitive ratio of 1 λ + 1, where λ is the maximal number of passengers a car can take. In general, we prove that no online algorithm can have a good guarantee for the design goal of maximizing utility. Innovatively, UtiMax considers not only the current maximal utility, but also the opportunity cost, which is the utility contributed by occupying a seat. It reflects the utility in the future and thus can be used to handle the difficulty in online design. We prove that, our algorithm has a competitive ratio of 1/3 in a special case. The schedule problem is NP-hard and we design a heuristic nearest neighbor algorithm to solve it.

IJCAI Conference 2019 Conference Paper

Feature Evolution Based Multi-Task Learning for Collaborative Filtering with Social Trust

  • Qitian Wu
  • Lei Jiang
  • Xiaofeng Gao
  • Xiaochun Yang
  • Guihai Chen

Social recommendation could address the data sparsity and cold-start problems for collaborative filtering by leveraging user trust relationships as auxiliary information for recommendation. However, most existing methods tend to consider the trust relationship as preference similarity in a static way and model the representations for user preference and social trust via a common feature space. In this paper, we propose TrustEV and take the view of multi-task learning to unite collaborative filtering for recommendation and network embedding for user trust. We design a special feature evolution unit that enables the embedding vectors for two tasks to exchange their features in a probabilistic manner, and further harness a meta-controller to globally explore proper settings for the feature evolution units. The training process contains two nested loops, where in the outer loop, we optimize the meta-controller by Bayesian optimization, and in the inner loop, we train the feedforward model with given feature evolution units. Experiment results show that TrustEV could make better use of social information and greatly improve recommendation MAE over state-of-the-art approaches.

NeurIPS Conference 2019 Conference Paper

Learning Latent Process from High-Dimensional Event Sequences via Efficient Sampling

  • Qitian Wu
  • Zixuan Zhang
  • Xiaofeng Gao
  • Junchi Yan
  • Guihai Chen

We target modeling latent dynamics in high-dimension marked event sequences without any prior knowledge about marker relations. Such problem has been rarely studied by previous works which would have fundamental difficulty to handle the arisen challenges: 1) the high-dimensional markers and unknown relation network among them pose intractable obstacles for modeling the latent dynamic process; 2) one observed event sequence may concurrently contain several different chains of interdependent events; 3) it is hard to well define the distance between two high-dimension event sequences. To these ends, in this paper, we propose a seminal adversarial imitation learning framework for high-dimension event sequence generation which could be decomposed into: 1) a latent structural intensity model that estimates the adjacent nodes without explicit networks and learns to capture the temporal dynamics in the latent space of markers over observed sequence; 2) an efficient random walk based generation model that aims at imitating the generation process of high-dimension event sequences from a bottom-up view; 3) a discriminator specified as a seq2seq network optimizing the rewards to help the generator output event sequences as real as possible. Experimental results on both synthetic and real-world datasets demonstrate that the proposed method could effectively detect the hidden network among markers and make decent prediction for future marked events, even when the number of markers scales to million level.

TCS Journal 2018 Journal Article

Reachability for airline networks: fast algorithm for shortest path problem with time windows

  • Xiaofeng Gao
  • Yueyang Xianzang
  • Xiaotian You
  • Yaru Dang
  • Guihai Chen
  • Xinglong Wang

Airline network, including airports as network nodes and flight routes as directed network edges, has a lot of special features such as departure and arrival times, air ticket budget, flight capacity, transportation cost, etc. Thus, analyzing network behavior and service performance for such a network is much more difficult than that for many other networks. In this paper, taking China domestic airline network as a representative, we try to discuss the reachability issue for each airport respectively, which could reflect its regional connectivity level and service quality of civil aviation. More specifically, we evaluate reachability through many features including node degree, betweenness, closeness, etc. To get the values of some features, we design a fast Dijkstra-based all-pair shortest path algorithm with both time and budget requirements, then use Fenwick Tree to further improve the time efficiency. Actually, it is a shortest path problem with time windows and other constraints. Furthermore, we propose a faster solution by reducing the edges in the duplicated graph as a simplification and then provide the time complexity proof. Finally, we implement Analytic Hierarchy Process (AHP) to convert the reachability feature into numerical values for all airports to measure their service qualities precisely. Our results for China domestic airline network with 210 airports and 69, 160 flight routes will definitely become a guide to airline companies and civil aviation administration for their further development and management.

TCS Journal 2015 Journal Article

A better approximation for constructing virtual backbone in 3D wireless ad-hoc networks

  • Xiaofeng Gao
  • Jun Li
  • Guihai Chen

Wireless ad hoc networks have been widely used in many areas. In order to improve network performance, we often select a connected dominating set (CDS) as its virtual backbone to deal with routing-related tasks. The problem of finding a minimum CDS (MCDS) for 2-dimensional networks has been widely studied, whereas finding an MCDS in 3-dimensional networks draws more attention recently, because it can formulate the network environment more precisely. Since MCDS problem is proved to be NP-complete, lots of approximations were proposed in literature. Among those, the best approximation for MCDS in 3D network is 14. 937 in [1]. However, their projection method during the approximation deduction process is incorrect, which overthrows its final bound completely. As a consequence, in this paper we will first propose a new projection method to overcome their problem, illustrate the cardinality upper bound of independent points in a graph (which will be used to analyze the approximation ratio), and then optimize the algorithms to select MCDS with prune techniques. The major technique we use is an adaptive jitter scheme, which solves the open question in this area.

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

v2026.09.13