Many real-world applications call for incorporating fairness constraints into the k-center clustering problem, where the dataset is partitioned into m demographic groups, each with a specified upper bound on the number of centers to ensure fairness. Focusing on big data scenarios, this paper addresses the problem in a streaming setting, where data points arrive sequentially in a continuous stream. Leveraging a structure called the λ-independent center set, we propose a one-pass streaming algorithm that first computes a reserved set of points during the streaming process. In the post-streaming process, we then select centers from the reserved point set by analyzing three possible cases and transforming the most complex one into a specially constrained vertex-cover problem on an auxiliary graph. Our algorithm achieves an approximation ratio of 5 + ? and memory complexity O(k log ?), where ? is the aspect ratio and ? > 0 is any small constant. Furthermore, we extend our approach to semi-structured data streams, where data points arrive in groups. In this setting, we present a (3 + ?)-approximation algorithm for m = 2, which can be readily adapted to solve the offline fair k-center problem, achieving an approximation ratio of 3 that matches the current state of the art. Lastly, we conduct extensive experiments to evaluate the performance of our approaches, demonstrating that they outperform existing baselines in both clustering cost and runtime efficiency.

Clustering is a long-standing research problem and a fundamental tool in AI and data analysis. The traditional k-center problem, known as a fundamental theoretical challenge in clustering, has a best possible approximation ratio of 2, and any improvement to a ratio of 2 - ε would imply P = NP. In this work, we study the constrained k-center clustering problem, where instance-level cannot-link (CL) and must-link (ML) constraints are incorporated as background knowledge. Although general CL constraints significantly increase the hardness of approximation, previous work has shown that disjoint CL sets permit constant-factor approximations. However, whether local search can achieve such a guarantee in this setting remains an open question. To this end, we propose a novel local search framework based on a transformation to a dominating matching set problem, achieving the best possible approximation ratio of 2. The experimental results on both real-world and synthetic datasets demonstrate that our algorithm outperforms baselines in solution quality.

Clustering is a fundamental tool that has garnered significant interest across a wide range of applications including text analysis. To improve clustering accuracy, many researchers have proposed incorporating background knowledge, typically in the form of must‑link and cannot‑link constraints, to guide the clustering process. With the recent advent of large language models (LLMs), there is growing interest in improving clustering quality through LLM-based automatic constraint generation. In this paper, we propose a novel constraint‑generation approach that reduces resource consumption by generating constraint sets rather than using traditional pairwise constraints. This improves both query efficiency and constraint accuracy compared to state‑of‑the‑art methods. We further introduce a constrained clustering algorithm tailored to the characteristics of LLM-generated constraints. Our method incorporates a confidence threshold and a penalty mechanism to address potentially inaccurate constraints. We evaluate our approach on five text datasets, considering both the cost of constraint generation and overall clustering performance. The results show that our method achieves clustering accuracy comparable to the state-of-the-art algorithms while reducing the number of LLM queries by more than 20 times.

Multi-FPGA platforms are indispensable for VLSI emulation and prototyping, but remain fundamentally constrained by limited inter-FPGA I/O bandwidth. Techniques such as time-division multiplexing and FPGA hopping partially alleviate this bottleneck but substantially increase partitioning and routing complexity and exacerbate timing closure. As modern FPGA-based applications impose stringent timing budgets, design flows must be explicitly delay-aware. In this paper, we present HoPart, a Hop-constrained partitioning approach that enforces per-path hop limits. A core ingredient of our approach is the joint optimization of path delay and congestion during partitioning. In addition, we propose a routing algorithm that adaptively adjusts the number of edges (hops) along each path based on real-time criticality metrics. This strategy reduces interconnect resource usage on non-critical paths while minimizing delay on timing-critical ones. Extensive experiments on public benchmark suites demonstrate that HoPart reduces maximum path delay by up to 30% compared with the state-of-the-art MaPart, while maintaining efficient utilization of inter-FPGA interconnect.

Modern multi-FPGA systems often integrate multiple dies to expand logic capacity and address the increasing complexity of integrated circuit designs. To overcome the limitations of physical I/O pins, these systems typically employ time-division multiplexing (TDM) technology. However, higher TDM ratios introduce considerable signal delays, resulting in higher critical connection delays. This paper focuses on optimizing the TDM ratio to tackle this challenge. We formulate the TDM ratio assignment problem as a block-angular convex program and solve it using Lagrangian decomposition, obtaining a (1 + ϵ)approximate solution for any given ϵ > 0. We further introduce a delay-aware TDM wire assignment scheme to achieve efficient signal assignment. Experimental results demonstrate that our method enables efficient, high-quality die-level routing in modern multi-FPGA systems, achieving up to 10.8% reduction in critical connection delay compared to the state-of-the-art approaches.

