Search

Protein-protein interaction (PPI) network alignment is a canonical operation to transfer biological knowledge among species. The alignment of PPI-networks has many applications, such as the prediction of protein function, detection of conserved network motifs, and the reconstruction of species’ phylogenetic relationships. A good multiple-network alignment (MNA), by considering the data related to several species, provides a deep understanding of biological networks and system-level cellular processes. With the massive amounts of available PPI data and the increasing number of known PPI networks, the problem of MNA is gaining more attention in the systems-biology studies. In this paper, we introduce a new scalable and accurate algorithm, called MPGM, for aligning multiple networks. The MPGM algorithm has two main steps: (i) SeedGeneration and (ii) MultiplePercolation. In the first step, to generate an initial set of seed tuples, the SeedGeneration algorithm uses only protein sequence similarities. In the second step, to align remaining unmatched nodes, the MultiplePercolation algorithm uses network structures and the seed tuples generated from the first step. We show that, with respect to different evaluation criteria, MPGM outperforms the other state-of-the-art algorithms. In addition, we guarantee the performance of MPGM under certain classes of network models. We introduce a sampling-based stochastic model for generating $k$ k correlated networks. We prove that for this model if a sufficient number of seed tuples are available, the MultiplePercolation algorithm correctly aligns almost all the nodes. Our theoretical results are supported by experimental evaluations over synthetic networks. [ABSTRACT FROM AUTHOR]

This paper considers a two‐agent scheduling problem with linear resource‐dependent processing times, in which each agent has a set of jobs that compete with that of the other agent for the use of a common processing machine, and each agent aims to minimize the weighted number of its tardy jobs. To meet the due date requirements of the jobs of the two agents, additional amounts of a common resource, which may be in discrete or continuous quantities, can be allocated to the processing of the jobs to compress their processing durations. The actual processing time of a job is a linear function of the amount of the resource allocated to it. The objective is to determine the optimal job sequence and resource allocation strategy so as to minimize the weighted number of tardy jobs of one agent, while keeping the weighted number of tardy jobs of the other agent, and the total resource consumption cost within their respective predetermined limits. It is shown that the problem is NP‐hard in the ordinary sense, and there does not exist a polynomial‐time approximation algorithm with performance ratio unless P=NP; however it admits a relaxed fully polynomial time approximation scheme. A proximal bundle algorithm based on Lagrangian relaxation is also presented to solve the problem approximately. To speed up convergence and produce sharp bounds, enhancement strategies including the design of a Tabu search algorithm and integration of a Lagrangian recovery heuristic into the algorithm are devised. Extensive numerical studies are conducted to assess the effectiveness and efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Standard quadratic optimization problems (StQPs) are NP-hard in computational complexity theory when the matrix is indefinite. This paper describes an approximate algorithm of finding inner optimal values of StQPs. The approximate algorithm fuzzifies variable x ∈ Rn with normalized possibility distributions and simplifies the solving of StQPs. The approximation ratio is discussed and determined. Numerical results show that (1) the new algorithm achieves higher accuracy than the semidefinite programming method and linear programming approximation method; (2) the novel algorithm consumes less than one out of fourth computational time that is consumed by linear programming approximation method; (3) the computational time of the new algorithm does not correlate with the matrix densities whereas the computational times of the branch-and-bound and heuristic algorithms do. [ABSTRACT FROM AUTHOR]

Recent years have witnessed increasingly more uses of Unmanned Aerial Vehicle (UAV) swarms for rapidly providing wireless coverage to ground users. Each UAV is constrained in its energy storage and wireless coverage, and it consumes most energy on flying to the top of the target area, thus leaving limited leftover energy for hovering at its deployed position and keeping wireless coverage. The literature largely overlooks the sustainability issues of deploying UAV swarm and the UAV-to-UAV cooperation, and we aim to maximize the minimum leftover energy storage among all the UAVs after their deployment. Our new energy-saving deployment problem captures that each UAV's wireless coverage is adjustable by its service altitude, and also takes the no-fly-zone (NFZ) constraint into account. We show that a UAV with larger initial energy storage in the UAV swarm should be deployed further away from the UAV station, and we propose an optimal energy-saving deployment algorithm by jointly balancing heterogeneous UAVs’ flying distances on the ground and final service altitudes in the sky. When n UAVs with different initial energy storages are dispatched from different initial locations, we prove this problem is NP-hard in general by reduction from partition problem. Despite of this, we propose to preserve the UAVs’ location order and successfully design an approximation algorithm of complexity n log 1/ε to arbitrarily approach the optimum with error ε. Inspiring by this proposed (1−ε)-approximation algorithm, we present a heuristic algorithm to solve the general case by balancing the efficiency and computation complexity well. [ABSTRACT FROM AUTHOR]

In this paper, a novel event-sampled robust optimal controller is proposed for a class of continuous-time constrained-input nonlinear systems with unknown dynamics. In order to solve the robust optimal control problem, an online data-driven identifier is established to construct the system dynamics, and an event-sampled critic-only adaptive dynamic programming method is developed to replace the conventional time-driven actor–critic structure. The designed online identification method runs during the solving process and is not applied as a priori part for the solutions, which simplifies the architecture and reduces computational load. The proposed robust optimal control algorithm tunes the parameters of critic-only neural network (NN) by event-triggering condition and runs in a plug-n-play framework without system functions, where fewer transmissions and less computation are required as all the measurements received simultaneously. Based on the novel design, the stability of system and the convergence of critic NN are demonstrated by Lyapunov theory, where the state is asymptotically stable and weight error is guaranteed to be uniformly ultimately bounded. Finally, the applications in a basic nonlinear system and the complex rotational–translational actuator problem demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

