Decentralized federated learning (DFL) has gained significant attention due to its ability to facilitate collaborative model training without relying on a central server. However, it is highly vulnerable to backdoor attacks, where malicious participants can manipulate model updates to embed hidden functionalities. In this paper, we propose BaDFL, a novel Backdoor Attack defense mechanism for Decentralized Federated Learning. BaDFL enhances robustness by applying strategic model clipping at the local update level. To the best of our knowledge, BaDFL is the first decentralized federated learning algorithm with theoretical guarantees against model poisoning attacks. Specifically, BaDFL achieves an asymptotically optimal convergence rate of$O(\frac{1}{\sqrt{nT}})$, wherenis the number of nodes andTis the global maximum iteration number. Furthermore, we provide a comprehensive analysis under two different attack scenarios, showing that BaDFL maintains robustness within a specific defense radius. Extensive experimental results show that, on average, BaDFL can effectively defend against model poisoning within 6 mitigation rounds, with less than a 1% drop in accuracy.

The shipping industry has irreplaceable importance in international trade and commerce. How to dynamically price different containers has long been a hot topic due to its direct connection to the final revenue. Two critical observations have been made after a comprehensive survey within a top liner company, China Ocean Shipping Company (COSCO). (1) Each type of container carried on a liner ship has its maximum capacity. (2) The sales volume is occasionally subject to huge fluctuations due to rare uncontrollable factors, such as COVID. Based on the above two points and the liner routine's periodic nature, we model the dynamic pricing problem as an episodic MDP model integrating with both capacity constraints and adversarial corruption, named C3-MDP. To maximize the cumulative revenue in the C3-MDP setting, we propose a programming framework, Bonus-Exploration based Episodic Programming (BEEP). This framework can directly accommodate the linear programming algorithm to form the algorithm BEEP-LP, which provides the episode-wise greedy optimal strategy. Furthermore, a detailed regret analysis is provided, showing that BEEP-LP has a regret that is sublinear in the number of episodes. Combining deep techniques, we also present an approximation algorithm BEEP-DQN in the case of large state-action space to strike a balance between the running time and the performance. Abundant experiments based on real container sales data exhibit the rationality of C3-MDP and the effectiveness of BEEP.

Car-hailing services play an important role in the modern transportation system, and the utilities of the service providers highly depend on the efficiency of route planning algorithms. A widely adopted route planning framework is to assign weights to roads and compute the routes with the shortest path algorithms. Existing techniques of weight-assigning often focus on the traveling time and length of the roads, but cannot incorporate with the preferences of the passengers (users).

In tiny object detection, the main challenges are tiny objects’ weak feature responses and possible semantic disappearance in deep networks. To address the problems, we proposed an Instance-level, Scale-adaptive, Shape-preserved, and Semantic-consistent Supervision (I4S) module for better locating tiny objects. It models across-scale feature responses of an instance as an elliptic cone, whose axis indicates the instance’s semantic center in different scales. By the cone supervision on across-scale feature maps, it not only exploits the classification semantic from multi-scale feature maps, but also preserves and explores the information of instance shape in consecutive scales. Experiment results on public datasets proved that our method can effectively improve the location accuracy and significantly reduce the missed detection rate comparing with the method of directly fusing multi-scale features.

With the growing demand for global trade transportation, the shipping container market has gained an increasingly important position. As a key issue of the market, container pricing is regarded as an important indicator to adjust the market supply and demand as well as the revenue of liner enterprises. Although various methods aimed at increasing enterprise revenue, such as expert pricing and dynamic pricing, have been proposed by industry and academia in recent years, these approaches rarely yield worst-case performance guarantee for the double-sided online scenarios of commodities and buyers.To cater to the double-sided online scenario and provide theoretical performance guarantee, we propose an online learning-based pricing framework named Balancing Inventory and Revenue with -chasing Decider (BIRD). BIRD determines container price by combining advantages of given multiple online pricing strategies. We utilize a strategy selector A to select a proper target strategy and use an ϵ-chasing decider ${{{\mathfrak{D}}}^{Cha\operatorname{s} ing}}$ to determine the price. BIRD is proven to combine the advantages of multiple online pricing strategies to achieve the performance close to the posterior optimal strategy for any sequence of online buyers on realistic sales platforms with inventory limitation. BIRD is proved to yield a vanishing regret for the online posted pricing problem with the features of limited inventory and multi-unit demand. Based on the historical data provided by COSCO, one of the largest liner enterprises in the world, we experimentally demonstrate the effectiveness of the proposed algorithm.

