Author name cluster

Weiwei Wu

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

1 author row

AAMAS Conference 2026 Conference Paper

Learning from Delay Distributions: A New Representation for Delay-Aware Reinforcement Learning

Zhuoru Yu
Chenchen Fu
Hengkai Zhong
Wanyuan Wang
Weiwei Wu
Chun Jason Xue

Delay remains a significant challenge for applying deep reinforcement learning (DRL) in real-world scenarios. Existing delay-aware DRL methods primarily rely on state augmentation to restore the Markov property in delayed environments, yet often assume the prior knowledge of the exact delay values and suffer from performance degradation in random delay environments. However, we observe that the random delays in real-world often follow specific statistical patterns. Based on this observation, we propose a novel method that leverages distributions to represent value functions, enabling a more accurate modeling of delay uncertainty beyond traditional expectation-based methods. Building upon delay distribution properties, we introduce a stochastic delay representation mechanism to reconstruct precise returns in delayed environments and prove its convergence to the optimal policy. Finally, we apply these techniques to design the delay-aware distributional actor-critic (D2AC) DRL framework. Experimental results show that D2AC significantly outperforms state-of-the-art delay-aware DRL methods across various random delay distributions in Mu- JoCo continuous control tasks. Open source code and appendix are available at: https: //github. com/COOLAS-CS/D2AC.

PDF

AAAI Conference 2026 Conference Paper

Learning from Human Gaze: Human-like Robot Social Navigation in Dense Crowds

Zhecheng Yu
Yan Lyu
Chen Yang
Tao Chen
Yishuang Zhang
Bo Ling
Peng Wang
Guanyu Gao

Robot navigation in dense crowds requires understanding social cues that humans naturally use, yet existing methods struggle with real-world complexity. We investigate two questions: (1) Where do pedestrians look when navigating crowds? and (2) Can eye tracking improve robot navigation? To answer, we introduce GazeNav, an egocentric dataset collected via wearable eye trackers, featuring synchronized video, gaze, and trajectories in crowded environments. Analysis reveals that the gaze of pedestrians is closely related to the semantic presence and movement of other individuals, exhibiting distinct attention patterns across navigation behaviors. Building on this, we propose Gaze2Nav, a modular framework that first predicts human gaze to infer socially salient pedestrians, then incorporates the semantic attention into motion planning alongside visual inputs. Our method achieves 87.6% salient pedestrian prediction accuracy and reduces trajectory error by 15.4% over state-of-the-art baselines. By aligning with human gaze, our framework improves both performance and interpretability, advancing toward human-like, socially intelligent robot navigation.

PDF Details DOI

NeurIPS Conference 2025 Conference Paper

Faithful Dynamic Imitation Learning from Human Intervention with Dynamic Regret Minimization

Bo Ling
Zhengyu Gan
Wanyuan Wang
Guanyu Gao
Weiwei Wu
Yan Lyu

Human-in-the-loop (HIL) imitation learning enables agents to learn complex behaviors safely through real-time human intervention. However, existing methods struggle to efficiently leverage agent-generated data due to dynamically evolving trajectory distributions and imperfections caused by human intervention delays, often failing to faithfully imitate the human expert policy. In this work, we propose Faithful Dynamic Imitation Learning (FaithDaIL) to address these challenges. We formulate HIL imitation learning as an online non-convex problem and employ dynamic regret minimization to adapt to the shifting data distribution and track high-quality policy trajectories. To ensure faithful imitation of the human expert despite training on mixed agent and human data, we introduce an unbiased imitation objective and achieve it by weighting the behavior distribution relative to the human expert's as a proxy reward. Extensive experiments on MetaDrive and CARLA driving benchmarks demonstrate that FaithDaIL achieves state-of-the-art performance in safety and task success with significantly reduced human intervention data compared to prior HIL baselines.

PDF Details

AAAI Conference 2025 Conference Paper

Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction

