Search

We present a (1 + k k + 2) -approximation algorithm for the Maximum k - dependent Set problem on bipartite graphs for any k ≥ 1. For a graph with n vertices and m edges, the algorithm runs in O (k m n) time and improves upon the previously best-known approximation ratio of 1 + k k + 1 established by Kumar et al. (2014). Our proof also indicates that the algorithm retains its approximation ratio when applied to the (more general) class of König–Egerváry graphs. [ABSTRACT FROM AUTHOR]

Background: sorting by transpositions (SBT) is a classical problem in genome rearrangements. In 2012, SBT was proven to be NP -hard and the best approximation algorithm with a 1.375 ratio was proposed in 2006 by Elias and Hartman (EH algorithm). Their algorithm employs simplification, a technique used to transform an input permutation π into a simple permutation π ^ , presumably easier to handle with. The permutation π ^ is obtained by inserting new symbols into π in a way that the lower bound of the transposition distance of π is kept on π ^ . The simplification is guaranteed to keep the lower bound, not the transposition distance. A sequence of operations sorting π ^ can be mimicked to sort π . Results and conclusions: First, using an algebraic approach, we propose a new upper bound for the transposition distance, which holds for all S n . Next, motivated by a problem identified in the EH algorithm, which causes it, in scenarios involving how the input permutation is simplified, to require one extra transposition above the 1.375-approximation ratio, we propose a new approximation algorithm to solve SBT ensuring the 1.375-approximation ratio for all S n . We implemented our algorithm and EH's. Regarding the implementation of the EH algorithm, two other issues were identified and needed to be fixed. We tested both algorithms against all permutations of size n, 2 ≤ n ≤ 12 . The results show that the EH algorithm exceeds the approximation ratio of 1.375 for permutations with a size greater than 7. The percentage of computed distances that are equal to transposition distance, computed by the implemented algorithms are also compared with others available in the literature. Finally, we investigate the performance of both implementations on longer permutations of maximum length 500. From the experiments, we conclude that maximum and the average distances computed by our algorithm are a little better than the ones computed by the EH algorithm and the running times of both algorithms are similar, despite the time complexity of our algorithm being higher. [ABSTRACT FROM AUTHOR]

Piecewise Linear Approximation (PLA) is one of the most widely used approaches for representing a time series with a set of approximated line segments. With this compressed form of representation, many large complicated time series can be efficiently stored, transmitted and analyzed. In this article, with the introduced concept of “semi-connection” that allowing two representation lines to be connected at a point between two consecutive time stamps, we propose a new optimal linear-time PLA algorithm SemiOptConnAlg for generating the least number of semi-connected line segments with guaranteed maximum error bound. With extended experimental tests, we demonstrate that the proposed algorithm is very efficient in execution time and achieves better performances than the state-of-art solutions. [ABSTRACT FROM AUTHOR]

Suppose a target is hidden in one of the vertices of an edge-weighted graph according to a known probability distribution. Starting from a fixed root node, an expanding search visits the vertices sequentially until it finds the target, where the next vertex can be reached from any of the previously visited vertices. That is, the time to reach the next vertex equals the shortest-path distance from the set of all previously visited vertices. The expanding search problem then asks for a sequence of the nodes, so as to minimize the expected time to finding the target. This problem has numerous applications, such as searching for hidden explosives, mining coal, and disaster relief. In this paper, we develop exact algorithms and heuristics, including a branch-and-cut procedure, a greedy algorithm with a constant-factor approximation guarantee, and a local search procedure based on a spanning-tree neighborhood. Computational experiments show that our branch-and-cut procedure outperforms existing methods for instances with nonuniform probability distributions and that both our heuristics compute near-optimal solutions with little computational effort. Summary of Contribution: This paper studies new algorithms for the expanding search problem, which asks to search a graph for a target hidden in one of the nodes according to a known probability distribution. This problem has applications such as searching for hidden explosives, mining coal, and disaster relief. We propose several new algorithms, including a branch-and-cut procedure, a greedy algorithm, and a local search procedure; and we analyze their performance both experimentally and theoretically. Our analysis shows that the algorithms improve on the performance of existing methods and establishes the first constant-factor approximation guarantee for this problem. [ABSTRACT FROM AUTHOR]

We revisit the constant-factor approximation algorithm for the asymmetric traveling salesman problem by Svensson, Tarnawski, and V\'egh [J. ACM, 67 (2020), 37]. We improve on each part of this algorithm. We avoid the reduction to irreducible instances and thus obtain a simpler and much better reduction to vertebrate pairs. We also show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio. Overall we improve the approximation ratio from 506 to 22 + ε for any ε > 0. This also improves the upper bound on the integrality ratio from 319 to 22. [ABSTRACT FROM AUTHOR]

With the increasing maturity of wireless charging technology, especially the development of magnetic resonance wireless charging technology, the employment of mobile charging vehicles and wireless charging technology to replenish sensors' energy to ensure the continuous operation of wireless sensor networks has become a new research hotspot. This paper focused on how to schedule multiple charging vehicles to replenish energy to the sensors in a large-scale wireless sensor network. In order to balance the charging tasks of multiple charging vehicles and reduce the completion time of the whole charging task, the paper proposed the charging task completion time minimization problem, hoping to find K closed charging circles for K charging vehicles, so that the longest completion time among these K vehicles was the shortest. Since the charging task completion time minimization problem was an NP-hard problem and it was difficult to find an optimal solution in polynomial time, this paper proposed an approximation algorithm with a ratio of 5 for this problem. Finally, it demonstrated the performance of the algorithm by simulation experiments, and the experiments show that the actual approximation ratio of the proposed algorithm is less than 2. [ABSTRACT FROM AUTHOR]

Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is large gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat 1- 1 e in the single-pass streaming model. Let n be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio 2- v 2+e requires O(n K2) space for any e > 0, where K is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio K 2K-1 + e requires O(n K2) space for any e > 0, where K is the rank of the given matroid. In addition, we give streaming algorithms that assume access to the objective function via a weak oracle that can only be used to evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios K 2K-1 and 1 2, respectively, whose space complexity is exponential in K but is independent of n. The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of K 2K-1 for a matroid constraint, which almost settles the approximation ratio for a matroid constraint that can be obtained by a streaming algorithm whose space complexity is independent of n. [ABSTRACT FROM AUTHOR]