With the rapid development of Metro, it has aroused more attention to its energy efficiency. The regenerative energy is a kind of energy generated by a braking train, which can be used by other trains nearby. Due to the application of regenerative braking and automatic train operation function, more and more studies focus on using regenerative energy by optimal train control. To maximize the utilization of regenerative energy for a couple of trains, we formulate a model and design an algorithm for maximizing the utilization of regenerative energy (MURE) by using the proposed approximate dynamic programming (ADP) approach to adjust the speed curve of the accelerating train. Then, we discuss three approximation methods for the proposed ADP-based approach such as rollout method, interpolation method, and neural network. The rollout algorithm could improve the basic policy for train control with carefully designing. The function approximation method using interpolation could further decrease the energy consumption with assuring punctuality. The neural network approximation usually cannot realize the effect superior to the interpolation strategy due to its complex structure, and it needs more computation time. Finally, the analysis of regenerative energy utilization is given by implementing the numerical experiments with field data from the Yizhuang line, Beijing subway. The numerical results show its effectiveness and stability. [ABSTRACT FROM AUTHOR]

The main reason of the extensive usage of the fuzzy systems in many branches of science is their approximation ability. In this paper, an interval type-3 fuzzy system (IT3FS) is proposed. The uncertainty modeling capability of the proposed IT3FS is improved in contrast to type-1 and type-2 fuzzy systems (T1FS and T2FS). Because in the proposed IT3FS, the membership is defined as an interval type-2 fuzzy set, whereas in T1FS and T2FS, the membership is crisp value and type-1 fuzzy set, respectively. An online fractional-order learning algorithm is given to optimize the consequent parameters of the IT3FS. The stability of the learning algorithm is proved by utilizing the Lyapunov method. The validity of the proposed fuzzy system is illustrated by both simulation and the experimental studies. It is shown that the proposed fuzzy system and associated learning algorithm result in better approximation performance in comparison with the other well-known approaches. [ABSTRACT FROM AUTHOR]

We investigate variants of Lloyd's heuristic for clustering high-dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order to suggest improvements in its application. We propose and justify a clusterability criterion for data sets.We present variants of Lloyd's heuristic that quickly lead to provably near-optimal clustering solutions when applied to well-clusterable instances. This is the first performance guarantee for a variant of Lloyd's heuristic. The provision of a guarantee on output quality does not come at the expense of speed: some of our algorithms are candidates for being faster in practice than currently used variants of Lloyd's method. In addition, our other algorithms are faster on well-clusterable instances than recently proposed approximation algorithms, while maintaining similar guarantees on clustering quality. Our main algorithmic contribution is a novel probabilistic seeding process for the starting configuration of a Lloyd-type iteration. [ABSTRACT FROM AUTHOR]

The problem we study in this paper arises from the washing step of hospital sterilisation services. Washers in the washing step are capable of handling more than one medical device set as long as their capacity is not exceeded. The medical device set sizes and arrival times to the sterilisation service may be different, but they all have the same washing duration. Thus, we model the washing step as a batch scheduling problem where medical device sets are treated as jobs with non-identical sizes and release dates, but equal processing times. The main findings we present in this paper are the following. First, we study two special cases for which polynomial algorithms are presented. We then develop a 2-approximation algorithm for the general problem. Finally, we develop a MILP model and compare it with another MILP model from the literature. Computational results show that our MILP model outperforms the model from the literature. [ABSTRACT FROM PUBLISHER]

It is recognized that existing multi-scale exposure fusion algorithms can be improved using edge-preserving smoothing techniques. However, the complexity of edge-preserving smoothing-based multi-scale exposure fusion is an issue for mobile devices. In this paper, a simpler multi-scale exposure fusion algorithm is designed in YUV color space. The proposed algorithm can preserve details in the brightest and darkest regions of a high dynamic range (HDR) scene and the edge-preserving smoothing-based multi-scale exposure fusion algorithm while avoiding color distortion from appearing in the fused image. The complexity of the proposed algorithm is about half of the edge-preserving smoothing-based multi-scale exposure fusion algorithm. The proposed algorithm is thus friendlier to the smartphones than the edge-preserving smoothing-based multi-scale exposure fusion algorithm. In addition, a simple detail-enhancement component is proposed to enhance fine details of fused images. The experimental results show that the proposed component can be adopted to produce an enhanced image with visibly enhanced fine details and a higher MEF-SSIM value. This is impossible for existing detail enhancement components. Clearly, the component is attractive for PC-based applications. [ABSTRACT FROM AUTHOR]

Next-generation sequencing has revolutionized the field of genomics by producing accurate, rapid and cost-effective genome analysis with the use of high throughput sequencing technologies. This has intensified the need for accurate and performance efficient genome assemblers to assemble a large set of short reads produced by next-generation sequencing technology. Genome assembly is an NP-hard problem that is computationally challenging. Therefore, the current methods that rely on heuristic and approximation algorithms to assemble genomes prevent them from arriving at the most accurate solution. This paper presents a novel approach by gamifying whole-genome shotgun assembly from next-generation sequencing data; we present "Geno", a human-computing game designed with the aim of improving the accuracy of whole-genome shotgun assembly. We evaluate the feasibility of crowdsourcing the problem of whole-genome shotgun assembly by breaking the problem into small subtasks. The evaluation results, for single-cell Escherichia coli K-12 substr. MG1655 with a read length of 25 bp that produced 144,867 game instances of mean 25 sequences per instance at 40x coverage indicate the feasibility of sub-tasking the problem of genome assembly to be solved using crowdsourcing. [ABSTRACT FROM AUTHOR]