Yixuan Li
Can Chen
Jiajun Li
Jiahui Duan
Xiongwei Han
Tao Zhong
Vincent Chau
Weiwei Wu

By exploiting the correlation between the structure and the solution of Mixed-Integer Linear Programming (MILP), Machine Learning (ML) has become a promising method for solving large-scale MILP problems. Existing ML-based MILP solvers mainly focus on end-to-end solution learning, which suffers from the scalability issue due to the high dimensionality of the solution space. Instead of directly learning the optimal solution, this paper aims to learn a reduced and equivalent model of the original MILP as an intermediate step. The reduced model often corresponds to interpretable operations and is much simpler, enabling us to solve large-scale MILP problems much faster than existing commercial solvers. However, current approaches rely only on the optimal reduced model, overlooking the significant preference information of all reduced models. To address this issue, this paper proposes a preference-based model reduction learning method, which considers the relative performance (i.e., objective cost and constraint feasibility) of all reduced models on each MILP instance as preferences. We also introduce an attention mechanism to capture and represent preference information, which helps improve the performance of model reduction learning tasks. Moreover, we propose a SetCover based pruning method to control the number of reduced models (i.e., labels), thereby simplifying the learning process. Evaluation on real-world MILP problems shows that 1) compared to the state-of-the-art model reduction ML methods, our method obtains nearly 20% improvement on solution accuracy, and 2) compared to the commercial solver Gurobi, two to four orders of magnitude speedups are achieved.

PDF Details DOI

EAAI Journal 2025 Journal Article

Fire resistance rating prediction of timber-to-steel connections and design optimization informed by explainable machine learning

Tongchen Han
Zhidong Zhang
Weiwei Wu

Timber as a construction material is experiencing its renaissance, while fire safety is a critical factor for timber-based building design. Currently, the fire resistance rating of wood-steel-wood (WSW) connections is evaluated using empirical equations derived from experimental results. However, these equations consider a limited set of parameters and lack interpretability. This paper developed an explainable machine learning (ML) model considering comprehensive parameters related to connection’s configuration, based on 140 experimental and experimental-validated numerical data. The performances of various machine learning models are evaluated in terms of predicting the fire resistance rating of connections after hyperparameter tuning. The eXtreme Gradient Boosting (XGBoost) model outperforms other ML models ( R 2 = 0. 93 ) and empirical equations. The local sensitivity analysis (LSA), global sensitivity analysis (GSA), and SHapley Additive exPlanations (SHAP) analysis are conducted based on the XGBoost model to investigate the contributions of nine parameters to the fire resistance rating. Both sensitivity analysis and SHAP analysis identify timber thickness and load ratio as the primary factors influencing fire resistance. Finally, the calibrated XGBoost model is incorporated into a non-dominated sorting genetic algorithm (NSGA-II) to optimize the design, aiming to minimize the self-weight of the connection while maximizing the fire resistance rating and load-carrying capacity of the connection subjected to constraints on limited dimensions.

Details DOI

AAAI Conference 2025 Conference Paper

Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback

Xiang Liu
Hau Chan
Minming Li
Weiwei Wu
Long Tran-Thanh

We consider a general non-stochastic online pricing bandit setting in a procurement scenario where a buyer with a budget wants to procure items from a fixed set of sellers to maximize the buyer's reward by dynamically offering purchasing prices to the sellers, where the sellers' costs and values at each time period can change arbitrarily and the sellers determine whether to accept the offered prices to sell the items. This setting models online pricing scenarios of procuring resources or services in multi-agent systems. We first consider the offline setting when sellers' costs and values are known in advance and investigate the best fixed-price policy in hindsight. We show that it has a tight approximation guarantee with respect to the offline optimal solutions. In the general online setting, we propose an online pricing policy, Granularity-based Pricing (GAP), which exploits underlying side-information from the feedback graph when the budget is given as the input. We show that GAP achieves an upper bound of O(n{v_{max}}{c_{min}}sqrt{B/c_{min}}ln B) on the alpha-regret where n, v_{max}, c_{min}, and B are the number, the maximum value, the minimum cost of sellers, and the budget, respectively. We then extend it to the unknown budget case by developing a variant of GAP, namely Doubling-GAP, and show its alpha-regret is at most O(n{v_{max}}{c_{min}}sqrt{B/c_{min}}ln2 B). We also provide an alpha-regret lower bound Omega(v_{max}sqrt{Bn/c_{min}}) of any online policy that is tight up to sub-linear terms. We conduct simulation experiments to show that the proposed policy outperforms the baseline algorithms.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Transtreaming: Adaptive Delay-aware Transformer for Real-time Streaming Perception