The symmetric tensor decomposition problem is a fundamental problem in many fields, which appealing for investigation. In general, greedy algorithm is used for tensor decomposition. That is, we first find the largest singular value and singular vector and subtract the corresponding component from tensor, then repeat the process. In this article, we focus on designing one effective algorithm and giving its convergence analysis. We introduce an exceedingly simple and fast algorithm for rank‐one approximation of symmetric tensor decomposition. Throughout variable splitting, we solve symmetric tensor decomposition problem by minimizing a multiconvex optimization problem. We use alternating gradient descent algorithm to solve. Although we focus on symmetric tensors in this article, the method can be extended to nonsymmetric tensors in some cases. Additionally, we also give some theoretical analysis about our alternating gradient descent algorithm. We prove that alternating gradient descent algorithm converges linearly to global minimizer. We also provide numerical results to show the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

Although we have seen a proliferation of algorithms for recommending visualizations, these algorithms are rarely compared with one another, making it difficult to ascertain which algorithm is best for a given visual analysis scenario. Though several formal frameworks have been proposed in response, we believe this issue persists because visualization recommendation algorithms are inadequately specified from an evaluation perspective. In this paper, we propose an evaluation-focused framework to contextualize and compare a broad range of visualization recommendation algorithms. We present the structure of our framework, where algorithms are specified using three components: (1) a graph representing the full space of possible visualization designs, (2) the method used to traverse the graph for potential candidates for recommendation, and (3) an oracle used to rank candidate designs. To demonstrate how our framework guides the formal comparison of algorithmic performance, we not only theoretically compare five existing representative recommendation algorithms, but also empirically compare four new algorithms generated based on our findings from the theoretical comparison. Our results show that these algorithms behave similarly in terms of user performance, highlighting the need for more rigorous formal comparisons of recommendation algorithms to further clarify their benefits in various analysis scenarios. [ABSTRACT FROM AUTHOR]

Stochastic inventory systems with lead times are often challenging to optimize, including single-sourcing lost-sales and dual-sourcing systems. Recent numerical results suggest that capped policies demonstrate superior performance over existing heuristics. However, the superior performance lacks a theoretical foundation. In "1.79-Approximation Algorithms for Continuous Review Single-Sourcing Lost-Sales and Dual-Sourcing Inventory Models," the author provides a theoretical foundation for this phenomenon in two classical inventory models. First, in a continuous review lost-sales model with lead times and Poisson demand, he proves that a capped base-stock policy has a worst-case performance guarantee of 1.79 by conducting an asymptotic analysis under a large penalty cost and lead time. Second, in a more complex continuous review dual-sourcing model with general lead times and Poisson demand, he proves that a similar capped dual-index policy has a worst-case performance guarantee of 1.79 under large lead time and ordering cost differences. The results provide a deeper understanding of the superior numerical performance of capped policies and present a new approach to proving worst-case performance guarantees of simple policies in hard inventory problems. Stochastic inventory systems with lead times are often challenging to optimize, including single-sourcing lost-sales and dual-sourcing inventory systems. Recent numerical results suggest that capped policies demonstrate superior performance over existing heuristics. However, the superior performance lacks a theoretical foundation, and why such policies generally perform so well remains a major open question. In this paper, we provide a theoretical foundation for this phenomenon in two classical inventory models with lead times. First, in a continuous-review lost-sales inventory model with lead times and Poisson demand, we prove that a so-called capped base-stock policy has a worst-case performance guarantee of 1.79 by conducting an asymptotic analysis under a large penalty cost and lead time. Second, we extend the analysis to a more complex continuous-review dual-sourcing inventory model with general lead times and Poisson demand and also prove that a so-called capped dual-index policy has a worst-case performance guarantee of 1.79 under large lead time and ordering cost differences. Our results provide a deeper understanding of the superior numerical performance of capped policies and present a new approach to proving worst-case performance guarantees of simple policies in hard inventory problems. [ABSTRACT FROM AUTHOR]

In this paper, we describe a new algorithm to build a few sparse principal components from a given data matrix. Our approach does not explicitly create the covariance matrix of the data and can be viewed as an extension of the Kogbetliantz algorithm to build an approximate singular value decomposition for a few principal components. We show the performance of the proposed algorithm to recover sparse principal components on various datasets from the literature and perform dimensionality reduction for classification applications. [ABSTRACT FROM AUTHOR]

In the field of minimally invasive surgery, flexible needles can avoid blood vessels and organs more flexibly compared to rigid needles. One of the main challenges when using flexible needles to reach lesions is planning a suitable path. Due to the non-holonomic characteristic of the flexible needle dynamics and the tissue deformation caused by the needle tip during the insertion, the accessibility and safety of the needle’s states need to be considered in the path planning stage. In this article, we propose an adaptable algorithm by improving the canonical rapidly exploring random trees* (RRT*) algorithm to compute a path for the flexible needle to reach targets in a layered tissue environment. The improved RRT* algorithm that addresses the motion constraints of the flexible needle renders the computed path comparatively smoother and optimal in some approximation sense. In the proposed algorithm, a strategy of adapting some of its parameters for different tissues during the insertion is developed, which improves the safety of surgeries. Moreover, the path cost used in the algorithm takes the potential fields of surrounding obstacles into account, which is used to deal with the influence of the local movement of tissues during the needle puncture process. Simulations are conducted to verify the effectiveness of the proposed algorithm. The results show that the improved RRT* algorithm generates a smooth and safe path which satisfies the motion constraints of the flexible needle in layered tissue environment. [ABSTRACT FROM AUTHOR]