As a fundamental technique with many real-world applications, including social network analysis, center-based clustering may inadvertently discriminate against certain populations based on factors such as age, gender, or socioeconomic status, particularly when nodes are associated with sensitive attributes. In this work, we study the problem of fair k-center clustering in the streaming setting, which seeks to select representative items from a large data stream while respecting group-representation fairness. Given an input dataset in Euclidean space partitioned into m disjoint groups, the fairness constraint requires that the number of centers selected from each group satisfies a given upper bound. Moreover, the problem aims to select a set of centers that minimizes the maximum distance from any point to its nearest center (the k-center objective) while satisfying the fairness constraint. We present a one-pass streaming algorithm with approximation ratio 4.46, improving the previous best ratio of (5+?) for this problem in general metrics. Notably, our result establishes that streaming fair k-center admits a strictly better approximation ratio in Euclidean space than in general metrics, in contrast to the standard k-center problem, whose best-known approximation ratio is 2 in both Euclidean and general metric spaces. Finally, we complement our theoretical results with an empirical evaluation on five real-world social network datasets and million-scale synthetic datasets, demonstrating significant improvements over state-of-the-art methods in clustering quality while maintaining comparable runtime efficiency.

Any-direction wires and complex obstacle environments in emerging Printed Circuit Board (PCB) routing applications impose new challenges for length matching. To address these challenges, we develop a suite of area assignment approaches that leverage network flow theory and Linear Programming (LP) techniques. First, we partition the initial PCB region into a set of subregions and propose an LP formulation to model the area assignment of subregions to the wires in sparse PCB layouts. We then refine the LP formulation to handle dense PCB scenarios effectively. To enhance the algorithm’s performance further, we introduce utility constraints that consider complex obstacles and propose an Integer Linear Programming (ILP) model to optimize the subregion area assignment. Given the high computational complexity of solving the ILP model, we develop a combinatorial algorithm based on minimum-weight hierarchical flow to efficiently tackle the area assignment problem. By leveraging LP primal-dual techniques, we demonstrate that the proposed algorithm achieves near-optimal solutions even under upper bound constraints, and we further extend the approach to accommodate lower bound constraints. Notably, our algorithm allows the modification of the wire topology to generate better area assignment solutions. In addition, the proposed methodology is extensible to length-matching tasks in multilayer PCB designs. Lastly, we conduct extensive experiments to evaluate the effectiveness of our approach, demonstrating significant performance improvements over existing state-of-the-art methods, particularly in complex PCB routing scenarios.

Recent studies in collaborative edge computing fail to take advantage of shareable structures in multi-task learning (MTL) models and the potential of MTL models sharing at the edge. This leads to resource under-utilization at the edge. Thus, this paper focuses on shareable-structure-aware model deployment and task scheduling in collaborative multi-task inference, so as to fully utilize the low-latency potential of edge computing. Specifically, we formally define the problem with an objective to maximize edge throughput under multiple constraints (e.g., resource constraint, model integrity, etc.), and prove that it is NP-hard. To solve the problem, we first propose an approximation algorithm based on randomized rounding to generate sub-optimal solutions. We then present an adjustment strategy that generates a feasible solution when the approximation algorithm violates any of the given constraints. To evaluate the proposed algorithms, we conduct comprehensive simulations based on state-of-the-art MTL models, Google cluster-usage trace, and four kinds of computing units. Extensive experiments show that the proposed approximation algorithm coupled with the adjustment strategy, outperforms state-of-the-art methods for all cases, in terms of edge throughput.

In vehicular edge computing (VEC), two-level scheduling both at intra-vehicle and inter-vehicle offers great potential to improve quality of services for deep neural network (DNN) inference. However, existing works on two-level scheduling failed to jointly consider load balance among vehicles and the selfishness of vehicles, which results in the absence of guarantee in quality of services. This paper seeks to fill this gap by formulating an incentive problem associated with two-level scheduling aimed at load balance for DNN inference in VEC, with the objective of maximize the system utility in VEC under the constraints of per task response time, per vehicle energy consumption, per vehicle utility guarantee, etc. Then, we prove the problem is NP-complete. A coalition based incentive algorithm, called CBA, is proposed. CBA makes intra-vehicle scheduling decisions by a heuristic strategy and it makes inter-vehicle scheduling decisions by a coalition game based strategy. The Nash-stable and convergence for CBA are proved. In addition, a deep reinforcement learning based algorithm, called DRL, is proposed to solve the formulated problem. DRL introduces a heuristic strategy to generate the intra-vehicle scheduling decisions, and it exploits deep reinforcement learning method to generate the inter-vehicle scheduling decisions. The proposed algorithms are evaluated on a platform with CPUs, SCALE-Sim, OSM and SUMO. Simulation results show that two proposed algorithms outperform the state-of-the-art methods for all cases, in terms of system utility. Compared with two baseline algorithms, CBA and DRL improve system utility by an average of 0.56× and 1.24×, respectively, for different numbers of vehicles.