Xiang Zhang
Yufei Cui
Chenchen Fu
Zihao Wang
Yuyang Sun
Xue Liu
Weiwei Wu

Real-time object detection is critical for the decision-making process for many real-world applications, such as collision avoidance and path planning in autonomous driving. This work presents an innovative real-time streaming perception method, Transtreaming, which addresses the challenge of real-time object detection with dynamic computational delays. The core innovation of Transtreaming lies in its adaptive delay-aware transformer, which can concurrently predict multiple future frames and select the output that best matches the real-world present time, compensating for any system-induced computational delays. The proposed model outperforms existing state-of-the-art methods, even in single-frame detection scenarios, by leveraging a transformer-based methodology. It demonstrates robust performance across a range of devices, from powerful V100 to modest 2080Ti, achieving the highest level of perceptual accuracy on all platforms. Unlike most state-of-the-art methods that struggle to complete computation within a single frame on less powerful devices, Transtreaming meets the stringent real-time processing requirements on all kinds of devices. The experimental results emphasize the system's adaptability and its potential to significantly improve the safety and reliability of many real-world systems, such as autonomous driving.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Budget Feasible Mechanisms: A Survey

Xiang Liu
Hau Chan
Minming Li
Weiwei Wu

In recent decades, the design of budget feasible mechanisms for a wide range of procurement auction settings has received significant attention in the Artificial Intelligence (AI) community. These procurement auction settings have practical applications in various domains such as federated learning, crowdsensing, edge computing, and resource allocation. In a basic procurement auction setting of these domains, a buyer with a limited budget is tasked with procuring items (\eg, goods or services) from strategic sellers, who have private information on the true costs of their items and incentives to misrepresent their items' true costs. The primary goal of budget feasible mechanisms is to elicit the true costs from sellers and determine items to procure from sellers to maximize the buyer valuation function for the items and ensure that the total payment to the sellers is no more than the budget. In this survey, we provide a comprehensive overview of key procurement auction settings and results of budget feasible mechanisms. We provide several promising future research directions.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Factor Graph Neural Network Meets Max-Sum: A Real-Time Route Planning Algorithm for Massive-Scale Trips

Yixuan Li
Wanyuan Wang
Weiyi XU
Yanchen Deng
Weiwei Wu

Global route planning (GRP) is a typical combinatorial optimization problem that has been solved for a variety of industrial purposes, such as traffic flow management, network routing, and conflict prevention. The goal of the GRP is to find a route for each trip query such that all queries have a minimum global travel time. The GRP problem is NP-hard and computationally challenging, even for medium-sized instances. However, in real-world GRP applications, such as Google Maps-based vehicle route guidance systems, there are always massive-scale trips issued simultaneously, and real-time response is required. Existing mathematical programming-based exact methods and heuristics struggle to balance the extremes of optimality and scalability. Considering that many closed-related GRP instances must be solved repeatedly, this paper explores a deep learning approach to learn real-time and efficient solutions for GRP. This paper first proposes a novel route-query factor graph (RQ-FG) to model the GRP problem, where the message-passing damped Max-sum (DMS) algorithm can be exploited to generate high-quality approximate solutions. A hybrid pruning method is proposed to accelerate solving the DMS. We further devise a route-query factor graph neural network (RQ-FGNN) based on the RQ-FG, which has the ability to return solutions in milliseconds. Experiments demonstrate that our method can generate high-quality solutions in massive-scale GRP instances in real-time.