Security is a key problem for the transmission, interchange, and storage process of multimedia systems and applications. In 2018, Li et al. proposed in-depth security analysis on an image encryption algorithm based on a first-order time-delay system (IEATD) and gave a specific chosen-plaintext attack on it. Moreover, an enhanced version called as IEACD was designed to fix the reported security defects. This article analyzes the essential structures of the two algorithms and evaluates their real security performances: 1) no efficient nonlinear operations are adopted to assure the sensibility of keystream; 2) the equivalent secret key of IEATD can be efficiently recovered from one known plain-image and the corresponding cipher-image; and 3) IEACD can still be efficiently cracked with a chosen-plaintext attack. Both rigorous theoretical analyses and detailed experimental results are provided to demonstrate effectiveness of the advanced cryptanalytic methods. [ABSTRACT FROM AUTHOR]

We present a low-constant approximation for the metric k -median problem on insertion-only streams using O (ε − 3 k log n) space. In particular, we present a streaming (O (ε − 3 k log n) , 2 + ε) -bicriterion solution that reports cluster weights. Running the offline approximation algorithm due to Byrka et al. (2015) on this bicriterion solution yields a (17. 66 + ε) -approximation (Guha et al., 2003; Charikar et al., 2003; Braverman et al., 2011). Our result matches the best-known space requirements for streaming k -median clustering while significantly improving the approximation accuracy. We also provide a lower bound, showing that any polylog (n) -space streaming algorithm that maintains an (α , β) -bicriterion must have β ≥ 2. Our technique breaks the stream into segments defined by jumps in the optimal clustering cost, which increases monotonically as the stream progresses. By storing an accurate summary of recent segments of the stream and a lower-space summary of older segments, our algorithm maintains a (O (ε − 3 k log n) , 2 + ε) -bicriterion solution for the entirety of the stream. In addition to our main result, we introduce a novel construction that we call a candidate set. This is a collection of points that, with high probability, contains k points that yield a near-optimal k -median cost. We present an algorithm called monotone faraway sampling (MFS) for constructing a candidate set in a single pass over a data stream. We show that using this candidate set in tandem with a coreset speeds up the search for a solution set of k cluster centers upon termination of the data stream. While coresets of smaller asymptotic size are known, comparative simplicity of MFS makes it appealing as a practical technique. [ABSTRACT FROM AUTHOR]

Wireless sensor networks (WSNs) are extensively utilized in various circumstances. For applications, the construction of the virtual backbones (VBs) of WSNs has attracted considerable attention in this field. Generally, a homogeneous WSN is formulated as a unit disk graph (UDG), and the VB of the corresponding WSN is modeled as a connected dominating set (CDS) in the UDG. In certain applications, communication between sensors in a network may fail for various reasons, such as sensor movement, signal interference, and the appearance of obstacles. Consequently, a CDS in a UDG should possess fault tolerance on the edges. In this paper, we introduce a new concept called the 2 edge-connected 2 edge-dominating set ( 2 , 2 -ECDS); then, we design an approximation algorithm for computing 2 , 2 -ECDSs in UDGs, the performance ratio of which is 30.51. By means of simulations, we compare our algorithm and existing algorithms in terms of the CDS size, running time, success rate, and network lifetime. The simulation results indicate that our algorithm exhibits better performance and is more suitable for constructing a VB with edge fault tolerance in a WSN. [ABSTRACT FROM AUTHOR]

We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include: A (2 + ϵ) -approximation for all-pairs shortest paths in O (log 2 n / ϵ) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model. A (1 + ϵ) -approximation for multi-source shortest paths from O (n) sources in O (log 2 n / ϵ) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size. Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in O ~ (n 1 / 6) rounds. [ABSTRACT FROM AUTHOR]