This article studies the efficacy of the Metropolis algorithm for the minimum-weight codeword problem. The input is a linear code $C$ given by its generator matrix and our task is to compute a nonzero codeword in the code $C$ of least weight. In particular, we study the Metropolis algorithm on two possible search spaces for the problem: 1) the codeword space and 2) the generator space. The former is the space of all codewords of the input code and is the most natural one to use and hence has been used in previous work on this problem. The latter is the space of all generator matrices of the input code and is studied for the first time in this article. In this article, we show that for an appropriately chosen temperature parameter the Metropolis algorithm mixes rapidly when either of the search spaces mentioned above are used. Experimentally, we demonstrate that the Metropolis algorithm performs favorably when compared to previous attempts. When using the generator space, the Metropolis algorithm is able to outperform the previous algorithms in most of the cases. We have also provided both theoretical and experimental justification to show why the generator space is a worthwhile search space to use for this problem. [ABSTRACT FROM AUTHOR]

Cyber-epidemics, the widespread of fake news or propaganda through social media, can cause devastating economic and political consequences. A common countermeasure against cyber-epidemics is to disable a small subset of suspected social connections or accounts to effectively contain the epidemics. An example is the recent shutdown of 125,000 ISIS-related Twitter accounts. Despite many proposed methods to identify such a subset, none are scalable enough to provide high-quality solutions in nowadays’ billion-size networks. To this end, we investigate the Spread Interdiction problems that seek the most effective links (or nodes) for removal under the well-known Linear Threshold model. We propose novel CPU-GPU methods that scale to networks with billions of edges, yet possess rigorous theoretical guarantee on the solution quality. At the core of our methods is an $O(1)$ O (1) -space out-of-core algorithm to generate a new type of random walks, called Hitting Self-avoiding Walks ($\mathsf{HSAW}$ HSAW s). Such a low memory requirement enables handling of big networks and, more importantly, hiding latency via scheduling of millions of threads on GPUs. Comprehensive experiments on real-world networks show that our algorithms provide much higher quality solutions and are several orders of magnitude faster than the state-of-the art. Comparing to the (single-core) CPU counterpart, our GPU implementations achieve significant speedup factors up to 177x on a single GPU and 338x on a GPU pair. [ABSTRACT FROM AUTHOR]

RFID-based stocktaking uses RFID technology to verify the presence of objects in a region e.g., a warehouse or a library, compared with an inventory list. The existing approaches for this purpose assume that the number of missing tags is small. This is not true in some cases. For example, for a handheld RFID reader, only the objects in a larger region (e.g., the warehouse) rather than in its interrogation region can be known as the inventory list, and hence many tags in the list are regarded as missing. The missing objects significantly increase the time required for stocktaking. In this paper, we propose an algorithm called CLS (Coarse-grained inventory list based stocktaking) to solve this problem. CLS enables multiple missing objects to hash to a single time slot and thus verifies them together. CLS also improves the existing approaches by utilizing more kinds of RFID collisions and reducing approximately one-fourth of the amount of data sent by the reader. Moreover, we observe that the missing rate constantly changes during the identification because some of tags are verified present or absent, which affects time efficiency; accordingly, we propose a hybrid stocktaking algorithm called DLS (Dynamic inventory list based stocktaking) to adapt to such changes for the first time. According to the results of extensive simulations, when the inventory list is 20 times that of actually present tags, the execution time of our approach is 36.3 percent that of the best existing algorithm. [ABSTRACT FROM AUTHOR]

This brief studies an energy management (EM) problem with unknown dynamics of consumer appliances. A two-level optimization model is established between the utility company and the consumers. In this model, the utility company maximizes its profit by setting the electricity price, and the consumers respond to the price by regulating power usage to minimize their costs. The aforementioned process is performed in multiple stages. In each stage, the consumer response is formulated as a constrained optimization problem, which can be transformed into an unconstrained optimization problem using the penalty function method, and then an extremum seeking control (ESC) algorithm is developed to search for the quasi-optimal power consumption of the consumers. The ESC algorithm has noncontinuous first and second derivatives with respect to the variables. We propose an approximation method to make the ESC algorithm continuous and prove that the algorithm is semiglobally practically asymptotically (SPA) stable. After the consumer response in the same stage, the utility company updates the electricity price by the particle swarm optimization (PSO) algorithm. Then, we give an EM algorithm that integrates the ESC with PSO. In simulations, the algorithm is applied to achieve EM of heating, ventilation, and air conditioning (HVAC) systems, and the results show that the algorithm can converge to a neighborhood of the optimal solution and reduce the peak load and daily load. [ABSTRACT FROM AUTHOR]

Inertial navigation computation is to acquire the attitude, velocity, and position information of a moving body by integrating inertial measurements from gyroscopes and accelerometers. Over half a century has witnessed great efforts in coping with the motion noncommutativity errors to accurately compute the navigation information as far as possible, so as not to compromise the quality measurements of inertial sensors. Highly dynamic applications and the forthcoming cold-atom precision inertial navigation systems demand for even more accurate inertial navigation computation. The paper gives birth to an inertial navigation algorithm to fulfill that demand, named the iNavFIter, which is based on a brand-new framework of functional iterative integration and Chebyshev polynomials. Remarkably, the proposed iNavFIter reduces the noncommutativity errors to almost machine precision, namely, the coning/sculling/scrolling errors that have perplexed the navigation community for long. Numerical results are provided to demonstrate its accuracy superiority over the state-of-the-art inertial navigation algorithms at affordable computation cost. [ABSTRACT FROM AUTHOR]

The analysis of the dynamic behavior of cells in time-lapse microscopy sequences requires the development of reliable and automatic tracking methods capable of estimating individual cell states and delineating the lineage trees corresponding to the tracks. In this paper, we propose a novel approach, i.e., an ant colony inspired multi-Bernoulli filter, to handle the tracking of a collection of cells within which mitosis, morphological change and erratic dynamics occur. The proposed technique treats each ant colony as an independent one in an ant society, and the existence probability of an ant colony and its density distribution approximation are derived from the individual pheromone field and the corresponding heuristic information for the approximation to the multi-Bernoulli parameters. To effectively guide ant foraging between consecutive frames, a dual prediction mechanism is proposed for the ant colony and its pheromone field. The algorithm performance is tested on challenging datasets with varying population density, frequent cell mitosis and uneven motion over time, demonstrating that the algorithm outperforms recently reported approaches. [ABSTRACT FROM AUTHOR]