PDF

AAAI Conference 2024 Conference Paper

i-Rebalance: Personalized Vehicle Repositioning for Supply Demand Balance

Haoyang Chen
Peiyan Sun
Qiyuan Song
Wanyuan Wang
Weiwei Wu
Wencan Zhang
Guanyu Gao
Yan Lyu

Ride-hailing platforms have been facing the challenge of balancing demand and supply. Existing vehicle reposition techniques often treat drivers as homogeneous agents and relocate them deterministically, assuming compliance with the reposition. In this paper, we consider a more realistic and driver-centric scenario where drivers have unique cruising preferences and can decide whether to take the recommendation or not on their own. We propose i-Rebalance, a personalized vehicle reposition technique with deep reinforcement learning (DRL). i-Rebalance estimates drivers' decisions on accepting reposition recommendations through an on-field user study involving 99 real drivers. To optimize supply-demand balance and enhance preference satisfaction simultaneously, i-Rebalance has a sequential reposition strategy with dual DRL agents: Grid Agent to determine the reposition order of idle vehicles, and Vehicle Agent to provide personalized recommendations to each vehicle in the pre-defined order. This sequential learning strategy facilitates more effective policy training within a smaller action space compared to traditional joint-action methods. Evaluation of real-world trajectory data shows that i-Rebalance improves driver acceptance rate by 38.07% and total driver income by 9.97%.

PDF Details DOI

AIJ Journal 2023 Journal Article

Budget-feasible mechanisms for proportionally selecting agents from groups

Xiang Liu
Hau Chan
Minming Li
Weiwei Wu
Yingchao Zhao

In many social domains involving collective decision-making (e. g. , committee selection and survey sampling), it is often desirable to select individuals from different population groups to achieve proportional representation (e. g. , to represent the opinions of each group). For instance, in the selection of a committee (e. g. , to form a working group within a company), the planner would like to select agents from different groups to represent their respective groups proportionally. Typically, there are intrinsic private costs for agents to represent their groups, and the planner would like to compensate the selected agents via some form of payments, which is constrained by the planner's available budget. As the costs are unknown to the planner, the planner is required to design incentive mechanisms to elicit agents' real costs and provide payments (or monetary incentives) to the selected agents to ensure proportional representation and the total payments do not exceed the budget. Such a mechanism design setting falls into the budget-feasible mechanism design paradigm. However, existing budget-feasible mechanisms only consider all agents to be in the same group with non-proportional objectives. To study the above-mentioned setting, we consider the problem of designing budget-feasible mechanisms for selecting agents with private costs from various groups to ensure proportional representation, where the minimum proportion of the overall value of the selected agents from each group is maximized. We study this problem by first considering the setting with homogeneous agents who have identical values to the planner. Depending on agents' membership in the groups, we consider two models: a single group model where each agent belongs to only one group, and a multiple group model where each agent may belong to multiple groups. We propose novel budget-feasible proportion-representative mechanisms for these models that require different selection methods, i. e. , a novel greedy mechanism that considers all possible proportion ratios for the single group model and a novel mechanism that leverages the Max-Flow algorithm to evaluate the proportional representation for the multiple group model, to choose representative agents from each group. The proposed mechanisms guarantee theoretical properties of individual rationality, budget-feasibility, truthfulness, and approximation performance on maximizing the minimum proportional representation of each group. We also provide a matching lower bound for budget-feasible proportion-representative mechanisms. Finally, we non-trivially extend these mechanisms to the settings of heterogeneous agents who can have different values to the planner under the two models.

Details DOI

TCS Journal 2023 Journal Article

Budget-feasible Sybil-proof mechanisms for crowdsensing

Xiang Liu
Weiwei Wu
Wanyuan Wang
Yuhang Xu
Xiumin Wang
Helei Cui