• Improved distributed approximation for Steiner tree. • Approximation algorithms for Steiner tree in the CONGEST model of distributed computing. • Steiner tree problem in network optimization. In this paper we present two deterministic distributed algorithms for the Steiner tree (ST) problem in the CONGEST model. The first algorithm computes a 2 (1 − 1 / ℓ) -approximate ST using O (S + n log ⁎ ⁡ n) rounds and O (m S + n 3 / 2) messages for a graph of n nodes and m edges, where S is the shortest path diameter of the graph and ℓ is the number of leaf nodes in the optimal ST. It improves the round complexity of the best distributed ST algorithm known so far, which is O ˜ (S + min { S t , n }) [34] , where t is the number of terminal nodes. The second algorithm improves the message complexity of the first one by dropping the additive term of O (n 3 / 2) at the expense of a logarithmic multiplicative factor in the round complexity. We also show that for graphs with S = O (log ⁡ n) , a 2 (1 − 1 / ℓ) -approximate ST can be deterministically computed using O ˜ (n) rounds and O ˜ (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in [15,22,37]. [ABSTRACT FROM AUTHOR]

We consider a well-studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and a fixed parameter d ≥ 1 , in the maximum diameter-bounded subgraph problem (MaxDBS for short) the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d = 1 , this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n 1 - ϵ , for any ϵ > 0 . Moreover, it is known that, for any d ≥ 2 , it is NP-hard to approximate MaxDBS within a factor n 1 / 2 - ϵ , for any ϵ > 0 . In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems, and several geometric properties of unit disk graphs. [ABSTRACT FROM AUTHOR]

Point-mass filter (PMF) is a numerical Bayesian filtering algorithm that estimates the probability density of state variables using a deterministically defined grid on state space. An important factor that determines the performance of the PMF is how accurately one guesses the probabilistically significant region (called a nonnegligible region) where a grid will be placed. In this article, we introduce the concept of boundary to express the nonnegligible region and propose a method to define a grid tailored to the nonnegligible region of posterior density by transporting boundary according to log-homotopy induced flow. The proposed method ensures accurate estimation performance and robustness especially for uncertain prior information. Terrain referenced navigation (TRN) is composed of a nonlinear observation model defined by terrains and an uncertain initial position. Therefore, it is a major application of the PMF, which can handle nonlinearity and has a more robust characteristic than other numerical filters. In order to compare the proposed PMF with the conventional PMFs, this article applies the proposed method to TRN. Monte Carlo simulation results show that the proposed algorithm is more accurate and robust than the conventional PMFs. [ABSTRACT FROM AUTHOR]

In this article, we consider the problem of transmit waveform design for collocated multiple-input multiple-output (MIMO) radar under a constant-envelope (CE) constraint by taking advantage of the coordinate descent (CD) method. In this article, two algorithms are proposed to generate the CE waveforms. In the first algorithm, unlike the two stage methods, we propose an algorithm for direct design of the transmit waveform in order to approximate a desired beampattern (BP). Since our optimization problem is nonconvex multivariate (samples of the transmit waveform matrix), therefore, the CD method is leveraged, which converts the multivariate minimization into a number of scalar minimizations by cyclically (iteratively) optimizing w.r.t. each of the variables (coordinates) assuming the others are fixed. In the second algorithm, by exploiting the results of the first-algorithm, an algorithm to generate a transmit waveform for approximation of a given covariance matrix (CM) is proposed. We take into account in each of the two cases both the finite-alphabet phase codes and the continuous phase codes. In the former, a discrete Fourier transform based procedure is proposed in order to reduce the calculations involved in the searching step over the phase alphabet set. In the latter, both accurate and approximate closed form solutions for the phase code are derived. The experimental results show that, in the first case (BP approximation), our methods can attain to the performance of the nonconstrained methods and in the second case (realizing a given CM), our method has gained higher performance compared with some recent counterparts. [ABSTRACT FROM AUTHOR]

We study the problem of visually monitoring a set of points on a 2.5D terrain using an unmanned aerial vehicle (UAV) with a downward-facing camera. The goal is to find a tour of minimum length for the UAV offline to visually inspect all points of interest. Varying terrain and limited field of view of the camera restrict the visibility of the UAV and can create obstacles in the flight path, making the problem challenging. The problem is NP-hard and generalizes the traveling salesperson problem (TSP). We present several algorithms to solve this problem. Our main theoretical contribution is a constant-factor approximation algorithm (assuming fixed parameters for the terrain). We also present a practical algorithm that uses the solution to a generalized TSP (GTSP) subinstance. We benchmark the GTSP-based algorithm using a branch-and-cut integer linear programming formulation and find that the proposed algorithm scales to much larger instances and is computationally fast. We also show proof-of-concept using field deployment of a UAV to visually monitor points of interest in the environment. [ABSTRACT FROM AUTHOR]

Given a connected graph G = (V , E) , we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k ≥ 4 , no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k ≥ 3 . Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems. [ABSTRACT FROM AUTHOR]

We study the generalized minimum Manhattan network (GMMN) problem: given a set P of pairs of points in the Euclidean plane R 2 , we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the L 1 metric (a so-called Manhattan path) for each pair in P . This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in P , and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach. [ABSTRACT FROM AUTHOR]

In the classic minimum makespan scheduling problem, we are given an input sequence of n jobs with sizes. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. In this paper, we consider online scheduling algorithms without preemption. However, we allow the online algorithm to change the assignment of up to k jobs at the end for some limited number k. For m identical machines, Albers and Hellwig (Algorithmica 79(2):598–623, 2017) give tight bounds on the competitive ratio in this model. The precise ratio depends on, and increases with, m. It lies between 4/3 and ≈ 1.4659 . They show that k = O (m) is sufficient to achieve this bound and no k = o (n) can result in a better bound. We study m uniform machines, i.e., machines with different speeds, and show that this setting is strictly harder. For sufficiently large m, there is a δ = Θ (1) such that, for m machines with only two different machine speeds, no online algorithm can achieve a competitive ratio of less than 1.4659 + δ with k = o (n) . We present a new algorithm for the uniform machine setting. Depending on the speeds of the machines, our scheduling algorithm achieves a competitive ratio that lies between 4/3 and ≈ 1.7992 with k = O (m) . We also show that k = Ω (m) is necessary to achieve a competitive ratio below 2. Our algorithm is based on maintaining a specific imbalance with respect to the completion times of the machines, complemented by a bicriteria approximation algorithm that minimizes the makespan and maximizes the average completion time for certain sets of machines. [ABSTRACT FROM AUTHOR]

The minimum dominating set (MDS) of the network is a node subset of smallest size that every node in the network is either in this subset or is adjacent to one or more nodes of this subset. MDS has found wide applications, ranging from network monitoring, routing, to epidemic control, and text processing. However, the majority of existing studies on MDS problem are confined to single networks. In real world, more and more complex systems consist of a set of elements linked up by different types of connections, which are best modeled as multiplex networks with interacting network layers. Though vastly important, the MDS of the multiplex networks has not yet been formally defined and its application and identification remain open issues. In this article, we present the definition of the MDS of the multiplex network and show some of its possible applications. For solving the MDS problem of the multiplex network, we built a spin-glass model and solve it through the belief-propagation (BP) equations under the replica symmetry mean-field theory. As a consequence, we can predict the relative size of the MDS of the multiplex network theoretically and we can propose a BP-guided decimation algorithm to construct an approximate optimal dominating set in practice. Then the algorithm is improved in both accuracy and efficiency by embedding a novel multiplex network-oriented leaf-removal strategy. The effectiveness of the proposed algorithms is finally verified by comparing with other methods on a number of the multiplex network examples. [ABSTRACT FROM AUTHOR]

In this research, a new technique is suggested to reduce the long time required by the encoding process by using modified moment features on domain blocks. The modified moment features were used in accelerating the matching step of the Iterated Function System (IFS). The main disadvantage facing the fractal image compression (FIC) method is the over-long encoding time needed for checking all domain blocks and choosing the least error to get the best matched domain for each block of ranges. In this paper, we develop a method that can reduce the encoding time of FIC by reducing the size of the domain pool based on the moment features of domain blocks, followed by a comparison with threshold (the selected threshold based on experience is 0.0001). The experiment was conducted on three images with size of 512x512 pixel, resolution of 8 bits/pixel, and different block size (4x4, 8x8 and, 16x16 pixels). The resulted encoding time (ET) values achieved by the proposed method were 41.53, 39.06, and 38.16 sec, respectively, for boat, butterfly, and house images of block size 4x4 pixel. These values were compared with those obtained by the traditional algorithm for the same images with the same block size, which were 1073.85, 1102.66, and 1084.92 sec, respectively. The results imply that the proposed algorithm could remarkably reduce the ET of the images in comparison with the traditional algorithm. [ABSTRACT FROM AUTHOR]

A data-based value iteration algorithm with the bidirectional approximation feature is developed for discounted optimal control. The unknown nonlinear system dynamics is first identified by establishing a model neural network. To improve the identification precision, biases are introduced to the model network. The model network with biases is trained by the gradient descent algorithm, where the weights and biases across all layers are updated. The uniform ultimate boundedness stability with a proper learning rate is analyzed, by using the Lyapunov approach. Moreover, an integrated value iteration with the discounted cost is developed to fully guarantee the approximation accuracy of the optimal value function. Then, the effectiveness of the proposed algorithm is demonstrated by carrying out two simulation examples with physical backgrounds. [ABSTRACT FROM AUTHOR]

Mobile edge computing becomes a promising technology to mitigate the latency of various cloud services. In addition, network function virtualization (NFV) has been shown a great potential in reducing the operational cost of cloud services while enhancing the flexibility of virtual network function deployments, by implementing dedicated hardware network functions as pieces of software in generic servers. Recently, the GPU acceleration has been investigated to speed up flow processing in virtual network functions (VNFs), by leveraging the parallelism of GPUs. VNFs that need accelerations prefer to stay at cloudlets (locations) equipped with GPUs. However, little attention has been paid for the VNF placement that takes into account GPU-affinity in cloudlets of mobile edge clouds. In this paper, we consider the affinity-aware throughput maximization problem in a mobile edge cloud via leveraging the parallelism on GPUs for user requests with VNF requirements. We consider two types of affinities in the VNF placement: The soft-affinity that allows VNFs to be executed by either CPUs or GPUs in cloudlets; and the hard-affinity that only allows VNFs to be placed to the GPUs of a specified set of cloudlets. We formulate two corresponding VNF placement problems in a mobile edge cloud. Specifically, we first propose an exact solution to the soft-affinity throughput maximization problem by formulating an Integer Linear Program (ILP). We then propose an efficient algorithm for the problem, by proposing a randomized algorithm with a provable approximation ratio for the hard-affinity-aware throughput maximization problem and extending the proposed approximation algorithm to the soft-affinity throughput maximization problem. Furthermore, assuming that user requests arrive into the mobile edge cloud one by one without the knowledge of future arrivals, we devise an online algorithm with a good competitive ratio for this dynamic hard-affinity-aware throughput maximization problem. Finally, we evaluate the performance of the proposed algorithms, through simulations and implementations in a real test-bed. Experimental results show that the performance of the proposed algorithms outperform their existing counterparts and achieve higher throughput. [ABSTRACT FROM AUTHOR]

Unsplittable flow problems cover a wide range of telecommunication and transportation problems and their efficient resolution is key to a number of applications. In this work, we study algorithms that can scale up to large graphs and important numbers of commodities. We present and analyze in detail a heuristic based on the linear relaxation of the problem and randomized rounding. We provide empirical evidence that this approach is competitive with state-of-the-art resolution methods either by its scaling performance or by the quality of its solutions. We provide a variation of the heuristic which has the same approximation factor as the state-of-the-art approximation algorithm. We also derive a tighter analysis for the approximation factor of both the variation and the state-of-the-art algorithm. We introduce a new objective function for the unsplittable flow problem and discuss its differences with the classical congestion objective function. Finally, we discuss the gap in practical performance and theoretical guarantees between all the aforementioned algorithms. [ABSTRACT FROM AUTHOR]

Federated learning enables machine learning algorithms to be trained over decentralized edge devices without requiring the exchange of local datasets. Successfully deploying federated learning requires ensuring that agents (e.g., mobile devices) faithfully execute the intended algorithm, which has been largely overlooked in the literature. In this study, we first use risk bounds to analyze how the key feature of federated learning, unbalanced and non-i.i.d. data, affects agents’ incentives to voluntarily participate and obediently follow traditional federated learning algorithms. To be more specific, our analysis reveals that agents with less typical data distributions and relatively more samples are more likely to opt out of or tamper with federated learning algorithms. To this end, we formulate the first faithful implementation problem of federated learning and design two faithful federated learning mechanisms which satisfy economic properties, scalability, and privacy. First, we design a Faithful Federated Learning (FFL) mechanism which approximates the Vickrey–Clarke–Groves (VCG) payments via an incremental computation. We show that it achieves (probably approximate) optimality, faithful implementation, voluntary participation, and some other economic properties (such as budget balance). Further, the time complexity in the number of agents $K$ is $\mathcal {O}(\log (K))$. Second, by partitioning agents into several clusters, we present a scalable VCG mechanism approximation. We further design a scalable and Differentially Private FFL (DP-FFL) mechanism, the first differentially private faithful mechanism, that maintains the economic properties. Our DP-FFL mechanism enables one to make three-way performance tradeoffs among privacy, the iterations needed, and payment accuracy loss. [ABSTRACT FROM AUTHOR]

We formulate the sparse classification problem of n samples with p features as a binary convex optimization problem and propose a outer-approximation algorithm to solve it exactly. For sparse logistic regression and sparse SVM, our algorithm finds optimal solutions for n and p in the 10,000 s within minutes. On synthetic data our algorithm achieves perfect support recovery in the large sample regime. Namely, there exists an n 0 such that the algorithm takes a long time to find an optimal solution and does not recover the correct support for n < n 0 , while for n ⩾ n 0 , the algorithm quickly detects all the true features, and does not return any false features. In contrast, while Lasso accurately detects all the true features, it persistently returns incorrect features, even as the number of observations increases. Consequently, on numerous real-world experiments, our outer-approximation algorithms returns sparser classifiers while achieving similar predictive accuracy as Lasso. To support our observations, we analyze conditions on the sample size needed to ensure full support recovery in classification. For k-sparse classification, and under some assumptions on the data generating process, we prove that information-theoretic limitations impose n 0 < C 2 + σ 2 k log (p - k) , for some constant C > 0 . [ABSTRACT FROM AUTHOR]

Neutrosophic concept is known undirected graph theory to involve with complex logistic networks, not clearly given and unpredictable real life situations, where fuzzy logic malfunctions to model. The transportation objective is to ship all logistic nodes in the network. The logistic network mostly experiences in stable condition, but for some edges found to be volatile. The weight of these erratic edges may vary at random (bridgelifting/bascule, ad hoc accident on road, traffic condition) In this article, we propose an approximation algorithm for solving minimum spanning tree (MST) of an undirected neutrosophic graphs (UNG), in which the edge weights represent neutrosophic values. The approximation upon the balanced score calculation is introduced for all known configurations in alternative MST. As the result, we further compute decisive threshold value for the weak weights amid minimum cost pre-computation. If the threshold triggers then the proper MST can direct the decision and avoid post-computation. The proposed algorithm is also related to other existing approaches and a numerical analysis is presented. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We continue to study coherent partitions of graphs whereby the vertex set is partitioned into subsets that induce biclique spanned subgraphs. The problem of identifying the minimum number of edges to obtain biclique spanned connected components (CNP), called the coherence number, is NP-hard even on bipartite graphs. Here, we propose a graph transformation geared towards obtaining an O (log ⁡ n) -approximation algorithm for the CNP on a bipartite graph with n vertices. The transformation is inspired by a new characterization of biclique spanned subgraphs. In addition, we study coherent partitions on prime graphs, and show that finding coherent partitions reduces to the problem of finding coherent partitions in a prime graph. Therefore, these results provide future directions for approximation algorithms for the coherence number of a given graph. [ABSTRACT FROM AUTHOR]

We consider stochastic optimization of a smooth non-convex loss function with a convex non-smooth regularizer. In the online setting, where a single sample of the stochastic gradient of the loss is available at every iteration, the problem can be solved using the proximal stochastic gradient descent (SGD) algorithm and its variants. However in many problems, especially those arising in communications and signal processing, information beyond the stochastic gradient may be available thanks to the structure of the loss function. By constructing a strongly convex surrogate of the loss function at every iteration, the stochastic SCA algorithms can exploit the structural properties of the loss function. In this work, we take a closer look at the stochastic SCA algorithm and develop its asynchronous variant which can be used for resource allocation in wireless networks. While the stochastic SCA algorithm is known to converge asymptotically, its iteration complexity has not been well-studied, and is the focus of the current work. The insights obtained from the non-asymptotic analysis allow us to develop a more practical asynchronous variant of the stochastic SCA algorithm which allows the use of surrogate calculated in earlier iterations. We characterize precise bound on the maximum delay the algorithm can tolerate, while still achieving the same convergence rate. We apply the algorithm to the problem of linear precoding in wireless sensor networks, where it can be implemented at low complexity but is shown to perform well in practice. [ABSTRACT FROM AUTHOR]

In this paper, we consider the policy evaluation problem in reinforcement learning with agents on a decentralized and directed network. In order to evaluate the quality of a fixed policy in this decentralized setting, one option is for agents to run decentralized temporal-difference (TD) collaboratively. To account for the practical scenarios where the state and action spaces are large and malicious attacks emerge, we focus on the decentralized TD learning with linear function approximation in the presence of malicious agents (often termed as Byzantine agents). We propose a trimmed mean-based Byzantine-resilient decentralized TD algorithm to perform policy evaluation in this setting. We establish the finite-time convergence rate, as well as the asymptotic learning error that depends on the number of Byzantine agents. Numerical experiments corroborate the robustness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel adaptive importance sampling (AIS) algorithm for probabilistic inference. The sampler learns a proposal distribution adaptation strategy by framing AIS as a reinforcement learning problem. Under this structure, the proposal distribution of the sampler is treated as an agent whose state is controlled using a parameterized policy. At each iteration of the algorithm, the agent earns a reward that is related to its contribution to the variance of the AIS estimator of the normalization constant of the target distribution. Policy gradient methods are employed to learn a locally optimal policy that maximizes the expected value of the sum of all rewards. Numerical simulations on two different examples demonstrate promising results for the future application of the proposed method to complex Bayesian models. [ABSTRACT FROM AUTHOR]

Sorting permutations with various operations has applications in macro rearrangement of genes in a genome and the design of computer interconnection networks. Block-interchange is a powerful operation that swaps two substrings that are called as blocks in literature, in a given permutation. When the blocks are restricted to be adjacent then one obtains a well studied operation: transposition. We call either a prefix or a suffix as an extreme. Restricting one of the swapped blocks to be an extreme in block-interchange operation yields a prefix or a suffix block-interchange respectively, the two types of extreme block-interchanges. For prefix block-interchange operation over permutations we design: (i) an optimum algorithm to sort reverse permutation, R n , in n /2 moves, (ii) a simple 2-approximation algorithm, and (iii) for permutations with O (1) cycles, a 4/3 approximation algorithm. Due to symmetry, these results apply to suffix block-interchange operation also. [ABSTRACT FROM AUTHOR]

In this paper, we extend the bilinear generalized approximate message passing (BiG-AMP) approach, originally proposed for high-dimensional generalized bilinear regression, to the multi-layer case for the handling of cascaded problem such as matrix-factorization problem arising in relay communication among others. Assuming statistically independent matrix entries with known priors, the new algorithm called ML-BiGAMP could approximate the general sum-product loopy belief propagation (LBP) in the high-dimensional limit enjoying a substantial reduction in computational complexity. We demonstrate that, in large system limit, the asymptotic MSE performance of ML-BiGAMP could be fully characterized via a set of simple one-dimensional equations termed state evolution (SE). We establish that the asymptotic MSE predicted by ML-BiGAMP’ SE matches perfectly the exact MMSE predicted by the replica method, which is well-known to be Bayes-optimal but infeasible in practice. This consistency indicates that the ML-BiGAMP may still retain the same Bayes-optimal performance as the MMSE estimator in high-dimensional applications, although ML-BiGAMP's computational burden is far lower. As an illustrative example of the general ML-BiGAMP, we provide a detector design that could estimate the channel fading and the data symbols jointly with high precision for the two-hop amplify-and-forward relay communication systems. [ABSTRACT FROM AUTHOR]

Novel sparse reconstruction algorithms are proposed for beamspace channel estimation in massive multiple-input multiple-output systems. The proposed algorithms minimize a least-squares objective having a nonconvex regularizer. This regularizer removes the penalties on a few large-magnitude elements from the conventional $\ell _{1}$ -norm regularizer, and thus it only forces penalties on the remaining elements that are expected to be zeros. Accurate and fast reconstructions can be achieved by performing gradient projection updates within the framework of difference of convex functions (DC) programming. A double-loop algorithm and a single-loop algorithm are proposed via different DC decompositions, and these two algorithms have distinct computational complexities and convergence rates. An extension algorithm is further proposed by designing new step sizes for the single-loop algorithm. The extension algorithm has a faster convergence rate and can achieve approximately the same level of accuracy as the proposed double-loop algorithm. Numerical results show significant advantages of the proposed algorithms over existing reconstruction algorithms in terms of reconstruction accuracies and runtimes. Compared with the benchmark channel estimation approaches, the proposed algorithms can achieve smaller channel reconstruction error and higher achievable spectral efficiency. [ABSTRACT FROM AUTHOR]

• The placement of data and the scheduling of request are studied in edge caching. • Network unreliability and limited storage and bandwidth resources are considered. • Two algorithms with different computation complexity and cache efficiency are developed. • The experiments are conducted to evaluate the performance of proposed caching strategies. Edge caching is a prevailing media delivery technology where data is hosted at the edge nodes with computing and storage capability in close proximity to users, in order to expand the backhaul network capacity and enhance users' quality of experience (QoE). The existing work in this area often neglects the fact that large-scale distributed cache networks are not particularly reliable and many edge nodes are prone to failure. In this paper we investigate and develop a novel, cooperative caching mechanism for content placement and request routing. We aim to minimize the content access delay and achieve the optimization in polynomial time, taking into account failures in an unreliable network environment with limited edge storage and bandwidth. We introduce two optimization algorithms: 1) a primal-dual algorithm that is based on the Lagrangian dual decomposition and subgradient method, and 2) a greedy-based approximation algorithm with a proven approximation ratio. Numerical results show that the proposed algorithms outperform other comparative approaches in synthetic and real network environments, and the approximation algorithm is particularly suitable for networking scenarios with sparse node connectivity and resources in short supply. [ABSTRACT FROM AUTHOR]

We study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function. The connection is general and includes but is not limited to problems defined on graphs. We show a series of results exploring the connection and highlight examples of hard problem classes where a nontrivial symmetry subgroup can be obtained efficiently. In particular, we show how classical objective function symmetries lead to invariant measurement outcome probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. To illustrate the power of the developed connection, we apply machine learning techniques toward predicting QAOA performance based on symmetry considerations. We provide numerical evidence that a small set of graph symmetry properties suffices to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important setting where QAOA parameter schedules are constrained to be linear and hence easier to optimize. [ABSTRACT FROM AUTHOR]

In this work, we study the generalization capability of algorithms from an information-theoretic perspective. It has been shown that the expected generalization error of an algorithm is bounded from above by a function of the relative entropy between the conditional probability distribution of the algorithm’s output hypothesis, given the dataset with which it was trained, and its marginal probability distribution. We build upon this fact and introduce a mathematical formulation to obtain upper bounds on this relative entropy. Assuming that the data is discrete, we then develop a strategy using this formulation, based on the method of types and typicality, to find explicit upper bounds on the generalization error of stable algorithms, i.e., algorithms that produce similar output hypotheses given similar input datasets. In particular, we show the bounds obtained with this strategy for the case of $\epsilon $ -DP and $\mu $ -GDP algorithms. [ABSTRACT FROM AUTHOR]

We study a security game over a network played between a defender and kattackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of λ nodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717–728, 2006). We are interested in Nash equilibria of this game, as well as in characterizing defense-optimal networks which allow for the best equilibrium defense ratio; this is the ratio of k over the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for λ constantly close to 1 or n. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is NP -hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for the Price of Defense for any λ ; this is the worst equilibrium defense ratio over all graphs. [ABSTRACT FROM AUTHOR]