Witnessing the advancements in the scale and complexity of chip design, along with the benefits from high-performance computing technologies, the simulation of Very Large Scale Integration (VLSI) circuits increasingly demands acceleration through parallel computing with GPU devices. However, conventional parallel strategies fail to fully leverage modern GPU capabilities, introducing new challenges in GPU-based parallelism for VLSI simulations despite previous demonstrations of significant acceleration. In this paper, we propose a novel approach for accelerating the simulation of 4-value logic timing-aware gate-level circuits through waveform-based GPU parallelism. Our approach introduces an innovative strategy that effectively manages task dependencies during the parallelism of combinational circuits, significantly reducing the synchronization requirement between CPU and GPU. The proposed approach achieves one-pass parallelism by requiring only a single round of data transfer. Moreover, to address the implementation challenges associated with our strategy on GPU devices, we have developed and optimized a series of data structures that dynamically allocate and store newly generated outputs of uncertain scale. Finally, we conduct experiments on industrial-scale open-source benchmarks to demonstrate our approach’s performance gains over several state-of-the-art baselines.

The widespread adoption of 5 G networks and mobile devices has led to a surge in the generation of private data, creating massive data streams. Securing and continuously releasing histogram data over sliding windows in these streams has become a critical issue, as it enables understanding recent collective phenomena in data streams while preserving individual privacy. Existing state-of-the-art methods require buffering all data from each sliding window to reconstruct accurate histograms, which is unnecessary and significantly hampers efficiency. This paper proposes an online streaming sampling publication framework with differential privacy, named thePublishingApproach withSliding window estimation-count sketch(PAS), which constructs an approximate histogram without buffering each sliding window and subsequently generates publishable histograms. Specifically, we introduce a novel memory-efficient sketch structure called theSliding WindowEstimation-CountSketch(SES), which facilitates rapid retrieval of counts within sliding window intervals while providing guaranteed data protection. The output of this sketch structure approximates true counts while theoretically incorporating differentially private noise, thus ensuring$(\epsilon , \delta )$-differential privacy. Moreover, to improve the speed of histogram generation and reduce processing time in PAS, we propose an adaptive histogram generation algorithm based on SES. Extensive experiments are conducted to demonstrate the effectiveness of the proposed methods in comparison with other publication methods.

Many practical applications impose a new challenge of utilizing instance-level background knowledge (e.g., subsets of similar or dissimilar data points) within their input data to improve clustering results. In this work, we build on the widely adopted k-center clustering, modeling its input instance-level background knowledge as must-link (ML) and cannot-link (CL) constraint sets, and formulate the constrained k-center problem. Given the long-standing challenge of developing efficient algorithms for constrained clustering problems, we first derive an efficient approximation algorithm for constrained k-center at the best possible approximation ratio of 2 with linear programming (LP)-rounding technology. Recognizing the limitations of LP-rounding algorithms including high runtime complexity and challenges in parallelization, we subsequently develop a greedy algorithm that does not rely on the LP and can be efficiently parallelized. This algorithm also achieves the same approximation ratio 2 but with lower runtime complexity. Lastly, we empirically evaluate our approximation algorithm against baselines on various real datasets, validating our theoretical findings and demonstrating significant advantages of our algorithm in terms of clustering cost, quality, and runtime complexity.

Center-based clustering has attracted significant research interest from both theory and practice. In many practical applications, input data often contain background knowledge that can be used to improve clustering results. In this work, we build on widely adopted k-center clustering and model its input background knowledge as must-link (ML) and cannot-link (CL) constraint sets. However, most clustering problems including k-center are inherently NP-hard, while the more complex constrained variants are known to suffer severer approximation and computation barriers that significantly limit their applicability. By employing a suite of techniques including reverse dominating sets, linear programming (LP) integral polyhedron, and LP duality, we arrive at the first efficient approximation algorithm for constrained k-center with the best possible ratio of 2. We also construct competitive baseline algorithms and empirically evaluate our approximation algorithm against them on a variety of real datasets. The results validate our theoretical findings and demonstrate the great advantages of our algorithm in terms of clustering cost, clustering quality, and running time.