The proliferation of innovative mobile services such as augmented reality, networked gaming, and autonomous driving has spurred a growing need for low-latency access to computing resources that cannot be met solely by existing centralized cloud systems. Mobile Edge Computing (MEC) is expected to be an effective solution to meet the demand for low-latency services by enabling the execution of computing tasks at the network edge, in proximity to the end-users. While a number of recent studies have addressed the problem of determining the execution of service tasks and the routing of user requests to corresponding edge servers, the focus has primarily been on the efficient utilization of computing resources, neglecting the fact that non-trivial amounts of data need to be pre-stored to enable service execution, and that many emerging services exhibit asymmetric bandwidth requirements. To fill this gap, we study the joint optimization of service placement and request routing in dense MEC networks with multidimensional constraints. We show that this problem generalizes several well-known placement and routing problems and propose an algorithm that achieves close-to-optimal performance using a randomized rounding technique. Evaluation results demonstrate that our approach can effectively utilize available storage, computation, and communication resources to maximize the number of requests served by low-latency edge cloud servers. [ABSTRACT FROM AUTHOR]

Growing expressiveness of services increases the size of a manageable state at the network data plane. A service policy is an ordered set of classification patterns (classes) with actions; the same class can appear in multiple policies. Previous studies mostly concentrated on efficient representations of a single policy instance. In this work, we study space efficiency of multiple policies, cutting down a classifier size by sharing instances of classes between policies that contain them. In this paper we identify conditions for such sharing, propose efficient algorithms and analyze them analytically. The proposed representations can be deployed transparently on existing packet processing engines. Our results are supported by extensive evaluations. [ABSTRACT FROM AUTHOR]

A theoretical performance analysis of the $(\mu /\mu _{I},\lambda) - \sigma $ -self-adaptation evolution strategy ($\sigma $ SA-ES) is presented considering a conically constrained problem. Infeasible offspring are repaired using projection onto the boundary of the feasibility region. Closed-form approximations are used for the one-generation progress of the evolution strategy. Approximate deterministic evolution equations are formulated for analyzing the strategy’s dynamics. By iterating the evolution equations with the approximate one-generation expressions, the evolution strategy’s dynamics can be predicted. The derived theoretical results are compared to experiments for assessing the approximation quality. It is shown that in the steady state the $(\mu /\mu _{I},\lambda) - \sigma $ SA-ES exhibits a performance as if the ES were optimizing a sphere model. Unlike the nonrecombinative $(1,\lambda)$ -ES, the parental steady state behavior does not evolve on the cone boundary but stays away from the boundary to a certain extent. [ABSTRACT FROM AUTHOR]

Network function virtualization (NFV) fosters innovation in the networking field and reduces the complexity involved in managing modern-day conventional networks. Via NFV, the provisioning of a network service becomes more agile, whereby virtual network functions can be instantiated on commodity servers and data centers on demand. Network functions can be either mandatory or best-effort. The former type is strictly necessary for the correctness of a network service, whereas the latter is preferrable yet not necessary. In this paper, we study the online provisioning of NFV-enabled network services. We consider both unicast and multicast NFV-enabled services with multiple mandatory and best-effort NF instances. We propose a primal-dual based online approximation algorithm that allocates both processing and transmission resources to maximize a profit function, subject to resource constraints on physical links and NFV nodes. The online algorithm resembles a joint admission mechanism and an online composition, routing and NF placement framework. The online algorithm is derived from an offline formulation through a primal-dual based analysis. Such analysis offers direct insights and a fundamental understanding on the nature of the profit-maximization problem for NFV-enabled services with multiple resource types. [ABSTRACT FROM AUTHOR]

The introduction of Smart Grid systems has raised many new security concerns. If an attacker can compromise components of the Smart Grid communication network, they can fabricate malicious messages to interfere with the grid and ultimately cause outages. One method to address this concern is to conduct network audits by logging network traffic into dedicated servers in order to detect malicious messages. This may be done by using switches’ or routers’ ability to duplicate packets they receive with minimal overhead. The question of how many and which switches/routers to select for this task naturally follows. This paper considers the problem of finding minimal set of routers/switches in a Smart Grid communication network to use for auditing traffic. Accordingly, we devise three algorithms: the first one is highly effective with an approximation ratio of $(2+\theta)(\ln |V| + 1)$. The second method is a highly scalable algorithm with a constant performance ratio. And the last one is a dynamic algorithm which can efficiently update its solution in response to changes to critical traffic. We experimentally evaluate our solutions and compare them to an optimal Integer Programming formulation, finding that they perform near-optimally and significantly outperform a simple heuristic in all cases. [ABSTRACT FROM AUTHOR]

Diffusion on complex networks is often modeled as a stochastic process. Yet, recent work on strategic diffusion emphasizes the decision power of agents [1] and treats diffusion as a strategic problem. Here we study the computational aspects of strategic diffusion, i.e. , finding the optimal sequence of nodes to activate a network in the minimum time. We prove that finding an optimal solution to this problem is NP-complete in a general case. To overcome this computational difficulty, we present an algorithm to compute an optimal solution based on a dynamic programming technique. We also show that the problem is fixed parameter-tractable when parametrized by the product of the treewidth and maximum degree. We analyze the possibility of developing an efficient approximation algorithm and show that two heuristic algorithms proposed so far cannot have better than a logarithmic approximation guarantee. Finally, we prove that the problem does not admit better than a logarithmic approximation, unless P=NP. [ABSTRACT FROM AUTHOR]