The rapid use of smartphones and devices leads to the development of crowdsensing (CS) systems where a large crowd of participants can take part in performing data collecting tasks in large-scale distributed networks. Participants/users in such systems are usually selfish and have private information, such as costs and identities. Budget-feasible mechanism design, as a sub-field of auction theory, is a useful paradigm for crowdsensing, which naturally formulates the procurement scenario with buyers' budgets being considered and allows the users to bid their private costs. Although the bidding behavior is well-regulated, budget-feasible mechanisms are still vulnerable to the Sybil attack where users may generate multiple fake identities to manipulate the system. Thus, it is vital to provide Sybil-proof budget-feasible mechanisms for crowdsensing. In this paper, we design a budget-feasible incentive mechanism which can guarantee truthfulness and deter Sybil attack. We prove that the proposed mechanism achieves individual rationality, truthfulness, budget feasibility, and Sybil-proofness. Extensive simulation results further validate the efficiency of the proposed mechanism.

Details DOI

AAMAS Conference 2022 Conference Paper

Adaptive Aggregation Weight Assignment for Federated Learning: A Deep Reinforcement Learning Approach

Enwei Guo
Xiumin Wang
Weiwei Wu

Federated learning (FL) has recently received considerable attention due to its capability of allowing distributed clients to collaboratively train a global model without sharing their private data. However, due to the heterogeneous data distributions/contents of clients, it is non-trivial to accurately evaluate the contributions of local models in global model aggregation. Most existing works simply use the amount of data to assign weights of clients in global model aggregation, e. g. , FedAvg, which however is not effective, especially when the data of clients is non-IID. To address this issue, this paper aims to propose a novel FL algorithm, which can accurately evaluate the contributions of clients and aggregate global model in a more efficient manner. More specifically, this paper proposes a Deep Reinforcement Learning (DRL) method to dynamically learn the contributions of clients in each communication round. Based on this, we adaptively assign appropriate weights to clients, which will be used in global model aggregation. By improving the process of global mode aggregation, our proposed scheme greatly improves the performance of federated learning.

PDF

AAMAS Conference 2022 Conference Paper

Online Collective Multiagent Planning by Offline Policy Reuse with Applications to City-Scale Mobility-on-Demand Systems

Wanyuan Wang
Gerong Wu
Weiwei Wu
Yichuan Jiang
Bo An

The popularity of mobility-on-demand (MoD) systems boosts the need for online collective multiagent planning, where spatially distributed servicing agents are planned to meet dynamically arriving demands. For city-scale MoDs with a population of agents, it is necessary to find a balance between computation time (i. e. , realtime) and solution quality (i. e. , the number of demands served). Directly using an offline policy can guarantee real-time, but cannot be dynamically adjusted to real agent and demand distributions. On the other hand, search-based online planning methods are adaptive. However, they are computationally expensive and cannot scale up. In this paper, we propose a principled online multiagent planning method, which reuses and improves the offline policy in an anytime manner. We first model MoDs as a collective Markov Decision Process (C-MDP) where the history collective behavior of agents affects the joint reward. We propose a novel state value function to evaluate the policy, and a gradient ascent (GA) technique to improve the policy. We show that GA-based policy iteration (GA-PI) on local policy can converge. Finally, given real-time information, the offline policy is used as the default plan and GA-PI is used to improve it and generate an online plan. Experimentally, the proposed offline policy reuse method significantly outperforms standard online multiagent planning methods on MoD systems like ride-sharing and security traffic patrolling in terms of computation time and solution quality.

PDF

AAAI Conference 2021 Conference Paper

Budget Feasible Mechanisms Over Graphs

Xiang Liu
Weiwei Wu
Minming Li
Wanyuan Wang