Despite Graph neural networks' significant performance gain over many classic techniques in various graph-related downstream tasks, their successes are restricted in shallow models due to over-smoothness and the difficulties of optimizations among many other issues. In this paper, to alleviate the over-smoothing issue, we propose a soft graph normalization method to preserve the diversities of node embeddings and prevent indiscrimination due to possible over-closeness. Combined with residual connections, we analyze the reason why the method can effectively capture the knowledge in both input graph structures and node features even with deep networks. Additionally, inspired by Curriculum Learning that learns easy examples before the hard ones, we propose a novel label-smoothing-based learning framework to enhance the optimization of deep GNNs, which iteratively smooths labels in an auxiliary graph and constructs many gradual non-smooth tasks for extracting increasingly complex knowledge and gradually discriminating nodes from coarse to fine. The method arguably reduces the risk of overfitting and generalizes better results. Finally, extensive experiments are carried out to demonstrate the effectiveness and potential of the proposed model and learning framework through comparison with twelve existing baselines including the state-of-the-art methods on twelve real-world node classification benchmarks.

Emerging applications in Printed Circuit Board (PCB) routing impose new challenges on automatic length matching, including adaptability for any-direction traces with their original routing preserved for interactiveness. The challenges can be addressed through two orthogonal stages: assign non-overlapping routing regions to each trace and meander the traces within their regions to reach the target length. In this paper, mainly focusing on the meandering stage, we propose an obstacle-aware detailed routing approach to optimize the utilization of available space and achieve length matching while maintaining the original routing of traces. Furthermore, our approach incorporating the proposed Multi-Scale Dynamic Time Warping (MSDTW) method can also handle differential pairs against common decoupled problems. Experimental results demonstrate that our approach has effective length-matching routing ability and compares favorably to previous approaches under more complicated constraints.

As a promising technique for offloading computation tasks from mobile devices, Unmanned Aerial Vehicle (UAV)-assisted Mobile Edge Computing (MEC) utilizes UAVs as computational resources. A popular method for enhancing the quality of service (QoS) of UAV-assisted MEC systems is to jointly optimize UAV deployment and computation task offloading. This imposes the challenge of dynamically adjusting UAV deployment and computation offloading to accommodate the changing positions and computational requirements of mobile devices. Due to the real-time requirements of MEC computation tasks, finding an efficient joint optimization approach is imperative. This paper proposes an algorithm aimed at minimizing the average response delay in a UAV-assisted MEC system. The approach revolves around the joint optimization of UAV deployment and computation offloading through convex optimization. We break down the problem into three sub-problems: UAV deployment, Ground Device (GD) access, and computation tasks offloading, which we address using the block coordinate descent algorithm. Observing the$NP$-hardness nature of the original problem, we present near-optimal solutions to the decomposed sub-problems. Simulation results demonstrate that our approach can generate a joint optimization solution within seconds and diminish the average response delay compared to state-of-the-art algorithms and other advanced algorithms, with improvements ranging from 4.70% to 42.94%.

Summary In the article, we devise streaming algorithms for maximization of a monotone submodular function subject to a cardinality constraint on the integer lattice. Based on the observation that lattice submodularity is not equivalent to diminishing return submodularity on the integer lattice but rather a weaker condition, we propose a one‐pass streaming algorithm with a modified binary search as subroutine of each step. Finally, we show that the algorithm is with approximation ratio , memory complexity , and per‐element query complexity .

Effective monitoring of applications in wireless sensor networks can be underpinned by the multiple coverage problem with unit disks. In the problem, we are given a set of targets T = {t1, t2, …, tn} distributed in the plane, where tineeds to be covered f(ti) times for any positive integer f(ti). The aim is to place a minimum number of disks, such that all the targets can be covered as desired. In the paper, we first present a 5-approximation algorithm with runtime O(n + m) for m = maxi{f(ti)}. Then, we give a theoretically improved 4-approximation algorithm, albeit with an increased time complexity to O(n2). In addition, we consider the online setting where targets arrive in sequence and upon each arrival the corresponding coverage disk must be placed. For this setting, we devise an online algorithm with a competitive ratio of 6 and constant update time. To verify aforementioned theoretical findings, numerical experiments are conducted to demonstrate and compare the practical performance of the proposed algorithms.

Abstract Witnessing broad energy‐critical applications of barrier coverage in mobile and wireless sensor networks, emerging practical applications have recently brought a new barrier coverage model which uses sink‐based mobile sensors for covering a given barrier with the aim of prolonging the lifespan of the coverage. In the model, a set of sink stations were distributed on the plane in which each sink can emit mobile sensors with an identical radius. The task is to cover a given line barrier with the emitted mobile sensors, aiming to minimize the maximum movement of the sensors so as to prolong the shortest lifespan among the sensors in coverage. In this paper, we first devise an algorithm for optimally solving the problem based on the properties of the structures called movement parity and tangent equilibrium points between the sinks. Then based on a more sophisticated geometric property of optimum solutions, we improve the runtime to a linear runtime O(k) which attains the possibly optimum runtime of the problem for k being the number of sinks. At last, numerical experiments are carried out to demonstrate the practical performance gain of our algorithms against baselines in literature.