Algorithms determine which calculations computers use to solve problems and are one of the central pillars of computer science. As algorithms improve, they enable scientists to tackle larger problems and explore new domains and new scientific techniques ,. Bold claims have been made about the pace of algorithmic progress. For example, the President’s Council of Advisors on Science and Technology (PCAST), a body of senior scientists that advise the U.S. President, wrote in 2010 that “in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed”. However, this conclusion was supported based on data from progress in linear solvers , which is just a single example. With no guarantee that linear solvers are representative of algorithms in general, it is unclear how broadly conclusions, such as PCAST’s, should be interpreted. Is progress faster in most algorithms? Just some? How much on average? [ABSTRACT FROM AUTHOR]

We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the algorithm exploits the 'winding' technology devised by McQuillan [CoRR abs/1301.2880 (2013)] and developed by Huang, Lu and Zhang [Proc. 27th Symp. on Disc. Algorithms (SODA16), 514–527]. We show that exact computation of the partition function is #P-hard, even for line graphs, indicating that an approximation algorithm is the best that can be expected. We also show that Glauber dynamics for the Ising model is rapidly mixing on line graphs, an example being the kagome lattice. [ABSTRACT FROM AUTHOR]

Due to line-of-sight communication links and distributed deployment, Unmanned Aerial Vehicles (UAVs) have attracted substantial interest in agile Mobile Edge Computing (MEC) service provision. In this paper, by clustering multiple users into independent communities based on their geographic locations, we design a 5G-enabled UAV-to-community offloading system. A system throughput maximization problem is formulated, subjected to the transmission rate, atomicity of tasks and speed of UAVs. By relaxing the transmission rate constraint, the mixed integer non-linear program is transformed into two subproblems. We first develop an average throughput maximization-based auction algorithm to determine the trajectory of UAVs, where a community-based latency approximation algorithm is developed to regulate the designed auction bidding. Then, a dynamic task admission algorithm is proposed to solve the task scheduling subproblem within one community. Performance analyses demonstrate that our designed auction bidding can guarantee user truthfulness, and can be fulfilled in polynomial time. Extensive simulations based on real-world data in health monitoring and online YouTube video services show that our proposed algorithm is able to maximize the system throughput while guaranteeing the fraction of served users. [ABSTRACT FROM AUTHOR]