This paper studies the budget-feasible mechanism design over graphs, where a buyer wishes to procure items from sellers, and all participants (the buyer and sellers) can only directly interact with their neighbors during the auction campaign. The problem for the buyer is to use the limited budget to incentivize sellers to propagate auction information to their neighbors, thereby more sellers will be informed of the auction and more item value will be procured. An impossibility result shows that the large-market assumption is necessary. We propose efficient budget-feasible diffusion mechanisms for large markets that simultaneously guarantee individual rationality, budget-feasibility, strong budget-balance, incentivecompatibility to report private costs and diffuse auction information. Moreover, the proposed mechanisms achieve logarithmic approximation that the total procured value is within a logarithmic factor of the optimal solution. Compared to most related budget-feasible mechanisms, which do not take the individual interactions among sellers into account, our mechanisms can incentivize sellers to further propagate auction information to other potential sellers. Meanwhile, existing related diffusion mechanisms only focus on seller-centric auctions and fail to satisfy the budget-feasibility of the buyer.

PDF Details

IJCAI Conference 2021 Conference Paper

Budget-feasible Mechanisms for Representing Groups of Agents Proportionally

Xiang Liu
Hau Chan
Minming Li
Weiwei Wu

In this paper, we consider the problem of designing budget-feasible mechanisms for selecting agents with private costs from various groups to ensure proportional representation, where the minimum proportion of the selected agents from each group is maximized. Depending on agents' membership in the groups, we consider two main models: single group setting where each agent belongs to only one group, and multiple group setting where each agent may belong to multiple groups. We propose novel budget-feasible proportion-representative mechanisms for these models, which can select representative agents from different groups. The proposed mechanisms guarantee theoretical properties of individual rationality, budget-feasibility, truthfulness, and approximation performance on proportional representation.

PDF Details DOI

IJCAI Conference 2018 Conference Paper

Budget-feasible Procurement Mechanisms in Two-sided Markets

Weiwei Wu
Xiang Liu
Minming Li

This paper considers the mechanism design problem in two-sided markets where multiple strategic buyers come with budgets to procure as much value of items as possible from the strategic sellers. Each seller holds an item with public value and is allowed to bid its private cost. Buyers could claim their budgets, not necessarily the true ones. The goal is to seek budget-feasible mechanisms that ensure sellers are rewarded enough payment and buyers' budgets are not exceeded. Our main contribution is a random mechanism that guarantees various desired theoretical guarantees like the budget feasibility, the truthfulness on the sellers' side and the buyers' side simultaneously, and constant approximation to the optimal total procured value of buyers.

PDF Details

AAMAS Conference 2017 Conference Paper

Protecting Elections with Minimal Resource Consumption

Yunpeng Li
Yichuan Jiang
Weiwei Wu

In democratic elections, malicious agents may attempt to control elections to achieve their own goals. To guarantee impartiality, it is necessary to protect the election outcomes from control. In this paper, we consider how to protect election outcome from control using minimal resources. We assume malicious agents attempt to prevent a specific candidate from winning a democratic election with plurality rule through denial-of-service (deletion) attacks on voter groups (e. g. , polling places). First, we show that the problem is NP-hard. Second, we propose a (|C|-1)-approximation algorithm for the problem, where |C| is the number of candidates. Finally, we validate the efficiency of our approximation algorithm based on simulation experiments.

PDF

AAMAS Conference 2016 Conference Paper

Truthful Team Formation for Crowdsourcing in Social Networks (Extended Abstract)

Wanyuan Wang
Zhanpeng He
Peng Shi
Weiwei Wu
Yichuan Jiang

We study complex task crowdsourcing by team formation in social networks (SNs), where the requester wishes to hire a group of socially close workers that can work together as a team. The workers are selfish that can manipulate the crowdsourcing system by providing unreal private information, which will discourage other workers from participation and is unprofitable for the requester. This paper develops two efficient truthful mechanisms for the small- and largescale social team crowdsourcing applications, to guarantee each worker’s profit is optimized by behaving truthfully.

PDF

TCS Journal 2013 Journal Article

Minimizing the total weighted completion time of fully parallel jobs with integer parallel units

Qiang Zhang
Weiwei Wu
Minming Li