Manifold learning is an important class of methods for nonlinear dimensionality reduction. Among them, the LLE optimisation goal is to maintain the relationship between local neighbourhoods in the original embedding manifold to reduce dimensionality, and NPE is a linear approximation to LLE. However, these two algorithms only consider maintaining the neighbour relationship of samples in low-dimensional space and ignore the global features between non-neighbour samples, such as the face shooting angle. Therefore, in order to simultaneously consider the nearest neighbour structure and global features of samples in nonlinear dimensionality reduction, it can be linearly calculated. This work provides a novel linear dimensionality reduction approach named non-neighbour and neighbour preserving embedding (NNNPE). First, we rewrite the objective function of the algorithm LLE based on the principle of our novel algorithm. Second, we introduce the linear mapping to the objective function. Finally, the mapping matrix is calculated by the method of the fast learning Mahalanobis metric. The experimental results show that the method proposed in this paper is effective.

Along with device scaling, the drain-to-drain abutment (DDA) and fence region constraints arise as emerging challenges in modern circuit designs, incurring additional difficulties, especially for designs with mixed-cell-height standard cells which have prevailed in advanced technology. This article presents the first work to address the mixed-cell-height placement problem considering the DDA and fence region constraints from post-global placement throughout the detailed placement. Our algorithm consists of three major stages: 1) preprocessing; 2) legalization; and 3) detailed placement. At the preprocessing stage, we align cells to the desired rows that meet the region constraint, considering the total cell displacement and the distribution ratio of source nodes to drain nodes simultaneously. After deciding the cell ordering of every row, we first propose an interval concept to handle fixed macros and fence regions and then apply the robust modulus-based matrix splitting iteration method to remove all cell overlaps with minimized total displacement at the legalization stage. For detailed placement, unlike the existing works that can handle the DDA constraint only for single rows, we propose a satisfiability-based approach that considers the whole layout to fix the DDA violations more effectively. Besides, we further present an integer linear program (ILP)-based method to optimize the cell displacement without increasing the DDA violations. Compared with a shortest-path method, experimental results show that our proposed algorithm can significantly reduce cell violations, average cell displacement, and maximum cell displacement, in a comparable runtime.