Detecting objects in aerial images is an active yet challenging task due to the arbitrary orientation of aerial targets and the lack of details for small objects. Observing that geometric priors, e.g., some kinds of points and lines with specific geometrical properties, are helpful to determine the oriented bounding box, we proposed a Point-Line-Region (PLR) supervision module embedded in the Feature Pyramid Networks (FPN) to learn the robust geometrical features, which are conducive to evaluate and locate the orientation, vertexes, and boundary of the bounding box. Our method improves feature representations of aerial targets by utilizing the supervision of across-category geometrical semantics rather than their category semantics in the previous works. Extensive comparison experiments on the DOTA dataset prove that remarkable accuracy gains of mAP, about 2.1%, are achieved by integrating the PLR module in different architectures of networks.

This work focuses on a novel agricultural application of monitoring and managing summer shoots on citrus fruit trees. To enhance the management efficiency and reliability, a novel scheme based on aerial image analysis was presented to implement intelligent supervision. To this end, we proposed an end-to-end network containing three main modules, i.e. semantic circle detection, circle-inner segmentation, and decision classification. They are respectively in charge of detecting multiple trees, evaluating each tree’s shoot quantity, and predicting management decision for each tree in aerial images. Detailed experiment analysis validates the proposed scheme and network on the aerial images collected from practical citrus orchards.

Cloud computing develops rapidly in recent years and provides service to many applications, in which job scheduling becomes more and more important to improve the quality of service. Parallel processing on cloud requires different machines starting simultaneously on the same job and brings processing slowdown due to communications overhead, defined as synchronization constraint and parallel slowdown. This paper investigates a new job scheduling problem of makespan minimization on uniform machines and identical machines with synchronization constraint and parallel slowdown. We first conduct complexity analysis proving that the problem is difficult in the face of adversarial job allocation. Then we propose a novel job scheduling algorithm, United Wrapping Scheduling (UWS), and prove that UWS admits an O(logm)-approximation for makespan minimization over m uniform machines. For the special case of identical machines, UWS is simplified to Sequential Allocation, Refilling and Immigration algorithm (SARI), proved to have a constant approximation ratio of 8 (tight up to a factor of 4). Performance evaluation implies that UWS and SARI have better makespan and realistic approximation ratio of 2 compared to baseline methods United-LPT and FIFO, and lower bounds.

In large-scale systems, due to system complexity and demand volatility, diverse and dynamic workloads make accurate predictions difficult. In this work, we address an online interval prediction problem (OnPred-Int) and adopt ensemble learning to solve it. We depict that the ensemble learning for OnPred-Int is a dynamic deterministic Markov Decision Process (Dd-MDP) and convert it into a stateful online learning task. Then we propose IPOC, a lightweight and flexible model able to produce effective confidence intervals, adapting the dynamics of real-time workload streams. At each time, IPOC selects a target model and executes chasing for it by a designed chasing oracle, during which process IPOC produces accurate confidence intervals. The effectiveness of IPOCis theoretically validated through sublinear regret analysis and satisfaction of confidence interval requirements. Besides, we conduct extensive experiments on 4 real-world datasets comparing with 19 baselines. To the best of our knowledge, we are the first to apply the frontier theory of online learning to time series prediction tasks.