We consider the total weighted completion time minimization in the following scheduling problem. There are m identical resources available at each time unit, and n jobs. Each job requires a number s i of resources and one resource can only be assigned to one job at each time unit. Each job is also called fully parallel such that the job is satisfied once it receives enough resources no matter how the resources distribute. The objective is to find a schedule that minimizes ∑ w i C i, where w i is the weight of job J i and C i is the time when job J i receives s i resources. We show that the total weighted completion time minimization is NP-hard when m is an input of the problem. We then give a simple greedy algorithm with an approximation ratio 2. Finally, we present a polynomial time algorithm with complexity O ( n d + 1 ) to solve this problem when the number of different resource requirements that are not multiples of m is at most d.

Details DOI

TCS Journal 2012 Journal Article

Single and multiple device DSA problems, complexities and online algorithms

Weiwei Wu
Minming Li
Wanyong Tian
Jason Chun Xue
Enhong Chen

We study the single-device Dynamic Storage Allocation (DSA) problem and the multi-device Balancing DSA problem in this paper. The goal is to dynamically allocate the job into memory to minimize the usage of space without concurrency. The SRF problem is just a variant of the DSA problem. Our results are as follows. • The NP-completeness for the 2-SRF problem, 3-DSA problem, and DSA problem for jobs with agreeable deadlines. • An improved 3-competitive algorithm for jobs with agreeable deadlines on single-device DSA problems. A 4-competitive algorithm for jobs with agreeable deadlines on multi-device Balancing DSA problems. • Lower bounds for jobs with agreeable deadlines: any non-clairvoyant algorithm cannot be ( 2 − ϵ ) -competitive and any clairvoyant algorithm cannot be ( 1. 54 − ϵ ) -competitive. • The first O ( log L ) -competitive algorithm for general jobs on multi-device Balancing DSA problems without any assumption.

Details DOI

TCS Journal 2011 Journal Article

Min-energy scheduling for aligned jobs in accelerate model

Weiwei Wu
Minming Li
Enhong Chen

A dynamic voltage scaling technique provides the capability for processors to adjust the speed and control the energy consumption. We study the pessimistic accelerate model where the acceleration rate of the processor speed is at most K and jobs cannot be executed during the speed transition period. The objective is to find a min-energy (optimal) schedule that finishes every job within its deadline. The job set we study in this paper is aligned jobs where earlier released jobs have earlier deadlines. We start by investigating a special case where all jobs have a common arrival time and design an O ( n 2 ) algorithm to compute the optimal schedule based on some nice properties of the optimal schedule. Then, we study the general aligned jobs and obtain an O ( n 2 ) algorithm to compute the optimal schedule by using the algorithm for the common arrival time case as a building block. Because our algorithm relies on the computation of the optimal schedule in the ideal model ( K = ∞ ), in order to achieve O ( n 2 ) complexity, we improve the complexity of computing the optimal schedule in the ideal model for aligned jobs from the currently best known O ( n 2 log n ) to O ( n 2 ).

Details DOI

TCS Journal 2009 Journal Article

Optimal tree structures for group key tree management considering insertion and deletion cost

Weiwei Wu
Minming Li
Enhong Chen

We study the optimal structure for the group broadcast problem where the key tree model is extensively used. The objective is usually to find an optimal key tree to minimize the cost based on certain assumptions. Under the assumption that n members arrive in the initial setup period and only member deletions are allowed after that period, previous works show that when only considering the deletion cost, the optimal tree can be computed in O ( n 2 ) time. In this paper, we first prove a semi-balance property for the optimal tree and use it to reduce the running time from O ( n 2 ) to O ( log log n ) multiplications of O ( log n ) -bit integers. Then we study the optimal tree structure when insertion cost is also considered. We show that the optimal tree is such a tree where any internal node has degree at most 7 and children of nodes with degree not equal to 2 or 3 are all leaves. Based on this result we give a dynamic programming algorithm with O ( n 2 ) time to compute the optimal tree.

Details DOI