As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest$k$-path problem ($k$-VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph$G$of order$n$, BP algorithm converges to the unique optimal solution of$k$-VDSP on$G$within$O(n^{2}w_{max})$iterations, provided that the weight$w_{e}$is nonnegative integral for each arc$e\in E(G)$, where$w_{max}=\max \{w_{e}: e\in E(G)\}$. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of$k$-VDSP to the case of multiple sources or sinks.

The data imbalance problem often occurs in nanometer VLSI applications, where normal cases far outnumber error ones. Many imbalanced data handling methods have been proposed, such as oversampling minority class samples and downsampling majority class samples. However, existing methods focus on improving the quality of minority classes while causing quality deterioration of majority ones. In this paper, we propose a two-stage classifier to handle the data imbalance problem. We first develop an iterative neural network framework to reduce false alarms. Then the oversampling method on a final classification network is applied to predict the two classes better. As a result, the data imbalance problem is well handled, and the quality deterioration of majority classes is also reduced. Since the iterative stage does not change any existing network structure, any convolutional neural network can be used in the framework. Compared with the state-of-the-art imbalanced data handling methods, experimental results on the hotspot detection problem show that our two-stage classification method achieves the best prediction accuracy and reduces false alarms significantly.

Emerging IoT applications have brought up new coverage problems with sink-based mobile sensors. In this paper, we first focus on the MinSum Sink-based Line Barrier Coverage (SLBC) problem of covering a line barrier with mobile sensors originated at sink stations distributed on the plane. The objective is to minimize the movement sum of the sensors for the sake of energy efficiency. When the sinks emit sensors with non-uniform radii, we prove the MinSum SLBC problem is$\mathcal{NP}$-complete via reducing from the Partition problem that is known$\mathcal{NP}$- complete. Then for the MinSum Sink-based on-a-Line Target Coverage (SLTC) problem of covering targets on a line, an exact algorithm is presented based on grouping the targets and transforming to the shortest path problem in the auxiliary graph induced by the vertices corresponding to the groups. The algorithm runs in time$O(n^{2})$when sinks emit sensors of uniform sensing radius, and in time$O(\vert R\vert ^{2}n^{2})$for sensors of non-uniform radii, where$n$and$\vert R\vert$are respectively the number of targets and different radii. Eventually for SLBC, we propose a pseudo additive fully polynomial-time approximation scheme by extending the algorithm for SLTC. The algorithm runs in$O(k^{2}(\frac{L}{\epsilon})^{2})$time and computes a coverage with total movement provably bounded by$opt+\epsilon$for any fixed sufficiently small$\epsilon > 0$, where$opt, k$and$L$are respectively the movement of an optimum solution, the number of sinks and the length of the barrier. At last, experiments are carried out to demonstrate the practical performance gain of our algorithms.

Due to the rapid development of deep learning (DL) has brought, artificial intelligence (AI) chips were invented incorperating the traditional computing architecture with the simulated neural network structure for the sake of improving the energy efficiency. Recently, emerging deep learning AI chips imposed the challenge of allocating computing resources according to a deep neural networks (DNN), such that tasks using the DNN can be processed in a parallel and distributed manner. In this paper, we combine graph theory and combinatorial optimization technology to devise a fast floorplanning approach based on kernel graph structure, which is provided by Cerebras Systems Inc. for mapping the layers of DNN to the mesh of computing units called Wafer-Scale-Engine (WSE). Numerical experiments were carried out to evaluate our method using the public benchmarks and evaluation criteria, demonstrating its performance gain comparing to the state-of-art algorithms.

Emerging applications impose the min-max line barrier coverage (LBC) problem that aims to minimize the maximum movement of the sensors for the sake of balancing energy consumption. In the paper, we devise an algorithm for LBC that finds an optimal solution within a runtime$O(n^{2})$, improving the previous state-of-art runtime$o(n^{2}\log n)$due to [7]. The key idea to accelerating the computation of the optimum solutions is to use approximation solutions that are obtained by our devised approximation algorithm. Numerical experiments demonstrate our algorithms outperform all the other baselines including the previous state-of-art algorithm.

Emerging applications raise the min-max line barrier coverage (LBC) problem that aims to minimize the maximum movement of the sensors for the sake of balancing energy consumption. In this paper, we devise an exact algorithm to optimally solve LBC within a runtime of O(n2), comparing favorably to the previous state-of-art runtime O(n2 log n), where n is the number of sensors. To achieve the improvement, we accelerate the computation of optimum solutions by using a novel approximation algorithm. Numerical experiments demonstrated that our algorithms outperform all the other baselines, including the previous state-of-art algorithm.

Multiple multi-dimensional data streams are ubiquitous in the modern world, such as IoT applications, GIS applications and social networks. Detecting anomalies in such data streams in real-time is an important and challenging task. It is able to provide valuable information from data and then assists decision-making. However, exiting approaches for anomaly detection in multi-dimensional data streams have not properly considered the correlations among multiple multi-dimensional streams. Moreover, for multi-dimensional streaming data, online detection speed is often an important concern. In this paper, we propose a fast yet effective anomaly detection approach in multiple multi-dimensional data streams. This is based on a combination of ideas, i.e., stream pre-processing, locality sensitive hashing and dynamic isolation forest. Experiments on real datasets demonstrate that our approach achieves a magnitude increase in its efficiency compared with state-of-the-art approaches while maintaining competitive detection accuracy.

Barrier coverage is a long-lasting problem in mobile and wireless sensor networks, particularly for energy-critical applications. Recently, practical applications propose new barrier coverage applications of using sink-based mobile sensors, with the aim of minimizing the maximum energy consumed by sensor movement. In the problem, we are a set of sinks distributed on the plane each of which can emit mobile sensors with an identical radius. The task is to cover a given barrier using the mobile sensors emitted from the sinks, such that the maximum movement of the sensors is minimized. In this paper, we first design an algorithm for optimally solving the problem based on the key observation of the property against the so-called movement parity and tangent equilibrium points between the sinks. Then based on a more sophisticated investigation of the geometric property of an optimum solution, we improve the runtime of the algorithm to O(k) for k being the number of sink stations, attaining possibly the best runtime of the problem.

The classical disjoint shortest path problem has recently recalled interests from researchers in the network planning and optimization community. However, the requirement of the shortest paths being completely vertex or edge disjoint might be too restrictive and demands much more resources in a network. Partially disjoint shortest paths, in which a bounded number of shared vertices or edges is allowed, balance between degree of disjointness and occupied network resources. In this paper, we consider the problem of finding k shortest paths which are edge disjoint but partially vertex disjoint. For a pair of distinct vertices in a network graph, the problem aims to optimally find k edge disjoint shortest paths among which at most a bounded number of vertices are shared by at least two paths. In particular, we present novel techniques for exactly solving the problem with a runtime that significantly improves the current best result. The proposed algorithm is also validated by computer experiments on both synthetic and real networks which demonstrate its superior efficiency of up to three orders of magnitude faster than the state of the art.

In a mobile network, wireless data broadcast over$m$channels (frequencies) is a powerful means for distributed dissemination of data to clients who access the channels through multi-antennae equipped on their mobile devices. The$\delta$-antennae largest weight data retrieval ($\delta$ALWDR) problem is to compute a schedule for downloading a subset of data items that has a maximum total weight using$\delta$antennae in a given time interval. In this paper, we first give a linear programming (LP) relaxation for$\delta$ALWDR and show that it is polynomial-time solvable when every data item appears at most once. We also show that when there exist data items with multiple occurrences, the integrality gap of this LP formula is 2. We then present an approximation algorithm of ratio$1-\frac{1}{e}$for the$\delta$-antennae$\gamma$-separated largest weight data retrieval ($\delta$A$\gamma$LWDR) problem, a weaker version of$\delta$ALWDR where each block of up to$\gamma$data (time) slots is separated by a vacant slot on all channels, applying the techniques called collectively randomized LP rounding and layered DAG construction. We show that$\delta$A$\gamma$LWDR is${\mathcal NP}-$complete even for the simple case of$\gamma =2$,$m=3$, and equal-weight data items each appearing up to 3 times. Our algorithm runs in time$O(2^{\gamma}m^{7}T^{3.5}L)$, where$T$is the number of time slots, and$L$is the maximum length of the input. Then, from the simple observation that a ratio$\alpha$approximation solution to$\delta$A$\gamma$LWDR implies a ratio$\alpha -\epsilon$approximation solution to$\delta$ALWDR for any fixed$\epsilon >0$, we immediately have an approximation algorithm of ratio$1-\frac{1}{e}-\epsilon$for$\delta$ALWDR. Our algorithm has the same approximation ratio as the known result in[15]which holds only for$\delta =1$, with a significantly lower time complexity of$O(2^{\frac{1}{\epsilon}}\frac{1}{\epsilon}m^{7}T^{3.5}L)$(improved from$O(\epsilon ^{3.5}m^{\frac{3.5}{\epsilon}}T^{3.5}L)$of[15]). As a by-product, we also give a fixed-parameter tractable (fpt-)algorithm of time complexity$O(2^{B}m^{7}T^{3.5}L)$for$\delta$ALWDR, where$B$is the number of time slots that contain data items with multiple occurrences.

Clouds, such as Amazon Infrastructure-as-a-Service (IaaS) clouds and EMC Hybrid Cloud, impose growing requirements of resource-efficiency scheduling. The bounded flexible scheduling (BFS) problem is one of the problems proposed to meet such requirements. In BFS, we are given a set of identical machines and a set of jobs, each of which is with a value, a workload, a deadline and a parallelism degree, i.e., the maximum number of machines on which the job can execute concurrently. The problem is to compute an assignment of the given jobs to the machines, such that the total value of the jobs successfully completed by their deadlines is maximized. This paper presents a factor C/C-k approximation algorithm for BFS, where k is the maximum parallelism degree and C is the capacity of the system (i.e., the number of machines). Since C ≫ k in BFS, our result significantly improves the known best approximation ratio of (2C-k/C-k)(1-ϵ) for tight deadlines [17], and C/C-k · s/s-1/s for loose deadlines [18] on a slackness ratios > 1 that is the maximum ratio between a job's earliest actual finish time and its deadline. We first propose feasibility condition to determine whether an instance of BFS is feasible, i.e., whether there exists a scheduling according to which all jobs can finish before their deadlines, which is the key to achieve the ratio improvement of our algorithm. To prove the correctness of the feasibility condition, we give a simple linear program (LP) for a weaker version of BFS, and show that it is with an integral polyhedron and hence the version of BFS is polynomial-time solvable. Then we present a greedy algorithm and its equivalent primal-dual algorithm for the complementary problem of BFS. Both algorithms have an approximation ratio of C/C-k, and time complexity O(n2+ nT), where n is the number of jobs and T is the number of time slots. As a by-product, we show that the BFS admits a polynomial-time approximation scheme (PTAS) when T is fixed.

Let G=(V, E) be a digraph with nonnegative integral cost and delay on each edge, s and t be two vertices, and D ∈ Z+/o be a delay bound, the k disjoint Restricted Shortest Path (k RSP) problem is to compute k disjoint paths between s and t with the total cost minimized and the total delay bounded by D. In this paper, we first present a pseudo-polynomial-time algorithm with a bifactor approximation ratio of (1,2), then improve the algorithm to polynomial time with a bifactor ratio of (1+ε,2+ε) for any fixed ε>0, which is better than the current best approximation ratio (O(1+λ), O(1 + ln 1/λ)) for any fixed λʌ0. To the best of our knowledge, this is the first constant-factor algorithm that almost strictly obeys kRSP constraint.

Let G = (V, E) be a given graph with nonnegative integral edge cost and delay, S ⊆ V be a terminal set and r ∈ S be the selected root. The shallow-light Steiner tree (SLST) problem is to compute a minimum cost tree spanning the terminals of S, such that the delay between r and every other terminal is bounded by a given delay constraint D ∈ ℤ0+. It is known that the SLST problem is NP-hard and unless NP ⊆ DTIME(nlog log n) there exists no approximation algorithm with ratio (1, γ log2 n) for some fixed γ > 0 [12]. Nevertheless, under the same assumption it admits no approximation ratio better than (1, γ log2n) for some fixed γ > 0 even when D = 2 [2]. This paper first gives an exact algorithm with time complexity O(3tnD + 2tn2D2+ n3D3), where n and t are the numbers of vertices and terminals of the given graph respectively. This is a pseudo polynomial time parameterized algorithm with respect to the parameterization “number of terminals”. Later, this algorithm is improved to a parameterized approximation algorithm with a time complexity O(3tn2/∈ + 2tn4/∈2+ n6/∈3) and a bifactor approximation ratio (1 + ∈, 1). That is, for any small real number ∈ > 0, the algorithm computes a Steiner tree with delay and cost bounded by (1 + ∈)D and the optimum cost respectively.

For a given undirected (edge) weighted graph G = (V, E), a terminal set S ⊆ V and a root r ∈ S, the rooted k-vertex connected minimum Steiner network (kVSMNr) problem requires to construct a minimum-cost subgraph of G such that each terminal in S \ {R} is k-vertex connected to τ. As an important problem in survivable network design, the kVSMNτproblem is known to be NP-hard even when k 1/4 1 [14]. For k 1/4 3 this paper presents a simple combinatorial eight-approximation algorithm, improving the known best ratio 14 of Nutov [20]. Our algorithm constructs an approximate 3VSMNτthrough augmenting a two-vertex connected counterpart with additional edges of bounded cost to the optimal. We prove that the total cost of the added edges is at most six times of the optimal by showing that the edges in a 3VSMNτcompose a subgraph containing our solution in such a way that each edge appears in the subgraph at most six times.

For a given graph G with distinct vertices s, t and a given delay constraint D ∈ R+, the k-disjoint restricted shortest path (kRSP) problem of computing k-disjoint minimum cost stpaths with total delay restrained by D, is known to be NP-hard. Bifactor approximation algorithms have been developed for its special case when k = 2, while no approximation algorithm with constant single factor or bifactor ratio has been developed for general k. This paper firstly presents a (k, (1 + ε)H(k))-approximation algorithm for the kRSP problem by extending Orda's factor(1.5, 1.5) approximation algorithm [9]. Secondly, this paper gives a novel linear programming (LP) formula for the kRSP problem. Based on LP rounding technology, this paper rounds an optimal solution of this formula and obtains an approximation algorithm within a bifactor ratio of (2, 2). To the best of our knowledge, it is the first approximation algorithm with constant bifactor ratio for the kRSP problem. Our results can be applied to serve applications in networks which require quality of service and robustness simultaneously, and also have broad applications in construction of survivable networks and fault tolerance systems.

For an undirected and weighted graph G = (V, E) and a terminal set S ⊆ V , the 2-connected Steiner minimal network (SMN) problem requires to compute a minimum-weight subgraph of G in which all terminals are 2-connected to each other. This problem has important applications in design of survivable networks and fault-tolerant communication, and is known MAXSNP-hard [7], a harder subclass of NP-hard problems for which no polynomial-time approximation scheme (PTAS) is known. This paper presents an efficient algorithm of O(|V|2|S|3) time for computing a 2-vertex connected Steiner network (2VSN) whose weight is bounded by two times of the optimal solution 2-vertex connected SMN (2VSMN). It compares favorably with the currently known 2-approximation solution to the 2VSMN problem based on that to the survivable network design problem [10], [16], with a time complexity reduction of O(|V|5|E|7) for strongly polynomial time and O(|V|5γ) for weakly polynomial time where -y is determined by the sizes of input. Our algorithm applies a novel greedy approach to generate a 2VSN through progressive improvement on a set of vertex-disjoint shortest path pairs incident with each terminal of S. The algorithm can be directly deployed to solve the 2-edge connected SMN problem at the same approximation ratio within time O(|V|2|S|2). To the best of our knowledge, this result presents currently the most efficient 2-approximation algorithm for the 2-connected Steiner minimal network problem.