The Multi-Agent Path Finding (MAPF) problem is a computationally challenging task that involves coordinating collision-free trajectories for multiple cooperative agents. Although existing methods address corridor symmetry, where agents encounter repeated bidirectional conflicts in constrained environments, they typically focus exclusively on pairwise agent interactions. Our observations reveal that such pairwise symmetry frequently arises when multiple agents traverse shared corridors, necessitating repeated applications of the corridor reasoning technology over extended durations. To overcome this limitation, we propose a multi-agent corridor reasoning (MAC) technology capable of resolving group-level corridor symmetry in a single optimization step. Our theoretical analysis demonstrates that this technology preserves the completeness and optimality guarantees of Conflict-Based Search (CBS). By integrating MAC technology with CBSH-RTC, we developed CBSH-MACRT, which significantly outperforms state-of-the-art algorithms (CBSH-RTC and CBSH with mutex propagation) on standardized MAPF benchmarks, improving success rates by 8–40% and cutting runtimes by 14–67%.

Multi-exit architecture allows early-stop inference to reduce computational cost, which can be used in resource-constrained circumstances. Recent works combine the multi-exit architecture with self-distillation to simultaneously achieve high efficiency and decent performance at different network depths. However, existing methods mainly transfer knowledge from deep exits or a single ensemble to guide all exits, without considering that inappropriate learning gaps between students and teachers may degrade the model performance, especially in shallow exits. To address this issue, we propose Multi-exit self-distillation with Appropriate TEachers (MATE) to provide diverse and appropriate teacher knowledge for each exit. In MATE, multiple ensemble teachers are obtained from all exits with different trainable weights. Each exit subsequently receives knowledge from all teachers, while focusing mainly on its primary teacher to keep an appropriate gap for efficient knowledge transfer. In this way, MATE achieves diversity in knowledge distillation while ensuring learning efficiency. Experimental results on CIFAR-100, TinyImageNet, and three fine-grained datasets demonstrate that MATE consistently outperforms state-of-the-art multi-exit self-distillation methods with various network architectures.

Channel-wise distillation for semantic segmentation has proven to be a more effective method than spatial-based distillation. By removing the redundant information from the teacher model, the student can focus on specific channel-related pixels, which can be viewed as a weighting of the pixels. However, the standard channel-wise distillation ignores the fact that such importance difference also exists among channels. In this paper, we propose a novel method called Holistic Weighted Distillation (HWD) to address this issue. We calculate the channel divergences between the teacher and the student, and convert them into distillation weights, making the student focus more on learning channels that are not well mastered, thus improving the final model performance. Besides, our method does not introduce additional network structure or back-propagation process, which improves the training efficiency. Experiments on ADE20K, Cityscapes, and COCO-Stuff demonstrate the superiority of our method. The code is available at https://github.com/zju-SWJ/HWD.

Although diffusion model has shown great potential for generating higher quality images than GANs, slow sampling speed hinders its wide application in practice. Progressive distillation is thus proposed for fast sampling by progressively aligning output images of N-step teacher sampler with N/2-step student sampler. In this paper, we argue that this distillation-based accelerating method can be further improved, especially for few-step samplers, with our proposed Classifier-based Feature Distillation (CFD). Instead of aligning output images, we distill teacher’s sharpened feature distribution into the student with a dataset-independent classifier, making the student focus on those important features to improve performance. We also introduce a dataset-oriented loss to further optimize the model. Experiments on CIFAR-10 show the superiority of our method in achieving high quality and fast sampling. Code is available at https://github.com/zju-SWJ/RCFD.

Analyzing network robustness under various circumstances is generally regarded as a challenging problem. Robustness against failure is one of the essential properties of large-scale dynamic network systems such as power grids, transportation systems, communication systems, and computer networks. Due to the network diversity and complexity, many topological features have been proposed to capture specific system properties. For power grids, a popular process for improving a network’s structural robustness is via the topology design. However, most of existing methods focus on localized network metrics, such as node connectivity and edge connectivity, which do not encompass a global perspective of cascading propagation in a power grid. In this paper, we use an informative global metric algebraic connectivity because it is sensitive to the connectedness in a broader spectrum of graphs. Our process involves decreasing the average propagation in a power grid by minimizing the increase in its algebraic connectivity. We propose a topology-based greedy strategy to optimize the robustness of the power grid. To evaluate the network robustness, we calculate the average propagation using MATCASC to simulate cascading line outages in power grids. Experimental results illustrate that our proposed method outperforms existing techniques.