In agricultural pest management based on computer vision, numerous species of tiny pests need to be detected in images. However, such tiny detection objects are usually missed when adopting deep detection networks. To improve the detection of tiny pests, this paper presented an adaptive tiny object detection network based on the CenterNet framework. Firstly, a branch with a learnable gating function is integrated into the backbone, and supervised learning is performed on it so that tiny pests’ high-resolution feature maps with category and location semantics are exploited, and the learned gating function adaptively controls the combination of such feature maps and the backbone. Moreover, we proposed a size-adaptive weighting method to improve the CenterNet’s detection loss function. In training, a higher weight will be assigned to an instance if its size is smaller or its prediction center is farther from the ground truth. Extensive experiments on multiple datasets verify that our two contributions, i.e. the adaptive-gating branch, and the size-adaptive weighting method, are both help to enhance tiny pests’ weak feature responses and their discriminations, and further improve the IoU accuracies in detection.

This paper considers a variant of the online paging problem, where the online algorithm has access to multiple predictors, each producing a sequence of predictions for the page arrival times. The predictors may have occasional prediction errors and it is assumed that at least one of them makes a sublinear number of prediction errors in total. Our main result states that this assumption suffices for the design of a randomized online algorithm whose time-average regret with respect to the optimal offline algorithm tends to zero as the time tends to infinity. This holds (with different regret bounds) for both the full information access model, where in each round, the online algorithm gets the predictions of all predictors, and the bandit access model, where in each round, the online algorithm queries a single predictor. While online algorithms that exploit inaccurate predictions have been a topic of growing interest in the last few years, to the best of our knowledge, this is the first paper that studies this topic in the context of multiple predictors for an online problem with unbounded request sequences. Moreover, to the best of our knowledge, this is also the first paper that aims for (and achieves) online algorithms with a vanishing regret for a classic online problem under reasonable assumptions.

In this paper, a rather general online problem called \emph{dynamic resource allocation with capacity constraints (DRACC)} is introduced and studied in the realm of posted price mechanisms. This problem subsumes several applications of stateful pricing, including but not limited to posted prices for online job scheduling and matching over a dynamic bipartite graph. As the existing online learning techniques do not yield vanishing-regret mechanisms for this problem, we develop a novel online learning framework defined over deterministic Markov decision processes with \emph{dynamic} state transition and reward functions. We then prove that if the Markov decision process is guaranteed to admit an oracle that can simulate any given policy from any initial state with bounded loss --- a condition that is satisfied in the DRACC problem --- then the online learning problem can be solved with vanishing regret. Our proof technique is based on a reduction to online learning with \emph{switching cost}, in which an online decision maker incurs an extra cost every time she switches from one arm to another. We formally demonstrate this connection and further show how DRACC can be used in our proposed applications of stateful pricing.

In a generalized network design (GND) problem, a set of resources are assigned (non-exclusively) to multiple requests . Each request contributes its weight to the resources it uses and the total load on a resource is then translated to the cost it incurs via a resource-specific cost function. Motivated by energy efficiency applications, recently, there is a growing interest in GND using cost functions that exhibit (dis)economies of scale ((D)oS) , namely, cost functions that appear subadditive for small loads and superadditive for larger loads. The current article advances the existing literature on approximation algorithms for GND problems with (D)oS cost functions in various aspects: (1) while the existing results are restricted to routing requests in undirected graphs, identifying the resources with the graph’s edges, the current article presents a generic approximation framework that yields approximation results for a much wider family of requests (including various types of Steiner tree and Steiner forest requests) in both directed and undirected graphs, where the resources can be identified with either the edges or the vertices; (2) while the existing results assume that a request contributes the same weight to each resource it uses, our approximation framework allows for unrelated weights, thus providing the first non-trivial approximation for the problem of scheduling unrelated parallel machines with (D)oS cost functions; (3) while most of the existing approximation algorithms are based on convex programming, our approximation framework is fully combinatorial and runs in strongly polynomial time; (4) the family of (D)oS cost functions considered in the current article is more general than the one considered in the existing literature, providing a more accurate abstraction for practical energy conservation scenarios; and (5) we obtain the first approximation ratio for GND with (D)oS cost functions that depends only on the parameters of the resources’ technology and does not grow with the number of resources, the number of requests, or their weights. The design of our approximation framework relies heavily on Roughgarden’s smoothness toolbox [43], thus demonstrating the possible usefulness of this toolbox in the area of approximation algorithms.