Dense subgraph discovery has proven useful in various applications of temporal networks. We focus on a special class of temporal networks whose nodes and edges are kept fixed, but edge weights regularly vary with timestamps. However, finding dense subgraphs in temporal networks is non-trivial, and its state of the art solution uses a filter-and-verification framework that is not scalable on large temporal networks. In this study, we propose a highly efficient approach to finding dense subgraphs in large temporal networks with $T$ T timestamps. (1) We first develop a statistics-driven approach that employs hidden statistics to identifying $k$ k time intervals, instead of $T(T+1)/2$ T (T + 1) / 2 ones ($k$ k is typically much smaller than $T$ T ), which strikes a balance between quality and efficiency. (2) After proving that the problem has no constant factor approximation algorithms, we design better heuristic algorithms to attack the problem, by connecting finding dense subgraphs with a variant of the Prize Collecting Steiner Tree problem. (3) Finally, we have conducted an extensive experimental study to verify that our approach is both effective and efficient. [ABSTRACT FROM AUTHOR]

The problem of quickest detection of dynamic events in networks is studied. At some unknown time, an event occurs, and a number of nodes in the network are affected by the event, in that they undergo a change in the statistics of their observations. It is assumed that the event is dynamic, in that it can propagate along the edges in the network, and affect more and more nodes with time. The event propagation dynamics is assumed to be unknown. The goal is to design a sequential algorithm that can detect a “significant” event, i.e., when the event has affected no fewer than $\eta $ nodes, as quickly as possible, while controlling the false alarm rate. Fully connected networks are studied first, and the results are then extended to arbitrarily connected networks. The designed algorithms are shown to be adaptive to the unknown propagation dynamics, and their first-order asymptotic optimality is demonstrated as the false alarm rate goes to zero. The algorithms can be implemented with linear computational complexity in the network size at each time step, which is critical for online implementation. Numerical simulations are provided to validate the theoretical results. [ABSTRACT FROM AUTHOR]

Mesh segmentation is a process of partitioning a mesh model into meaningful parts — a fundamental problem in various disciplines. This paper introduces a novel mesh segmentation method inspired by sparsity pursuit. Based on the local geometric and topological information of a given mesh, we build a Laplacian matrix whose Fiedler vector is used to characterize the uniformity among elements of the same segment. By analyzing the Fiedler vector, we reformulate the mesh segmentation problem as a $\ell _0$ ℓ 0 gradient minimization problem. To solve this problem efficiently, we adopt a coarse-to-fine strategy. A fast heuristic algorithm is first devised to find a rational coarse segmentation, and then an optimization algorithm based on the alternating direction method of multiplier (ADMM) is proposed to refine the segment boundaries within their local regions. To extract the inherent hierarchical structure of the given mesh, our method performs segmentation in a recursive way. Experimental results demonstrate that the presented method outperforms the state-of-the-art segmentation methods when evaluated on the Princeton Segmentation Benchmark, the LIFL/LIRIS Segmentation Benchmark and a number of other complex meshes. [ABSTRACT FROM AUTHOR]

In this article, the dynamic economic dispatch (DED) problem for smart grid is solved under the assumption that no knowledge of the mathematical formulation of the actual generation cost functions is available. The objective of the DED problem is to find the optimal power output of each unit at each time so as to minimize the total generation cost. To address the lack of a priori knowledge, a new distributed reinforcement learning optimization algorithm is proposed. The algorithm combines the state-action-value function approximation with a distributed optimization based on multiplier splitting. Theoretical analysis of the proposed algorithm is provided to prove the feasibility of the algorithm, and several case studies are presented to demonstrate its effectiveness. [ABSTRACT FROM AUTHOR]

A chance-constrained optimization problem involves constraints with random data that can be violated with probability bounded from above by a prespecified small risk parameter. Such constraints are used to model reliability requirements in a variety of application areas, such as finance and energy. Except under very special conditions, chance-constrained problems are extremely difficult. In "Bicriteria Approximation of Chance-Constrained Covering Problems," Xie and Ahmed study a class of chance-constrained covering problems. They propose a bicriteria approximation scheme. Their scheme finds a solution whose violation probability may be larger than but is within a constant factor of the specified risk parameter and whose objective value is within a constant factor of the true optimal value. They extend the approximation results to a setting in which the underlying distribution of the constraint data are not known; that is, they consider distributionally robust chance-constrained covering problems and provide bicriteria approximation results. A chance-constrained optimization problem involves constraints with random data that can be violated with probability bounded from above by a prespecified small risk parameter. Such constraints are used to model reliability requirements in a variety of application areas, such as finance, energy, service, and manufacturing. Except under very special conditions, chance-constrained problems are extremely difficult. There has been a great deal of elegant work on developing tractable approximations of chance constraints. Unfortunately, none of these approaches comes with a constant factor approximation guarantee. We show that such a guarantee is impossible by proving an inapproximability result. By contrast, for a large class of chance-constrained covering problems, we propose a bicriteria approximation scheme. Our scheme finds a solution whose violation probability may be larger than but is within a constant factor of the specified risk parameter and whose objective value is within a constant factor of the true optimal value. Key to our developments is the construction of a tractable convex relaxation of a chance-constrained problem and an appropriate scaling of a solution to this relaxation. We extend our approximation results to the setting in which the underlying distribution of the constraint data is not known. That is, we consider distributionally robust chance-constrained covering problems with convex moment and Wasserstein ambiguity sets and provide bicriteria approximation results. [ABSTRACT FROM AUTHOR]