Constrained interval type-2 (CIT2) fuzzy sets have been introduced to preserve interpretability when moving from type-1 to interval type-2 (IT2) membership functions. Although they can be used to produce type-2 fuzzy systems with enhanced explainability, so far, the latter comes at the expense of high computational cost. Specifically, the exhaustive type-reduction method for CIT2 Mamdani systems has been shown to be too slow to be used in practical applications and even the current approximation procedure is much slower than modern type-reduction algorithms used for IT2 fuzzy sets. In this article, a novel type-reduction procedure for CIT2 sets is presented, based on the concept of switch indices. The algorithm is applied on a real-world classification problem and compared to other type-reduction approaches used in IT2 and CIT2 systems. In the case studies presented, the new algorithm is significantly faster than the exhaustive and sampling CIT2 approaches while keeping the high level of interpretability of the type-reduction operation that characterizes CIT2 fuzzy sets. [ABSTRACT FROM AUTHOR]

A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to define the XOS function is called the width. In this paper, we study the problem of maximizing XOS functions in the value oracle model. The problem is trivial for the XOS functions of width 1 because they are just additive, but it is already nontrivial even when the width is restricted to 2. We show two types of tight bounds on the polynomial-time approximability for this problem. First, in general, the approximation bound is between O(n) and Ω (n / l o g n ) , and exactly θ (n / l o g n ) if randomization is allowed, where n is the ground set size. Second, when the width of the input XOS functions is bounded by a constant k ≥ 2, the approximation bound is between k − 1 and k − 1 − ɛ for any ɛ > 0. In particular, we give a linear-time algorithm to find an exact maximizer of a given XOS function of width 2, whereas we show that any exact algorithm requires an exponential number of value oracle calls even when the width is restricted to 3. [ABSTRACT FROM AUTHOR]

In this paper, a route-planning approach is proposed based on the region-segmentation Dynamic Programming (DP) algorithm for Automated Guided Vehicles (AGVs) in large Smart Road Network Systems (SRNSs) to deal with the problem of low route computation efficiency of the classical DP algorithm. We introduced an improved Markov Decision Process (MDP) to describe SRNSs, in which the SRNSs are divided into several regions according to the AGVs' start nodes and their goal nodes to improve the route-planning efficiency. Moreover, the route with the minimum number of turns is selected to reduce the system running time and energy cost in the following way: first, all the equidistant shortest routes are acquired from the AGVs' start nodes to their goal nodes using the improved DP algorithm; then, the routes are screened by calculating the angular deviation between all feasible routes and AGVs' initial directions, and the route with the fewest number of turns is taken as the shortest-time route. The simulation results verified that the proposed method can effectively solve the route-planning problem of AGVs in current SRNSs. [ABSTRACT FROM AUTHOR]