Search

Thanks to the increasing number and massive coverage, delivery drones, equipped with various sensors, have demonstrated significant but unexplored potentials for large-scale and low-cost urban sensing during package delivery. In this paper, we propose novel studies on the reutilization of such delivery drone resources to fill this void in urban crowdsensing. Accounting for interdependency between flying/sensing and drone delivery weight, we jointly optimize route selection, sensing time, and delivery weight allocation, to maximize delivery and sensing utility under drones energy constraints. This problem is formulated as a non-convex mixed integer non-Linear programming problem, which is proved to be NP-hard. To address this intricate problem, we propose near-optimal algorithms that leverage the equivalent objective function construction, the local search scheme, and the alternating iteration technique. Theoretical analysis indicates that our algorithms can achieve the 1/(4+ -approximation ratio (where is an arbitrarily small positive parameter and the convergence guarantee in polynomial time, for the scenarios of fixed and adjustable delivery weights, respectively. Extensive trace-based simulations and field experiments demonstrate that ours can significantly improve the delivery & sensing utility by 124.7% and the energy utilization rate by 72.2% on average, compared with the drone delivery without reusing.

Temporal networks are ubiquitous in nature and society, and tracking the dynamics of networks is fundamental for investigating the mechanisms of systems. Dynamic communities in temporal networks simultaneously reflect the topology of the current snapshot (clustering accuracy) and historical ones (clustering drift). Current algorithms are criticized for their inability to characterize the dynamics of networks at the vertex level, independence of feature extraction and clustering, and high time complexity. In this study, we solve these problems by proposing a novel joint learning model for dynamic community detection in temporal networks (also known as jLMDC) via joining feature extraction and clustering. This model is formulated as a constrained optimization problem. Vertices are classified into dynamic and static groups by exploring the topological structure of temporal networks to fully exploit their dynamics at each time step. Then, jLMDC updates the features of dynamic vertices by preserving features of static ones during optimization. The advantage of jLMDC is that features are extracted under the guidance of clustering, promoting performance, and saving the running time of the algorithm. Finally, we extend jLMDC to detect the overlapping dynamic community in temporal networks. The experimental results on 11 temporal networks demonstrate that jLMDC improves accuracy up to 8.23% and saves 24.89% of running time on average compared to state-of-the-art methods.

We study the problem of Resilient Service Provisioning for Edge computing (RSPE), i.e., how to determine a service placement strategy to maximize the expected overall utility by service provisioning, in the presence of uncertain service failures. RSPE is extremely challenging to tackle, because the explicit expression of its objective function is difficult to obtain, and it is a resilient max-min problem subject to knapsack constraints, which is unexplored so far and cannot be addressed by existing resilient optimization techniques. We first explore the potential properties of the implicit objective function, and reveal that it is monotone submodular under certain conditions. We further prove that the knapsack constraints form a q-independence system constraint, where q>0 is a constant related to the constraints. We propose two novel solutions for the general RSPE and homogeneous case, respectively. Firstly, for the general problem, we propose a “two-step greedy” algorithm achieving constant approximation ratio within polynomial time. Secondly, for the homogeneous case where one of the knapsack constraints reduces to a matroid constraint, we propose an improved “first-greedy-then-local search” polynomial time algorithm achieving better approximation ratio than the previous one. Both extensive simulations and field experiments validate the effectiveness of our proposed algorithms.

We consider the multiuser detection (MUD) problem, i.e., how to separate and decode colliding data streams, in the uplink of massive Machine Type Communications (mMTC) at millimeter wave (mmWave). Operating on factor-graphs by passing messages, the sum-product algorithm and its variants are widely applied in many other scenarios. However, in this paper, we find that their performance in mMTC at mmWave could be dramatically degraded due to the ill-conditioned MUD channel gain matrix and the existence of enormous short cycles in their corresponding factor-graphs, which are caused by the limited scattering of mmWave and the sharing of a same codebook for error correction among densely located user equipments. Assuming LDPC codes are used for error correction, we further propose a novel sum-product based approach to dealing with the MUD problem in mMTC at mmWave. It first leverages the propagation characteristics of mmWave to optimize the factor-graph for MUD by removing short cycles based on node-split and node-contraction, and then takes a dynamic-programming based method to approximate the messages passing on the resulted factor-graph, which can achieve a higher decoding accuracy. Extensive simulation results show that our approach outperforms the state-of-the-art sum-product based approaches significantly.

The data surveying this study mines methods for extracting informative and interesting knowledge from learning student datasets. The amount of data stored in education big databases is growing at an alarming rate. As such, data processing and knowledge discovery techniques can be used to discover interesting relationships between different characteristics and assessments of students. Initially to propose a novel self-analysis model which performs analysis about the different big data learning services. From the result provided by the user, the service will be ranked and analyze about the knowledge from daily activity gathered by the learner. The proposed model performs analysis to provide efficient Educational Data Mining (EDM) E-Learning system based on machine learning to ranking the users and performance evaluation in their activities. The existing method does not consider the learner activities, ranking and it focus on single feature based classification so the system doesn’t provide a better classification result. These issues to overcome introduce an Extended Multi-Labeled Gradient Boosting (XMGB) improve the classification performance both of imbalanced dataset. The method initial stage apply the Adaptive Expectation-Maximization Mixture (AEMM) method cluster the data various group and extract the E-learning multiple feature set. In this method to compute the classification time and memory provide an efficient result. Then introduce an academic activity based weight score analysis model to evaluate the learner daily activates and exam score its help to the ranking and cluster the data groups. In this proposed method analysis result to evaluate the following performance matrix: Recall, precision, F measure, classification accuracy. In this simulation analysis of the proposed method XMGB are provide an efficient classification with less time complexity compared to other existing methods.

Density-Based clustering are the main clustering algorithms because they can cluster data with different shapes and densities, but some of these algorithms have high time complexity like OPTICS (Ordering Points to Identify Clustering Structure) and DBSCAN (Density-based spatial clustering of applications with noise) where the time complexity up to O( n 2 ). In this paper, we use an approach to reduce this complexity by providing fuzzy clusters to OPTICS, which make the process of finding neighbours within an only narrow region (fuzzy group) instead of searching all the state space making the algorithm faster than the original one with keeping almost the same accuracy of the innovative algorithm. The results show that there is an improvement in execution time using some synthetic and real datasets with high dimensions.

In Intelligent Transportation Systems, images are the main data sources to be analyzed for providing intelligent and precision cognitive services. Therefore, how to protect the privacy of sensitive images in the process of information transmission has become an important research issue, especially in future no non-private data era. In this article, we design the Rearrangement-Arnold Cat Map (R-ACM) to disturb the relationship between adjacent pixels and further propose an efficient Bit-level Image Encryption Algorithm(Bl-IEA) based on R-ACM. Experiments show that the correlation coefficients of two adjacent pixels are 0.0022 in the horizontal direction, -0.0105 in the vertical direction, and -0.0035 in the diagonal direction respectively, which are obviously weaker than that of the original image with high correlations of adjacent pixels. What's more, the NPCR is 0.996120172, and the UACI is 0.334613406, which indicate that Bl-IEA has stronger ability to resist different attacks compared with other solutions. Especially, the lower time complexity and only one round permutation make it particularly suitable to be used in the time-limited intelligent transportation field.

Cloud service providers typically provide different types of virtual machines (VMs) to cloud users with various requirements. Thanks to its effectiveness and fairness, auction has been widely applied in this heterogeneous resource allocation. Recently, several strategy-proof combinatorial cloud auction mechanisms have been proposed. However, they fail to protect the bid privacy of users from being inferred from the auction results. In this paper, we design a differentially private combinatorial cloud auction mechanism (DPCA) to address this privacy issue. Technically, we employ the exponential mechanism to compute a clearing unit price vector with a probability proportional to the corresponding revenue. We further improve the mechanism to reduce the running time while maintaining high revenues, by computing a single clearing unit price, or a subgroup of clearing unit prices at a time, resulting in the improved mechanisms DPCA-S and its generalized version DPCA-M, respectively. We theoretically prove that our mechanisms can guarantee differential privacy, approximate truthfulness and high revenue. Extensive experimental results demonstrate that DPCA can generate near-optimal revenues at the price of relatively high time complexity, while the improved mechanisms achieve a tunable trade-off between auction revenue and running time., 12 pages, 6 figures

The grid-based approach is popular for point-in-polygon tests. However, there is a trade-off between the preprocessing and the inclusion test, which always requires the grid resolutions to be tuned. In this article, we address this challenge by enhancing the grid structure using y-axis-aligned stripes, which are formed by the y-axis-aligned lines passing through the endpoints of the edge segments in the cell, thereby managing the edge segments in each grid cell. Moreover, we precompute the inclusion properties of the x-axis-aligned top borders of the stripes during preprocessing. Therefore, to answer a query point with the ray crossing method, we can emit a ray from the point to propagate upwards until the ray arrives at the top border of a stripe. We thoroughly consider singular cases to guarantee each query point can be answered in the stripe that contains the point. In our method, the computational load can be decreased, as one coordinate of the intersection point between the ray and an edge is known in advance, and parallel computing can be well exploited because the branching operations for determining whether an edge intersects with the ray are saved. Experimental results show that the efficiency of our method does not vary much with respect to the grid resolutions, so the trouble of tuning grid resolutions can be avoided. Ultimately, our method with a low grid resolution can reduce the preprocessing time and still achieve a higher inclusion test efficiency than the existing methods with a high grid resolution, especially on GPUs.

Bipartite graphs widely exist in real-world scenarios and model binary relations like host-website, author-paper, and user-product. In bipartite graphs, a butterfly (i.e., $2\times 2$ bi-clique) is the smallest non-trivial cohesive structure and plays an important role in applications such as anomaly detection. Considerable efforts focus on counting butterflies in static bipartite graphs. However, they suffer from high time and space complexity when the bipartite graph of interest is given as a stream of edges. Although there are methods for approximately counting butterflies from bipartite graph streams, they suffer from either low accuracy or high time complexity. Therefore, it is still a challenge to accurately estimate butterfly counts from bipartite graph streams in a short time. To address this issue, we develop novel algorithms by exploiting the bipartite nature, which subtly integrates sampling and sketching techniques. We provide accurate estimators for butterfly counts and derive simple yet exact formulas for bounding their errors. We also conduct extensive experiments on a variety of real-world large bipartite graphs. Experimental results demonstrate that our algorithms are up to 20.0 times more accurate and up to 286.3 times faster than state-of-the-art methods under the same memory usage.

One-class collaborative filtering (OCCF) problems are prevalent in real-world recommender systems, such as news and music recommendation, but suffer from sparsity issues and particularly lack negatively preferred items. To address the challenge, the state-of-the-art algorithms assigned uninteracted items smaller weights of being negative and performed low-rank approximation over a user-item interaction matrix. However, the prior ratings of uninteracted items are usually set to zero but may not well-defined. To avert the prior ratings of uninteracted items, in this paper, we propose a novel ranking-based implicit regularizer by hypothesizing that users preference scores for uninteracted items are close to each other. The regularizer is then used in a ranking-based OCCF framework to penalize large difference of preference scores between uninteracted items. To optimize model parameters in this framework, we develop a scalable alternating least square algorithm and coordinate descent algorithm, whose time complexity is linearly proportional to data size. Finally, we extensively evaluate the proposed algorithms with six real-world datasets. The results show that the proposed regularizer significantly improves recommendation quality of ranking-based OCCF algorithms, such as BPRMF and RankALS. Moreover, the ranking-based framework with the proposed regularizer outperforms the state-of-the-art recommendation algorithms for implicit feedback.

The present study focuses on designing the memory-based sampled data control approach to achieve the desired performance from switched-type of neural networks. The overall contribution of the study can be viewed from two directions. The first part is to derive the theoretical-based sufficient stability conditions that ensure the synchronization of uncontrolled and controlled systems. The idea behind the synchronization analysis is because of time complexity and computational cost. Once, we derive the closed-loop system then user can employ them in any practical application without interruptions. The existence of time-delays during the information transmission is inevitable, and in a practical sense, the delays, which are a function of time are well-effective. Besides, the sufficient conditions are derived in terms of solvable linear matrix inequalities (LMIs), which can be solved to ensure the global asymptotical stability of the error system, derived from uncontrolled–controlled systems. Technically, the work integrates with the new type of discontinuous Lyapunov–Krasovskii functional candidate with integral terms, several delay-dependent stability conditions, and Wirtinger-based integral inequality. The second part works on utilizing the controlled system into a real-life application, say, encryption/decryption process. To an evident, the proposed controlled system is considered as crypto-system in the encryption/decryption process.

The reachability problem on directed graphs, asking whether two vertices are connected via a directed path, is an elementary problem that has been well-studied. In this paper, we study a variation of the elementary reachability problem, called the sink-reachability problem, which can be found in many applications such as static program analysis, social network analysis, large scale web graph analysis, XML document link path analysis, and the study of gene regulation relationships. To scale sink-reachablity analysis to large graphs, we develop a highly scalable sink-reachability preserving graph reduction strategy for input sink graphs, by using a composition framework. That is, individual sink-reachability preserving condensation operators, each running in linear time, are pipelined together to produce graph reduction algorithms that result in close to maximum reduction, while keeping the computation efficient. Experiments on large real-world sink graphs demonstrate the efficiency and effectiveness of our compositional approach to sink-reachability preserving graph reduction with a reduction rate of up to 99.74% for vertices and a rate of up to 99.46% for edges.

Graph planning gives rise to fundamental algorithmic questions such as shortest path, traveling salesman problem, etc. A classical problem in discrete planning is to consider a weighted graph and construct a path that maximizes the sum of weights for a given time horizon $T$. However, in many scenarios, the time horizon is not fixed, but the stopping time is chosen according to some distribution such that the expected stopping time is $T$. If the stopping time distribution is not known, then to ensure robustness, the distribution is chosen by an adversary, to represent the worst-case scenario. A stationary plan for every vertex always chooses the same outgoing edge. For fixed horizon or fixed stopping-time distribution, stationary plans are not sufficient for optimality. Quite surprisingly we show that when an adversary chooses the stopping-time distribution with expected stopping time $T$, then stationary plans are sufficient. While computing optimal stationary plans for fixed horizon is NP-complete, we show that computing optimal stationary plans under adversarial stopping-time distribution can be achieved in polynomial time. Consequently, our polynomial-time algorithm for adversarial stopping time also computes an optimal plan among all possible plans.

Auxiliary rewards are widely used in complex reinforcement learning tasks. However, previous work can hardly avoid the interference of auxiliary rewards on pursuing the main rewards, which leads to the destruction of the optimal policy. Thus, it is challenging but essential to balance the main and auxiliary rewards. In this article, we explicitly formulate the problem of rewards' balancing as searching for a Pareto optimal solution, with the overall objective of preserving the policy's optimization orientation for the main rewards (i.e., the policy driven by the balanced rewards is consistent with the policy driven by the main rewards). To this end, we propose a variant Pareto and show that it can effectively guide the policy search toward more main rewards. Furthermore, we establish an iterative learning framework for rewards' balancing and theoretically analyze its convergence and time complexity. Experiments in both discrete (grid word) and continuous (Doom) environments demonstrated that our algorithm can effectively balance rewards, and achieve remarkable performance compared with those RLs with heuristically designed rewards. In the ViZDoom platform, our algorithm can learn expert-level policies.

By employing time-varying proximal functions, adaptive subgradient methods (ADAGRAD) have improved the regret bound and been widely used in online learning and optimization. However, ADAGRAD with full matrix proximal functions (ADA-FULL) cannot handle large-scale problems due to the impractical $O(d^3)$ time and $O(d^2)$ space complexities, though it has better performance when gradients are correlated. In this paper, we propose two efficient variants of ADA-FULL via a matrix sketching technique called frequent directions (FD). The first variant named as ADA-FD directly utilizes FD to maintain and manipulate low-rank matrices, which reduces the space and time complexities to $O(\tau d)$ and $O(\tau^2d)$ respectively, where d is the dimensionality and $\tau\ll d$ is the sketching size. The second variant named as ADA-FFD further adopts a doubling trick to accelerate FD used in ADA-FD, which reduces the average time complexity to $O(\tau d)$ while only doubles the space complexity of ADA-FD. Theoretical analysis reveals that the regret of ADA-FD and ADA-FFD is close to that of ADA-FULL as long as the outer product matrix of gradients is approximately low-rank. Experimental results demonstrate the efficiency and effectiveness of our algorithms.

With the rapid growth of Internet, plenty of applications has been implemented for users to exchange resources with each other over networks. As a result, it has been a critical challenge to efficiently and fairly allocate resource among participating agents. Motivated by the famous BitTorrent system, a BD Mechanism for resource exchange allocation is proposed, which is based on a combinatorial structure called bottleneck decomposition. The mechanism has been shown to lead to market equilibrium, a state optimizing each individual's utility, and to be truthful, that is robust against agents' strategic behaviors. However, the crux on how to compute a bottleneck decomposition of any graph remains untouched. In this paper, we focus on the computation of bottleneck decomposition to fill the blanks and prove that the bottleneck decomposition of a network can be computed in O(n^6\log(nU)) time, where n and U are the number of agents and the maximal amount of resource any agent has in the network. Based on the bottleneck decomposition, a fair allocation in a resource exchange network can be obtained in polynomial time. We further carefully discuss the fairness in resource exchange scenario, showing the derived allocation satisfies several common fairness notions simultaneously.

The rapid growth of information technology and Internet applications has provided users with an explosion of information. Mobile e-commerce applications and web search engines are of great interest in extracting representative information from the original abundant information. However, the information extracted by several existing methods, such as top-k, are often quite similar, which is difficult to meet users’ demand for diversified information. In order to increase the diversity of representative information, this article proposes a data-driven approach to automatically identifying a subset of the original dataset that can cover more themes and content. The data-driven approach consists of two stages. First, a new unified similarity measure is proposed for handling dataset with categorical and numeric attributes. We inject external knowledge and attribute interactions into the similarity learning process to improve the accuracy of similarity estimation between data objects. Second, we develop an enhanced density peaks clustering algorithm based on shared nearest neighbors to automatically identify representative objects according to the previous estimated similarity. The enhanced density peaks algorithm takes the local structure in the entire data space into consideration, which makes the proposed approach relatively insensitive to variations in dataset’ density and dimensionality. Theoretical analysis demonstrates that the time complexity of the proposed approach can achieve the best $\bm {O}({\bm {N}\log \bm {N}})$ . Extensive comparison experiments were conducted on artificial and real-world datasets. The experimental results demonstrate the effectiveness and robustness of the proposed approach.

In reality, learning from multi-view multi-label data inevitably confronts three challenges: missing labels, incomplete views, and non-aligned views. Existing methods mainly concern the first two and commonly need multiple assumptions to attack them, making even state-of-the-arts involve at least two explicit hyper-parameters such that model selection is quite difficult. More roughly, they will fail in handling the third challenge, let alone addressing the three jointly. In this paper, we aim at meeting these under the least assumption by building a concise yet effective model with just one hyper-parameter. To ease insufficiency of available labels, we exploit not only the consensus of multiple views but also the global and local structures hidden among multiple labels. Specifically, we introduce an indicator matrix to tackle the first two challenges in a regression form while aligning the same individual labels and all labels of different views in a common label space to battle the third challenge. In aligning, we characterize the global and local structures of multiple labels to be high-rank and low-rank, respectively. Subsequently, an efficient algorithm with linear time complexity in the number of samples is established. Finally, even without view-alignment, our method substantially outperforms state-of-the-arts with view-alignment on five real datasets., 15 pages, 7 figures

Phylogenetic analyses commonly assume that the species history can be represented as a tree. However, in the presence of hybridization, the species history is more accurately captured as a network. Despite several advances in modeling phylogenetic networks, there is no known polynomial-time algorithm for parsimoniously reconciling gene trees with species networks while accounting for incomplete lineage sorting. To address this issue, we present a polynomial-time algorithm for the case of level-1 networks, in which no hybrid species is the direct ancestor of another hybrid species. This work enables more efficient reconciliation of gene trees with species networks, which in turn, enables more efficient reconstruction of species networks.

Attributable to emerging of Mobile Edge Computing (MEC), the hardware-constrained industrial devices have further computational and service capability in Industrial Internet of Thing (IIoT) systems. Nevertheless, unreliable network environments and unpredictable processing delays are intolerable factors for any service application. Therefore, this paper studies the associated constraint problem of how to optimize the offloading decision and resource allocation in collaborative edge computing networks with multiple IIoT devices and MEC servers. In order to achieve this purpose, the optimization problem is mathematically derived as a mixed-integer nonlinear programming (MINLP) problem which is a large-scale NP-hard problem. Then, an Improved Differential Evolution algorithm (IDE) is proposed to obtain the optimal solutions in an accessible time complexity. Finally, the performance of the IDE based resource allocation scheme has been compared with other baseline schemes. Simulation results demonstrate that the IDE based optimization scheme could significantly reduce the system delay and energy consumption.

Chromatin immunoprecipitation (ChIP-Seq) has emerged as a superior alternative to microarray technology as it provides higher resolution, less noise, greater coverage and wider dynamic range. While ChIP-Seq enables probing of DNA-protein interaction over the entire genome, it requires the use of sophisticated tools to recognize hidden patterns and extract meaningful data. Over the years, various attempts have resulted in several algorithms making use of different heuristics to accurately determine individual peaks corresponding to unique DNA-protein. However, finding all the significant peaks with high accuracy in a reasonable time is still a challenge. In this work, we propose the use of Multi-level thresholding algorithm, which we call LinMLTBS, used to identify the enriched regions on ChIP-Seq data. Although various suboptimal heuristics have been proposed for multi-level thresholding, we emphasize on the use of an algorithm capable of obtaining an optimal solution, while maintaining linear-time complexity. Testing various algorithm on various ENCODE project datasets shows that our approach attains higher accuracy relative to previously proposed peak finders while retaining a reasonable processing speed.

A networked control system (NCS) with the communication channels described by cascaded two-port networks for linear time-varying systems is studied. In this framework, a system is considered as a (possibly unbounded) linear operator that maps an input space to an output space. We consider the operator norm bounded uncertainties in the transmission matrices of two-port networks as well as the gap-type uncertainties in the plant and controller. A necessary and sufficient condition for robust stability of the NCS is generalized from the time-invariant case.

By migrating tasks from the end devices to the edge or cloud, cooperative computing in Internet of Things can support time-sensitive, high-dimensional, and complex applications while utilizing existing resources such as network bandwidth, computing resources, and storage capacity. How to design the multi-resource allocation system efficiently is a significant research problem. In this paper, we design a Multi-Resource Allocation system for cooperative computing in Internet of Things based on Deep Reinforcement Learning by redefining latency calculation models for communication, computation, and caching with consideration of practical interference factors such as Gaussian noise and data loss. The proposed system uses actor-critic as the base model for rapidly approximating the optimal policy by updating parameters of the actor and critic in respective gradient directions. The balance control parameter is introduced to fit the desired learning rate and actual learning rate. At the same time, we use the method of double experience pool to limit the exploration direction of the optimal policy, which reduces the time complexity and space complexity of the problem solution and improves the adaptability and reliability of the scheme. Experiments have demonstrated that DRL-MRA performs well in terms of average service latency under resource-constrained conditions, and the improvement is significant with the increase of network size.

Multi-order proximity is useful for effective network embedding. In contrast to many previous works that only consider order-level weights, this paper proposes to explore a more expressive node-level weighting mechanism to encode the diverse local structure, with a scalable and theoretically justified sampling strategy for its learning. Specifically, we start with a formal definition of multi-order proximity matrix which leads to our new multi-order objective based on Laplacian Eigenmaps and Skip-Gram. Then we instantiate the node-specific multi-order weights in the objective with the help of neighborhood size estimation, which indicates node-specific multi-order information. For objective learning, it is implicitly fulfilled with our proposed branching tree-like random walk strategy termed by BTWalk, which differs from the dominant chain-like walk in existing sampling techniques. BTWalk is designed by a synergetic combination of BFS (breadth-first search) and DFS (depth-first search), which is modulated according to the weights of the considered proximity orders. We theoretically analyze its cost-efficiency, and further propose the so-called Vec4Cross framework that incorporates joint node embedding and network alignment for two partially overlapped networks based on the seed matchings, whereby BTWalk is also adopted for embedding. Promising experimental results are obtained on real-world datasets across popular tasks.

Dynamic ridesharing refers to services that arrange one-time shared rides on short notice. It underpins various real-world intelligent transportation applications such as car-pooling, food delivery and last-mile logistics. A core operation in dynamic ridesharing is the "insertion operator". Given a worker and a feasible route which contains a sequence of origin-destination pairs from previous requests, the insertion operator inserts a new origin-destination pair from a newly arrived request into the current route such that certain objective is optimized. Common optimization objectives include minimizing the \rev{maximum/sum} flow time of all requests and minimizing the total travel time of the worker. Despite its frequent usage, the insertion operator has a time complexity of $O(n^3)$ , where $n$ is the number of all requests assigned to the worker. The cubic running time of insertion fundamentally limits the efficiency of urban-scale dynamic ridesharing based applications. In this paper, we propose a novel partition framework and a dynamic programming based insertion with a time complexity of $O(n^2)$ . We further improve the time efficiency of the insertion operator to $O(n)$ harnessing efficient index structures, such as fenwick tree. Evaluations on two real-world large-scale datasets show that our methods can accelerate insertion by 1.5 to 998.1 times.

This article proposes two decision-making models in an incomplete fuzzy hesitant linguistic environment and applies them to address the site selection problems for hydropower stations. For better depicting a decision maker's judgments under uncertainty, based on the concept of incomplete hesitant fuzzy linguistic preference relation, this article first defines its consistency measures from the perspective of additive consistency and multiplicative consistency, respectively. By introducing decision maker's satisfaction degree to measure the differences between the incomplete hesitant fuzzy linguistic preference relation and its corresponding weight vector, two decision-making models, which aim to achieve the maximum satisfaction degree, are established for determining the optimal weight vector. This article further designs experiments to make decision support by evaluating the proposed models from the correlation and time complexity point of view and providing sensitivity analysis. A case study concerning the site selection for a hydropower station at Yalong River is given to illustrate the decision-making process and the effectiveness of the proposed models.

The notion of age of information (AoI) has become an important performance metric in network and control systems. Information freshness, represented by AoI, naturally arises in the context of caching. We address optimal scheduling of cache updates for a time-slotted system where the contents vary in size. There is limited capacity for the cache for making updates. Each content is associated with a utility function that depends on the AoI and the time duration of absence from the cache. For this combinatorial optimization problem, we present the following contributions. First, we provide theoretical results of problem tractability. Whereas the problem is NP-hard, we prove solution tractability in polynomial time for a special case with uniform content size, by a reformulation using network flows. Second, we derive an integer linear formulation for the problem, of which the optimal solution can be obtained for small-scale scenarios. Next, via a mathematical reformulation, we derive a scalable optimization algorithm using repeated column generation. In addition, the algorithm computes a bound of global optimum, that can be used to assess the performance of any scheduling solution. Performance evaluation of large-scale scenarios demonstrates the strengths of the algorithm in comparison to a greedy schedule. Finally, we extend the applicability of our work to cyclic scheduling.

This work proposes an exact solution approach for the two-machine robust flow shop problem, where operation processing times are uncertain and vary in a given interval. Based on the concept of budgeted uncertainty, the objective is to obtain a robust scheduling that minimizes the makespan of the restricted worst-case scenario, where only a subset of job processing times will oscillate to their worst-case values. To our knowledge, this is the first work to obtain optimal solutions to this problem, by extending two classical MILP formulations for the deterministic case and combining them with a Column-and-Constraint Generation framework. For this purpose, a dynamic programming algorithm was also developed, allowing the identification of worst-case scenarios in polynomial time. Experiments on a set of literature instances confirm the efficacy of our approach, including a case study that shows little overhead in the expected solution value of obtained robust solutions.

An Autonomous Vehicle (AV) is believed to be the next generation transport that can enhance safety and efficiency for smart mobility. In an AV-based public transportation system, the full autonomy of AVs enables high-efficiency transport services and the potential ride-sharing feature of AV system enhances the utilization. The system manages a fleet of AVs, determines their assignments to transport requests, sends instructions concerning the optimized plans, and recommends the parking locations for the unoccupied AVs. The parking location of an empty AV is crucial in the sense that rebalancing AVs to areas with high potential service demand can curtail the unnecessary waiting time for passengers. As AVs are generally electric, proper parking locations can also facilitate vehicle-to-grid (V2G) support. In this paper, we propose a joint rebalancing and V2G coordination strategy for AV-based public transportation system. We formulate the problem as an integer linear program and propose a heuristic based on Genetic Algorithm and Model Predictive Control to solve the problem in low time complexity. Extensive experiments are performed with the real taxi service data from New York City. The formulated integer linear program is solved dynamically where each problem instance contains 3 to 5 AVs and 3 to 8 requests in 30s time interval. Compared with the transport system without rebalancing, the results show that the coordination strategy is efficient and effective in reducing unnecessary waiting time for passengers while satisfying V2G support. Compared to computational time with the standard solver, the proposed heuristic dramatically reduces the computational time.

In this study, we propose an efficient optimization algorithm that is a hybrid of the iterated greedy and simulated annealing algorithms (hereinafter, referred to as IGSA) to solve the flexible job shop scheduling problem with crane transportation processes (CFJSP). Two objectives are simultaneously considered, namely, the minimization of the maximum completion time and the energy consumptions during machine processing and crane transportation. Different from the methods in the literature, crane lift operations have been investigated for the first time to consider the processing time and energy consumptions involved during the crane lift process. The IGSA algorithm is then developed to solve the CFJSPs considered. In the proposed IGSA algorithm, first, each solution is represented by a 2-D vector, where one vector represents the scheduling sequence and the other vector shows the assignment of machines. Subsequently, an improved construction heuristic considering the problem features is proposed, which can decrease the number of replicated insertion positions for the destruction operations. Furthermore, to balance the exploration abilities and time complexity of the proposed algorithm, a problem-specific exploration heuristic is developed. Finally, a set of randomly generated instances based on realistic industrial processes is tested. Through comprehensive computational comparisons and statistical analyses, the highly effective performance of the proposed algorithm is favorably compared against several efficient algorithms.

In the multi-access edge computing environment, app vendors deploy their services and applications at the network edges, and edge users offload their computation tasks to edge servers. We study the user-perceived delay-aware service placement and user-allocation problem in edge environment. We model the MEC-enabled network, where the user-perceived delay consists of computing delay and transmission delay. The total cost in the offloading system is defined as the sum of service placement, edge server usage and energy consumption cost, and we need to minimize the total cost by determining the overall service-placing decision and user-allocation decision, while guaranteeing that the user-perceived delay requirement of each user is fulfilled. Our considered problem is formulated as a Mixed Integer Linear Programming problem, and we prove its NP-hardness. Due to the intractability of the considered problem, we propose a LOCal-search based algorithm for USer-perceived delay-aware service placement and user-allocation in edge environment, named LOCUS, which starts with a feasible solution and then repeatedly reduces the total cost by performing local-search steps. After that, we analyze the time complexity of LOCUS and prove that it achieves provable guaranteed performance. Finally, we compare LOCUS with other existing methods and show its good performance through experiments.

The space-air-ground integrated network (SAGIN) related issues are attractive in the sixth generation (6G) technologies, which facilitate the global coverage and seamless service. The cooperation of high altitude platforms (HAPs) and low earth orbit (LEO) satellites provides the remote area users with comprehensive coverage and service. In this work, we consider the cooperation of HAPs and LEO satellites in SAGIN to serve terrestrial users in the remote area for data collection and transmission. To deal with the periodical motion of LEO satellites, we employ the time expanding graph (TEG) to represent the multiple resources in SAGIN and depict task flow transmission processes. Based on TEG, we aim to maximize the total data received by the ground data processing center in a time horizon, considering multiple resource constraints and flow restrictions. The original problem is formulated in the form of mixed integer linear programming, which is intractable to obtain the optimal solution by brute-force searching. To alleviate this intractability, we propose the Benders decomposition based algorithm to obtain the optimal solution within an acceptable time complexity via iterations between the master problem and subproblem. Moreover, to further expedite the solution in large-scale systems, an acceleration algorithm is proposed by handling the master problem with an approximation algorithm and the subproblem with a unit-flow based algorithm. Finally, simulations are conducted and the numerical results verify the efficiency of the proposed algorithms, and the effects of various network parameters are analyzed as well.