In view of the prevalence of dynamic uncertainties, we study the robust policy learning control of nonlinear plants in this paper. The auxiliary system and policy learning techniques are integrated to accomplish robust stabilization of mismatched nonlinear systems. First, the uncertain dynamics is handled by proper transformation, so as to construct an optimal regulation problem with respect to an augmented auxiliary system. Then, the integral policy iteration algorithm is employed for optimal control design without requiring system dynamics. The equivalence results involved in problem transformation and algorithm improvement are analyzed. After that, the actor-critic structure is adopted with least squares implementation for approximate calculation. Finally, the experimental simulation with an application to a power system is provided, which demonstrates the validity of the adaptive robust control strategy. The present policy learning algorithm does not rely on whole information of system dynamics and the established robust control technique is applicable for nonlinear plants subjected to mismatched uncertainties. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of operating a battery storage unit in a home with a rooftop solar photovoltaic (PV) system so as to minimize expected long-run electricity costs under uncertain electricity usage, PV generation, and electricity prices. Solving this dynamic program using standard techniques is computationally burdensome, and is often complicated by the difficulty of estimating conditional distributions from sparse data. To overcome these challenges, we implement a data-driven dynamic programming (DDP) algorithm that uses historical data observations to generate empirical conditional distributions and approximate the cost-to-go function. Then, we formulate two robust data-driven dynamic programming (RDDP) algorithms that consider the worst-case expected cost over a set of conditional distributions centered at the empirical distribution, and within a given Chi-square or Wasserstein distance, respectively. We test our algorithms using data from homes with rooftop PV in Austin, Texas. Numerical results reveal that DDP and RDDP outperform common existing methods with acceptable computational effort. Finally, we show that implementation of these superior operational algorithms significantly raises the break-even battery cost under which a homeowner is incentivized to invest in a residential battery rather than participate in a feed-in tariff or net energy metering program. [ABSTRACT FROM AUTHOR]

This paper studies the problem of user association, deadline scheduling and channel allocation in dense cellular networks with energy harvesting base stations. The objective is to maximize the number of associated and scheduled users while allocating the available channels to the users and respecting the energy and deadline constraints. First, the computational complexity of this problem is characterized by studying its NP-hardness in different cases. Next, efficient algorithms are proposed in each case. The case of single channel and single base station is solved by proposing polynomial-time optimal algorithms. The case of single channel and multiple base stations is solved by proposing an efficient constant-factor approximation algorithm. The case of multiple channels is solved by proposing efficient heuristic algorithms. Our theoretical analysis are supplemented by simulation results to illustrate the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

We study the problem of maximizing the number of spanning trees in a connected graph with $n$ vertices and $m$ edges, by adding at most $k$ edges from a given set of $q$ candidate edges, a problem that has applications in many domains. We give both algorithmic and hardness results for this problem: 1) We give a greedy algorithm that obtains an approximation ratio of $(1 - 1/e - \epsilon)$ in the exponent of the number of spanning trees for any $\epsilon > 0$ in time $\widetilde {O}(m \epsilon ^{-1} + (n + q) \epsilon ^{-3})$ , where $\widetilde {O}(\cdot)$ hides ${\mathrm{ poly}}\log (n)$ factors. Our running time is optimal with respect to the input size, up to logarithmic factors, and improves on the $O(n^{3})$ running time of the previous proposed greedy algorithm with an approximation ratio $(1 - 1/e)$ in the exponent. Notably, the independence of our running time of $k$ is novel, compared to conventional top- $k$ selections on graphs that usually run in $\Omega (mk)$ time. 2) We show the exponential inapproximability of this problem by proving that there exists a constant $c > 0$ such that it is NP-hard to approximate the optimum number of spanning trees in the exponent within $(1 - c)$. [ABSTRACT FROM AUTHOR]

In an offload-capable Long Term Evolution (LTE)- Wireless Fidelity (WiFi) Heterogeneous Network (HetNet), we consider the problem of maximization of the total system throughput under voice user blocking probability constraint. The optimal policy is threshold in nature. However, computation of optimal policy requires the knowledge of the statistics of system dynamics, viz., arrival processes of voice and data users, which may be difficult to obtain in reality. Motivated by the Post-Decision State (PDS) framework to learn the optimal policy under unknown statistics of system dynamics, we propose, in this paper, an online Radio Access Technology (RAT) selection algorithm using Relative Value Iteration Algorithm (RVIA). However, the convergence speed of this algorithm can be further improved if the underlying threshold structure of the optimal policy can be exploited. To this end, we propose a novel structure-aware online RAT selection algorithm which reduces the feasible policy space, thereby offering lesser storage and computational complexity and faster convergence. This algorithm provides a novel framework for designing online learning algorithms for other problems and hence is of independent interest. We prove that both the algorithms converge to the optimal policy. Simulation results demonstrate that the proposed algorithms converge faster than a traditional scheme. Also, the proposed schemes perform better than other benchmark algorithms under realistic network scenarios. [ABSTRACT FROM AUTHOR]

Feature selection is an important task in machine learning that has two main objectives: 1) reducing dimensionality and 2) improving learning performance. Feature selection can be considered a multiobjective problem. However, it has its problematic characteristics, such as a highly discontinuous Pareto front, imbalance preferences, and partially conflicting objectives. These characteristics are not easy for existing evolutionary multiobjective optimization (EMO) algorithms. We propose a new decomposition approach with two mechanisms (static and dynamic) based on multiple reference points under the multiobjective evolutionary algorithm based on decomposition (MOEA/D) framework to address the above-mentioned difficulties of feature selection. The static mechanism alleviates the dependence of the decomposition on the Pareto front shape and the effect of the discontinuity. The dynamic one is able to detect regions in which the objectives are mostly conflicting, and allocates more computational resources to the detected regions. In comparison with other EMO algorithms on 12 different classification datasets, the proposed decomposition approach finds more diverse feature subsets with better performance in terms of hypervolume and inverted generational distance. The dynamic mechanism successfully identifies conflicting regions and further improves the approximation quality for the Pareto fronts. [ABSTRACT FROM AUTHOR]