Device selection is a central issue for federated learning (FL) in a network with limited bandwidth resources, e.g., OFDMA. More participating devices in learning lead to faster convergence but will incur longer communication delays since less bandwidth will be allocated to each device. To balance between device participation and communication delay, Shi et al. [1] propose a joint bandwidth allocation and scheduling problem to achieve fast convergence. But their solution does not guarantee optimality and the computational complexity of the problem remains open. To address this issue, we propose a new algorithm that optimally solves this problem in polynomial-time by casting it into a joint cardinality-constrained device selection and bandwidth allocation problem. Experimental results on non-IID data sets show that our algorithm will attain faster convergence and higher accuracy than existing methods.

Demand response (DR) has been widely adopted as a strategic plan of the electricity market in maintaining power grid reliability, sustainability, and stability. In a typical emergency DR (EDR) that arises in colocation data centers, participating tenants can reduce their power consumption when the supply of electricity is a shortage and be rewarded with financial compensation. In this paper, we study a mechanism design problem of motivating tenants for colocation EDR (MEDR). To solve the MEDR problem, we present a truthful Fully Polynomial-Time Approximation Scheme (FPTAS) which is theoretically proved deterministic, truthful and near-optimal, and can be approximated within 1 + ϵ for any given ϵ > 0, while the running time is in the polynomial of the number of tenants n and ε. To speed up the calculation of the payments, we further study the Vickrey-Clarke-Groves (VCG) based mechanism. Moreover, we build a MEDR auction system (MEDRAS) and implement all mechanism algorithms for a colocation data center. Comprehensive and detailed experiments have been implemented to validate the efficiency of our proposed mechanisms.

Spread of negative influence (N-Inf) in a networked system seems to be inevitable, e.g., epidemic spread in human networks, rumors in an online social network and computer virus plaguing the Internet etc. The widespread of N-Inf might cause severe damage and hence the Influence Blocking (IB) problem is attracting ample research interest. The IB problem aims at minimizing the N-Inf spread by immunization, i.e. selecting k (budget size) immunization nodes (Imm-nodes) to prevent the N-Inf from spreading. However, existing works for IB problem are all formulated as a one-shot task: selecting all the k Imm-nodes at the very beginning of N-Inf spread. In real world, unforeseen events might occur and one-shot policies will lack reserved measures to handle these situations. A more reasonable policy is to adaptively invest the budget based on the observation of N-Inf spread along as the time goes by. With the adaptive policy, we can both reserve resources for handling unforeseen events and save unnecessary costs if the spread of N-Inf dies out quickly. Motivated by the above considerations, we propose a novel Adaptive Influence Blocking (AIB) problem. Given the intermediate observations of N-Inf spread, the AIB problem aims at selecting Imm-nodes adaptively. We design a k-R (k-nodes-per-Round) policy which selects k Imm-nodes for each round until the budget is exhausted, and an α-T (α-Tolerance) policy which selects a new Imm-node if the expected N-Inf spread exceeds a threshold α. Scalable algorithms with provable approximation guarantees and error bounds are implemented for these policies and significant improvements on time complexity are achieved. Experimental results on real-world datasets demonstrate the effectiveness and scalability of the proposed methods.

Demand response (DR) is a vital means of electricity market in maintaining power grid reliability, sustainability and stability. DR can enable consumers (e.g. data centers) to reduce their electricity consumption when the supply of electricity is a shortage. The consumers will be rewarded if they reduce or shift some of their energy usage during peak hours. Aiming at solving the efficiency of DR, in this paper, we present MEDR, a mechanism on emergency DR in colocation data center. First, we formalize the MEDR problem and propose a dynamic programming to solve the optimization version of the problem. We then design a deterministic mechanism to solve the MEDR. We prove that our mechanism is truthful and it is an FPTAS, i.e., it can be approximated within 1 + ε for any given ε > 0, while the running time of our mechanism is polynomial in the number of tenants n and 1/ε. Furthermore, we also give an auction system covering the efficient FPTAS algorithm as bidding decision program for DR. Finally, we choose a real dataset to build a large number of simulation datasets in performance evaluation. The results show that our mechanism outperforms near-optimal and high utility demonstrate the effectiveness of our work.

We study approximation and parameterized algorithms for R||C_max, focusing on the problem when the rank of the matrix formed by job processing times is small. Bhaskara et al. initiated the study of approximation algorithms with respect to the rank, showing that R||C_max admits a QPTAS (Quasi-polynomial time approximation scheme) when the rank is 2, and becomes APX-hard when the rank is 4. We continue this line of research. We prove that R||C_max is APX-hard even if the rank is 3, resolving an open problem. We then show that R||C_max is FPT parameterized by the rank and the largest job processing time p_max. This generalizes the parameterized results on P||C_max and R||C_max with few different types of machines. We also provide nearly tight lower bounds under Exponential Time Hypothesis which suggests that the running time of the FPT algorithm is unlikely to be improved significantly.