We study network coordination problems, as captured by the setting of generalized network design (Emek et al., STOC 2018), in the face of uncertainty resulting from partial information that the network users hold regarding the actions of their peers. This uncertainty is formalized using Alon et al.'s Bayesian ignorance framework (TCS 2012). While the approach of Alon et al. is purely combinatorial, the current paper takes into account computational considerations: Our main technical contribution is the development of (strongly) polynomial time algorithms for local decision making in the face of Bayesian uncertainty.

In a generalized network design (GND) problem, a set of resources are assigned (non-exclusively) to multiple requests. Each request contributes its weight to the resources it uses and the total load on a resource is then translated to the cost it incurs via a resource specific cost function. Motivated by energy efficiency applications, recently, there is a growing interest in GND using cost functions that exhibit (dis)economies of scale ((D)oS), namely, cost functions that appear subadditive for small loads and superadditive for larger loads.

The high energy consumption has become one bottleneck in the development of the data centers (DCs), where the main energy consumers are the cooling system and the servers. Therefore, the joint optimization for the energy efficiency of the cooling system and the servers is a crucial problem, while most of previous works on energy saving only studies one of these two components in an isolated manner. In this paper, we propose a real-time strategy, rTCS (real-time Task Classification and Scheduling strategy), to jointly optimize the energy efficiency of these two components in the scenario where the tasks arrive dynamically. Strategy rTCS first labels the tasks to classify them according to their run time and end time with a time complexity of O(1) and a bounded space complexity. Then, rTCS schedules the tasks in real time based on their labels and the energy consumption model of the DC. Simulation results show that rTCS can effectively improve the energy efficiency of DCs.

We study the energy minimization problem (EMP) in the optical WDM networks with arbitrary topologies. It is assumed that the traffic requests can arrive at and depart from the network arbitrarily, and idle network devices can be dynamically switched off to save energy. For each traffic request R, we need to specify a wavelength λRand a fiber in each link along its path to carry λR. The objective is to minimize the energy consumption incurred by the active devices over the entire network for any time period [0, t]. In this paper, a randomized online algorithm is proposed for EMP. Particularly, for each traffic request, our algorithm only needs O(1)-time to determine the wavelength, and the fiber allocation procedure can be performed in a fully distributed manner in each link with polynomial time. The competitive ratio of our algorithm is bounded by O(log μ · log hmax), where μ represents the number of wavelengths carried by each fiber and hmaxrepresents the holding time of the longest traffic request.

Energy efficiency is becoming an important issue in networks. Although some research works have been devoted to this topic, only a little attention has been paid to the stability of the network equipped with the energy conservation mechanisms. In fact, we find that the stability of networks can be undermined in the worst case if it isn't considered with care by the energy conservation mechanism.In this paper, we propose an energy-efficient scheduling protocol which can guarantee the stability of the network in all cases. We start by building a new model which can be used to verify the stability of the network equipped with the energy conservation mechanisms. With this model, we transform the packet scheduling problem to a Job Shop Scheduling problem. For this problem, we propose a time-stamp based work-conserving scheduling algorithm - G-FSA. Compared with existing methods, this scheduling algorithm guarantees a tighter bound on the make span of the jobs. Then, we integrate G-FSA with a time partition approach to generate our energy-efficient packet scheduling protocol. It is proved that the obtained protocol can guarantee the stability of network in all cases. And its approximation ratio in terms of energy efficiency can be bounded by O((1+∈ )α) for any ∈ > 0, where is an input parameter depending on the hardware infrastructure. Typically, 1 <; α ≤ 3.