Train marshalling is the process of reordering the railcars of a train in such a way that the railcars with the same destination appear consecutively in the final, reassembled train. The process takes place in the shunting yard by means of a number of classification tracks. In the train marshalling problem (TMP), the objective is to perform this rearrangement of the railcars with the use of as few classification tracks as possible. The problem has been shown to be NP-hard, and several exact and approximation algorithms have been developed for it. In this paper, we propose a novel exact dynamic programming (DP) algorithm for the TMP. The worst-case time complexity of this algorithm (which is exponential in the number of destinations and linear in the number of railcars) is lower than that of the best presently available algorithm for the problem, which is an inclusion–exclusion-based DP algorithm. In practice, the proposed algorithm can provide a substantially improved performance compared to its inclusion–exclusion-based counterpart, as demonstrated by the experimental results. [ABSTRACT FROM AUTHOR]

Signal recovery from unitarily invariant measurements is investigated in this paper. A message-passing algorithm is formulated on the basis of expectation propagation (EP). A rigorous analysis is presented for the dynamics of the algorithm in the large system limit, where both input and output dimensions tend to infinity while the compression rate is kept constant. The main result is the justification of state evolution (SE) equations conjectured by Ma and Ping. This result implies that the EP-based algorithm achieves the Bayes-optimal performance that was originally derived via a non-rigorous tool in statistical physics and proved partially in a recent paper, when the compression rate is larger than a threshold. The proof is based on an extension of a conventional conditioning technique for the standard Gaussian matrix to the case of the Haar matrix. [ABSTRACT FROM AUTHOR]

This paper studies the precedence-constrained task assignment problem for a team of heterogeneous vehicles to deliver packages to a set of dispersed customers subject to precedence constraints that specify which customers need to be visited before which other customers. A truck and a micro drone with complementary capabilities are employed where the truck is restricted to travel in a street network and the micro drone, restricted by its loading capacity and operation range, can fly from the truck to perform the last-mile package deliveries. The objective is to minimize the time to serve all the customers respecting every precedence constraint. The problem is shown to be NP-hard, and a lower bound on the optimal time to serve all the customers is constructed by using tools from graph theory. Then, integrating with a topological sorting technique, several heuristic task assignment algorithms are proposed to solve the task assignment problem. Numerical simulations show the superior performances of the proposed algorithms compared with popular genetic algorithms. Note to Practitioners—This paper presents several task assignment algorithms for the precedence-constrained package delivery for the team of a truck and a micro drone. The truck can carry the drone moving in a street network, while the drone completes the last-mile package deliveries. The practical contributions of this paper are fourfold. First, the precedence constraints on the ordering of the customers to be served are considered, which enables complex logistic scheduling for customers prioritized according to their urgency or importance. Second, the package delivery optimization problem is shown to be NP-hard, which clearly shows the need for creative approximation algorithms to solve the problem. Third, the constructed lower bound on the optimal time to serve all the customers helps to clarify for practitioners the limiting performance of a feasible solution. Fourth, the proposed task assignment algorithms are efficient and can be adapted for real scenarios. [ABSTRACT FROM AUTHOR]

We present three heuristics-Sliding Window, Look Ahead, and Iterative Sliding Window-to improve solutions for the Sorting Signed Permutations by Reversals and Transpositions Problem. We investigate the classical version of the problem as well as versions restricted to prefix and prefix or suffix operations. To assess the heuristics based on its improvement, we implemented algorithms described in the literature to provide initial solutions. Although we have a limited number of problems, these heuristics can be applied to many others within the area of genome rearrangement. When time is a crucial factor, Sliding Window is a better choice because it runs in linear time. If the quality of the solution is a priority, Look Ahead should be preferred. Iterative Sliding Window is the most flexible heuristic and allows us to find a trade-off for specific scenarios where running time and solution quality are relevant. [ABSTRACT FROM AUTHOR]

Location awareness is becoming essential for various wireless applications, and cooperation among nodes is highly beneficial for localization performance. However, the existing cooperative localization (CL) algorithms may suffer from major performance loss when applied to the mobile environments with fast changing network topologies. In this paper, we extend the joint spatial and temporal cooperation (JSTC) model to the range-based localization problem. Based on mobility constraints and the maximum likelihood estimation (MLE) criterion, we formulate the CL problems in both centralized and distributed cases. Different from the conventional distributed CL problems, the proposed one takes the transmission delay and the cooperation among multi-hop nodes into account, which is more practical. Moreover, the performance limits of the considered problems are investigated by the Cramér-Rao lower bound (CRLB). Finally, these two problems are solved by the Sequential Quadratic Programming (SQP) algorithm. Both simulation and experiment results show that the extended JSTC model can effectively improve the localization reliability and accuracy. [ABSTRACT FROM AUTHOR]

Inspired by Nash game theory, a multiplayer mixed-zero-sum (MZS) nonlinear game considering both two situations [zero-sum and nonzero-sum (NZS) Nash games] is proposed in this paper. A synchronous reinforcement learning (RL) scheme based on the identifier-critic structure is developed to learn the Nash equilibrium solution of the proposed MZS game. First, the MZS game formulation is presented, where the performance indexes for players 1 to ${N}$ − 1 and ${N}$ NZS Nash game are presented, and another performance index for players ${N}$ and ${N}$ + 1 zero-sum game is presented, such that player ${N}$ cooperates with players 1 to ${N}$ − 1, while competes with player ${N}$ + 1, which leads to a Nash equilibrium of all players. A single-layer neural network (NN) is then used to approximate the unknown dynamics of the nonlinear game system. Finally, an RL scheme based on NNs is developed to learn the optimal performance indexes, which can be used to produce the optimal control policy of every player such that Nash equilibrium can be obtained. Thus, the widely used actor NN in RL literature is not needed. To this end, a recently proposed adaptive law is used to estimate the unknown identifier coefficient vectors, and an improved adaptive law with the error performance index is further developed to update the critic coefficient vectors. Both linear and nonlinear simulations are presented to demonstrate the existence of Nash equilibrium for MZS game and performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