We consider the problem of scheduling with renewable speed-up resources. Given m identical machines, n jobs and c different discrete resources, the task is to schedule each job non-preemptively onto one of the machines so as to minimize the makespan. In our problem, a job has its original processing time, which could be reduced by utilizing one of the resources. As resources are different, the amount of the time reduced for each job is different depending on the resource it uses. Once a resource is being used by one job, it can not be used simultaneously by any other job until this job is finished, hence the scheduler should take into account the job-to-machine assignment together with the resource-to-job assignment. We observe that, the classical unrelated machine scheduling problem is actually a special case of our problem when m=c, i.e., the number of resources equals the number of machines. Extending the techniques for the unrelated machine scheduling, we give a 2-approximation algorithm when both m and c are part of the input. We then consider two special cases for the problem, with m or c being a constant, and derive PTASes (Polynomial Time Approximation Schemes) respectively. We also establish the relationship between the two parameters m and c, through which we are able to transform the PTAS for the case when m is constant to the case when c is a constant. The relationship between the two parameters reveals the structure within the problem, and may be of independent interest.

Virtualization technology enables various application services to be distributed and encapsulated within virtual machines (VMs), which are dynamically allocated to physical machines (PMs) in cloud computing environments. However, in many existing virtualized systems, the limited network bandwidth often becomes a bottleneck resource, leading to the intensification of network competition and the performance degradation for communication or data intensive applications. Aiming at reducing communication overheads and improving the application performance, in this paper, we propose an Affinity-Aware Grouping method for Allocation of VMs (AAGA). Firstly, we identity and model the problem of affinity-aware grouping-based allocation for virtual machines, and propose a detailed grouping method based on which a heuristic bin packing algorithm is used to deploy VM groups into PMs. In order to demonstrate the effectiveness of AAGA, we create multiple real virtual clusters (multi-VCs) with 56 VMs running multi-VM applications and compare application performance with Non-Affinity-aware Grouping-based Allocation methods (NAGA). Experimental results show that AAGA achieves better performance than NAGA.

Virtualization technology has been widely applied in data centers and IT infrastructures, with advantages of server consolidation and live migration. Through live migration, data centers could flexibly move virtual machines among different physical machines to balance workloads, reduce energy consumption and enhance service availability.

Virtualization brings many benefits such as improving system utilization and reducing cost through server consolidation. However, it also introduces isolation problem when running multiple virtual machine workloads in one physical platform. Additionally, with the advent of multi-core technology, more and more cores are built into one die in today's data center that will share and compete for the resource like cache. It's worthy to study the isolation of server consolidation in modern multi-core platform. However, to our knowledge there are few work done on the isolation property especially the fault isolation property when one of the virtual machine workloads is attacked in server consolidation. In this paper, we study the isolation property from performance perspective and provide two optimization methods to improve the isolation property. We first define the isolation property and quantify the performance isolation in consolidation and propose a VM-level optimization method. Then we study the fault isolation by introducing a misbehavior virtual machine in server consolidation scenario and propose a core-level cache-aware optimization method to improve the fault isolation. Experimental results show that our two optimization methods can effectively improve the performance isolation and fault isolation with 29.39% and 19.52% respectively. What's more, Oprofile/Xenoprof toolkits are used to find out the factors affecting isolation property from the hardware events level.

The growth of server consolidation is due to virtualization technology that enables multiple servers to run on a single platform. However, virtualization may bring the overheads in performance. The prediction of virtualization performance is of especially important. The contribution of our paper is two-fold. First, we propose a general model to predict the performance of consolidation. Second, we study a load balancing problem that arises in server consolidation, where is to assign a number of workloads to a small number of high-performance target servers such that the workloads in each target servers are balancing. We first model the load balancing problem as an integer linear programming. Then, an fully polynomial time approximate scheme (FPTAS) is provided to get the near optimal solution. That is to say, for any given epsiv > 0, our algorithm achieves (1+epsiv)-approximation, and its running time is polynomial of both the number of source servers and 1/epsiv when the number of target servers and the dimensions are constants.

Given a mobile telephone network, whose geographical coverage area is divided into cells, phone calls are serviced by assigning frequencies to them, so that no two calls emanating from the same or neighboring cells are assigned the same frequency. Assuming an online arrival of calls and the calls will not terminate, the problem is to minimize the span of frequencies used.