With the rapid growth of the Web scale, large scale search engines have to set up a huge number of machines to place the index files of the Web contents. The index files are normally divided into smaller index shards which are often replicated so that queries can be processed in parallel. We observe from real systems that the index shard replication strategy could have a significant impact on the resource usage. In this paper, we investigate the index shard replication problem with the goal of minimizing the resource usage in search engine datacenters. We consider both the offline version and online version of the problem, and formulate the problems as non-linear integer programming problems. We propose several heuristic algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using both synthetic data and real data from commercial search engines. The results demonstrate the effectiveness of the proposed algorithms. Our work also yields many insights about the impact of different input properties on the performance of each algorithm. We believe that this paper will provide valuable guidance to the design of the index shard replication strategy in practice. [ABSTRACT FROM AUTHOR]

Enterprise users at different geographic locations generate large-volume data that is stored at different geographic datacenters. These users may also perform big data analytics on the stored data to identify valuable information in order to make strategic decisions. However, it is well known that performing big data analytics on data in geographical-located datacenters usually is time-consuming and costly. In some delay-sensitive applications, the query result may become useless if answering a query takes too long time. Instead, sometimes users may only be interested in timely approximate rather than exact query results. When such approximate query evaluation is the case, applications must sacrifice timeliness to get more accurate evaluation results or tolerate evaluation result with a guaranteed error bound obtained from analyzing the samples of the data to meet their stringent timeline. In this paper, we study quality-of-service (QoS)-aware data replication and placement for approximate query evaluation of big data analytics in a distributed cloud, where the original (source) data of a query is distributed at different geo-distributed datacenters. We focus on the problems of placing data samples of the source data at some strategic datacenters to meet stringent query delay requirements of users, by exploring a non-trivial trade-off between the cost of query evaluation and the error bound of the evaluation result. We first propose an approximation algorithm with a provable approximation ratio for a single approximate query. We then develop an efficient heuristic algorithm for evaluating a set of approximate queries with the aim to minimize the evaluation cost while meeting the delay requirements of these queries. We finally demonstrate the effectiveness and efficiency of the proposed algorithms through both experimental simulations and implementations in a real test-bed, real datasets are employed. Experimental results show that the proposed algorithms are promising. [ABSTRACT FROM AUTHOR]

In network science and the data mining field, a long-lasting and significant task is to predict the propagation capability of nodes in a complex network. Recently, an increasing number of unsupervised learning algorithms, such as the prominent PageRank (PR) and LeaderRank (LR), have been developed to address this issue. However, in degree uncorrelated networks, this paper finds that PR and LR are actually proportional to in-degree of nodes. As a result, the two algorithms fail to accurately predict the nodes’ propagation capability. To overcome the arising drawback, this paper proposes a new iterative algorithm called SpectralRank (SR), in which the nodes’ propagation capability is assumed to be proportional to the amount of its neighbors after adding a ground node to the network. Moreover, a weighted SR algorithm is also proposed to further involve a priori information of a node itself. A probabilistic framework is established, which is provided as the theoretical foundation of the proposed algorithms. Simulations of the susceptible-infected-removed model on 32 networks, including directed, undirected, and binary ones, reveal the advantages of the SR-family methods (i.e., weighted and unweighted SR) over PR and LR. When compared with other 11 well-known algorithms, the indices in the SR-family always outperform the others. Therefore, the proposed measures provide new insights on the prediction of the nodes’ propagation capability and have great implications in the control of spreading behaviors in complex networks. [ABSTRACT FROM AUTHOR]

In this paper, a distributed average tracking (DAT) problem is studied for Lipschitz-type of nonlinear dynamical systems. The objective is to design DAT algorithms for locally interactive agents to track the average of multiple reference signals. Here, in both dynamics of agents and reference signals, there is a nonlinear term satisfying a Lipschitz-type condition. Three types of DAT algorithms are designed. First, based on state-dependent-gain design principles, a robust DAT algorithm is developed for solving DAT problems without requiring the same initial condition. Second, by using a gain adaption scheme, an adaptive DAT algorithm is designed to remove the requirement that global information, such as the eigenvalue of the Laplacian and the Lipschitz constant, is known to all agents. Third, to reduce chattering and make the algorithms easier to implement, a couple of continuous DAT algorithms based on time-varying or time-invariant boundary layers are designed, respectively, as a continuous approximation of the aforementioned discontinuous DAT algorithms. Finally, some simulation examples are presented to verify the proposed DAT algorithms. [ABSTRACT FROM AUTHOR]

In edge-cloud computing, a set of servers (called edge servers) are deployed near the mobile devices to allow these devices to offload their jobs to and subsequently obtain their results from the edge servers with low latency. One fundamental problem in edge-cloud systems is how to dispatch and schedule the jobs so that the job response time (defined as the interval between the release of the job and the arrival of the computation result at the device) is minimized. In this paper, we propose a general model for this problem, where the jobs are generated in arbitrary order and at arbitrary times at the mobile devices and then offloaded to servers with both upload and download delays. Our goal is to minimize the total weighted response time of all the jobs. The weight is set based on how latency-sensitive the job is. We derive the first online job dispatching and scheduling algorithm in edge-clouds, called OnDisc, which is scalable in the speed augmentation model; that is, OnDisc is $(1 + \varepsilon)$ -speed $O(1/\varepsilon)$ -competitive for any small constant $\varepsilon >0$. Moreover, OnDisc can be easily implemented in distributed systems. We also extend OnDisc with a fairness knob to incorporate the trade-off between the average job response time and the degree of fairness among jobs. Extensive simulations based on a real-world data-trace from Google show that OnDisc can reduce the total weighted response time dramatically compared with heuristic algorithms. [ABSTRACT FROM AUTHOR]