Search

Line coverage is the task of servicing a given set of one‐dimensional features in an environment. It is important for the inspection of linear infrastructure such as road networks, power lines, and oil and gas pipelines. This paper addresses the single robot line coverage problem for aerial and ground robots by modeling it as an optimization problem on a graph. The problem belongs to the broad class of arc routing problems and is closely related to the rural postman problem (RPP) on asymmetric graphs. The paper presents an integer linear programming formulation with proofs of correctness. Using the minimum cost flow problem, we develop approximation algorithms with guarantees on the solution quality. These guarantees also improve the existing results for the asymmetric RPP. The main algorithm partitions the problem into three cases based on the structure of the required graph, that is, the graph induced by the features that require servicing. We evaluate our algorithms on road networks from the 50 most populous cities in the world, consisting of up to 730 road segments. The algorithms, augmented with improvement heuristics, run within 3 s and generate solutions that are within 10% of the optimum. We experimentally demonstrate our algorithms with commercial UAVs on the UNC Charlotte campus road network. [ABSTRACT FROM AUTHOR]

The discrete α$$ \alpha $$‐neighbor p$$ p $$‐center problem (d‐α$$ \alpha $$‐p$$ p $$CP) is an emerging variant of the classical p$$ p $$‐center problem which recently got attention in literature. In this problem, we are given a discrete set of points and we need to locate p$$ p $$ facilities on these points in such a way that the maximum distance between each point where no facility is located and its α$$ \alpha $$‐closest facility is minimized. The only existing algorithms in literature for solving the d‐α$$ \alpha $$‐p$$ p $$CP are approximation algorithms and two recently proposed heuristics. In this work, we present two integer programming formulations for the d‐α$$ \alpha $$‐p$$ p $$CP, together with lifting of inequalities, valid inequalities, inequalities that do not change the optimal objective function value and variable fixing procedures. We provide theoretical results on the strength of the formulations and convergence results for the lower bounds obtained after applying the lifting procedures or the variable fixing procedures in an iterative fashion. Based on our formulations and theoretical results, we develop branch‐and‐cut (B&C) algorithms, which are further enhanced with a starting heuristic and a primal heuristic. We evaluate the effectiveness of our B&C algorithms using instances from literature. Our algorithms are able to solve 116 out of 194 instances from literature to proven optimality, with a runtime of under a minute for most of them. By doing so, we also provide improved solution values for 116 instances. [ABSTRACT FROM AUTHOR]

We study the investment incentives created by truthful mechanisms that allocate resources using approximation algorithms. Some approximation algorithms guarantee nearly 100% of the optimal welfare in the allocation problem but guarantee nothing when accounting for investment incentives. An algorithm's allocative and investment guarantees coincide if and only if its confirming negative externalities are sufficiently small. We introduce fast approximation algorithms for the knapsack problem that have no confirming negative externalities and guarantees close to 100% for both allocation and investment. [ABSTRACT FROM AUTHOR]

Absence of (complex) zeros property is at the heart of the interpolation method developed by Barvinok for designing deterministic approximation algorithms for various graph counting and related problems. An earlier method used for the same problem is one based on the correlation decay property. Remarkably, the classes of graphs for which the two methods apply often coincide or nearly coincide. In this article we show that this is not a coincidence. We establish that if the interpolation method is valid for a family of graphs, then this family exhibits a form of the correlation decay property which is asymptotic strong spatial mixing at superlogarithmic distances. Our proof is based on a certain graph polynomial representation of the associated partition function. This representation is at the heart of the design of the polynomial time algorithms underlying the interpolation method itself. We conjecture that our result holds for all, and not just amenable graphs. Indeed this conjecture was recently confirmed by Regts. See the body of the article for details. [ABSTRACT FROM AUTHOR]

Key time steps selection, i.e., selecting a subset of most representative time steps, is essential for effective and efficient scientific visualization of large time‐varying volume data. In particular, as computer simulations continue to grow in size and complexity, they often generate output that exceeds both the available storage capacity and bandwidth for transferring results to storage, making it indispensable to save only a subset of time steps. At the same time, this subset must be chosen so that it is highly representative, to facilitate post‐processing and reconstruction with high fidelity. The key time steps selection problem is especially challenging in the in situ setting, where we can only process data in one pass in an online streaming fashion, using a small amount of main memory and fast computation. In this paper, we formulate the problem as that of optimal piece‐wise linear interpolation. We first apply a method from numerical linear algebra to compute linear interpolation solutions and their errors in an online streaming fashion. Using that method as a building block, we can obtain a global optimal solution for the piece‐wise linear interpolation problem via a standard dynamic programming (DP) algorithm. However, this approach needs to process the time steps in multiple passes and is too slow for the in situ setting. To address this issue, we introduce a novel approximation algorithm, which processes time steps in one pass in an online streaming fashion, with very efficient computing time and main memory space both in theory and in practice. The algorithm is suitable for the in situ setting. Moreover, we prove that our algorithm, which is based on a greedy update rule, has strong theoretical guarantees on the approximation quality and the number of time steps stored. To the best of our knowledge, this is the first algorithm suitable for in situ key time steps selection with such theoretical guarantees, and is the main contribution of this paper. Experiments demonstrate the efficacy of our new techniques. [ABSTRACT FROM AUTHOR]

In the Steiner forest problem, we are given a set of terminal pairs and need to find the minimum cost subgraph that connects each of the terminal pairs together. Motivated by the recent work on greedy approximation algorithms for the Steiner forest, we provide efficient implementations of existing approximation algorithms and conduct a thorough experimental study to characterize their performance. We consider several approximation algorithms: the influential primal‐dual 2‐approximation algorithm due to Agrawal, Klein, and Ravi, the greedy algorithm due to Gupta and Kumar, and a randomized algorithm based on probabilistic approximation by tree metrics. We also consider the simplest heuristic greedy algorithm for the problem, which picks the closest unconnected pair of terminals and connects it using the shortest path between the terminals in the current graph. To characterize the performance of the algorithms, we created a new library with more than one thousand Steiner forest problem instances and conducted an extensive experimental analysis on those instances. Our analysis reveals that for the majority of instances the primal‐dual algorithm is the fastest among all the algorithms considered here, and obtains solutions that are very close to the optimal solutions obtained by solving the integer program formulation of the problem. [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]

In this paper, we suggest basing the development of classification methods on traditional techniques but approximating them in whole or in part with artificial neural networks (ANNs). Compared to a direct ANN approach, the underlying traditional method is often easier to analyse. Classification failures can be better understood and corrected for, while at the same time faster execution can be obtained due to the parallel ANN structure. Furthermore, such a two‐step design philosophy partly eliminates the 'guesswork' associated with the design of ANNs. The expected gain is thus that the benefits from the traditional field, and the ANN field can be obtained by combining the best features from both fields. We illustrate our approach by working through an explicit example, namely, a Nearest Neighbour classifier applied to a subset of the MNIST database of handwritten digits. Two different approaches are discussed for how to translate the traditional method into an ANN. The first approach is based on a constructive implementation which directly reflects the original algorithm. The second approach uses ANNs to approximate the whole, or part of, the original method. An important part of the approach is to show how improvements can be introduced. In line with the presented philosophy, this is done by extending the traditional method in several ways followed by ANN approximation of the modified algorithms. The extensions are based on a windowed version of the nearest neighbour algorithm. We show that the improvements carry over to the ANN implementations. We further investigate the stability of the solutions by modifying the training set. It is shown that the errors do not change significantly. This also holds true for the ANN approximations providing confidence that the two‐step strategy is robust. [ABSTRACT FROM AUTHOR]

The global routing network is the backbone of the Internet. However, it is quite vulnerable to attacks that cause major disruptions or routing manipulations. Prior related works have visualized routing path changes with node link diagrams, but it requires strong domain expertise to understand if a routing change between autonomous systems is suspicious. Geographic visualization has an advantage over conventional node‐link diagrams by helping uncover such suspicious routes as the user can immediately see if a path is the shortest path to the target or an unreasonable detour. In this paper, we present ProBGP, a web‐based progressive approach to visually analyze BGP update routes. We created a novel progressive data processing algorithm for the geographic approximation of autonomous systems and combined it with a progressively updating visualization. While the newest log data is continuously loaded, our approach also allows querying the entire log recordings since 1999. We present the usefulness of our approach with a real use case of a major route leak from June 2019. We report on multiple interviews with domain experts throughout the development. Finally, we evaluated our algorithm quantitatively against a public peering database and qualitatively against AS network maps. [ABSTRACT FROM AUTHOR]

Summary: High‐dimensionality reduction techniques are very important tools in machine learning and data mining. The method of generalized low rank approximations of matrices (GLRAM) is a popular technique for dimensionality reduction and image compression. However, it suffers from heavily computational overhead in practice, especially for data with high dimension. In order to reduce the cost of this algorithm, we propose a randomized GLRAM algorithm based on randomized singular value decomposition (RSVD). The theoretical contribution of our work is threefold. First, we discuss the decaying property of singular values of the matrices during iterations of the GLRAM algorithm, and provide a target rank required in the RSVD process from a theoretical point of view. Second, we establish the relationship between the reconstruction errors generated by the standard GLRAM algorithm and the randomized GLRAM algorithm. It is shown that the reconstruction errors generated by the former and the latter are comparable, even if the solutions are computed inaccurately during iterations. Third, the convergence of the randomized GLRAM algorithm is investigated. Numerical experiments on some real‐world data sets illustrate the superiority of our proposed algorithm over its original counterpart and some state‐of‐the‐art GLRAM‐type algorithms. [ABSTRACT FROM AUTHOR]

In this article, we study an efficient approximation algorithm for the Schrödinger–Possion system arising in the resonant tunneling diode (RTD) structure. By following the classical Gummel iterative procedure, we first decouple this nonlinear system and prove the convergence of the iteration method. Then via introducing a novel spatial discrete method, we solve efficiently the decoupled Schrödinger and Possion equations with discontinuous coefficients on no‐uniform meshes at each iterative step, respectively. Compared with the traditional ones, the algorithm considered here not only has a less restriction on the discrete mesh, but also is more accurate. Finally, some numerical experiments are shown to confirm the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

For a given set X of points in the plane, we consider the problem of constructing a 2‐vertex‐connected network spanning X and at most k additional Steiner points such that the length of the longest edge (the so‐called bottleneck) of the network is minimized. When one introduces a constraint on the network specifying that all Steiner points must be of degree 2 the problem remains NP‐complete but becomes fixed parameter tractable with respect to k. We prove this by presenting an algorithm which solves the degree‐2 bounded problem optimally in a time of O(n4k62k), where n = |X|. We also present a simple 3‐approximation algorithm for the degree‐2 bounded problem and show that the bottleneck length of an optimal solution to the degree‐2 bounded problem is at most twice the bottleneck length when degree is not bounded. [ABSTRACT FROM AUTHOR]

We answer a question on group connectivity suggested by Jaeger et al [J. Combin. Theory, Ser. B 56 (1992), pp. 165–182]: we find that Z22‐connectivity does not imply Z4‐connectivity, neither vice versa. We use a computer to find the graphs certifying this and to verify their properties using a nontrivial enumerative algorithm (and we also use an independent implementation of a straightforward algorithm to double‐check our results). We provide a simple construction to provide an infinite family of examples. While the graphs we found are small (the largest has 15 vertices and 21 edges), a computer‐free approach remains elusive. [ABSTRACT FROM AUTHOR]

We consider the salvo policy problem, in which there are k moments, called salvos, at which we can fire multiple missiles simultaneously at an incoming object. Each salvo is characterized by a probability pi: the hit probability of a single missile. After each salvo, we can assess whether the incoming object is still active. If it is, we fire the missiles assigned to the next salvo. In the salvo policy problem, the goal is to assign at most n missiles to salvos in order to minimize the expected number of missiles used. We consider three problem versions. In Gould's version, we have to assign all n missiles to salvos. In the Big Bomb version, a cost of B is incurred when all salvo's are unsuccessful. Finally, we consider the Quota version in which the kill probability should exceed some quota Q. We discuss the computational complexity and the approximability of these problem versions. In particular, we show that Gould's version and the Big Bomb version admit pseudopolynomial time exact algorithms and fully polynomial time approximation schemes. We also present an iterative approximation algorithm for the Quota version, and show that a related problem is NP‐complete. [ABSTRACT FROM AUTHOR]

Atmospheric moist available potential energy (MAPE) has traditionally been defined as the potential energy of a moist atmosphere relative to that of the adiabatically sorted reference state defining a global potential energy minimum. Although the Munkres algorithm can in principle find such a reference state exactly, its computational cost has prompted much interest in developing heuristic methods for computing MAPE in practice. Comparisons of the accuracy of such approximate algorithms have so far been limited to a small number of test cases; this work provides an assessment of the performance of the algorithms across a wide range of atmospheric soundings, in two different locations. We determine that the divide‐and‐conquer algorithm is the best suited to practical application, but suffers from the previously unexplored shortcoming that it can produce a reference state with higher potential energy than the actual state, resulting in a negative value of MAPE. Additionally, we show that it is possible to construct an algorithm exploiting a previously derived theoretical expression linking MAPE to Convective Available Potential Energy (CAPE). This approach has a similar accuracy to existing approximate sorting algorithms, whilst providing greater insight into the physical source of MAPE. In light of these results, we discuss possible ways to improve on the construction of Available Potential Energy (APE) theory for a moist atmosphere. Moist Available Potential Energy (MAPE) describes the energy available to atmospheric motion by taking the difference between the total potential energies (TPE) of the actual atmospheric state and a reference state. Reference states have previously been computed using sorting algorithms that approximate the reversible adiabatic rearrangement minimizing the TPE. However, we show that these algorithms regularly produce a reference state with even higher TPE than the actual state and therefore alternative approaches not based on sorting parcels are physically preferable. [ABSTRACT FROM AUTHOR]

Abstract: We consider the problem of efficiently scheduling deliveries by an uncapacitated courier from a central location under online arrivals. We consider both adversary‐controlled and Poisson arrival processes. In the adversarial setting we provide a randomized (3βΔ/2δ − 1)‐competitive algorithm, where β is the approximation ratio of the traveling salesman problem, δ is the minimum distance between the central location and any customer, and Δ is the length of the optimal traveling salesman tour overall customer locations and the central location. We provide instances showing that this analysis is tight. We also prove a 1 + 0.271Δ/δ lower‐bound on the competitive ratio of any algorithm in this setting. In the Poisson setting, we relax our assumption of deterministic travel times by assuming that travel times are distributed with a mean equal to the excursion length. We prove that optimal policies in this setting follow a threshold structure and describe this structure. For the half‐line metric space we bound the performance of the randomized algorithm in the Poisson setting, and show through numerical experiments that the performance of the algorithm is often much better than this bound. [ABSTRACT FROM AUTHOR]

The coordination arrival problems of first-order multi-agent systems with the arriving structure and the time structure requirements are considered for the cases with no obstacle and obstacle. To describe the distributed coordination arrival problems, we first introduce needed definitions, such as coordination arrival, threat point, and arrival structure. By selecting the estimated value of the arriving time of the agent as variable, we then develop a central estimating algorithm, which is used to construct the arriving protocols. Based on the estimating algorithm, we build and analyze coordination arriving protocols for the proposed coordination arrival problems. Several simulation examples are presented to validate the proposed algorithms. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The concept of mono-component is widely used in nonstationary signal processing and time-frequency analysis. In this paper, we construct several classes of complete rational function systems in the Hardy space, whose boundary values are mono-components. Then, we propose a best approximation algorithm (BAA) based on optimal selections of two parameters in the orthonormal bases according to the approximation error. Effectiveness of BAA is evaluated by comparison experiments with the classical Fourier decomposition algorithm. It is also shown that BAA has promising results for filtering out noises and dealing with real-world signals. Copyright © 2014 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Sparse principal components analysis (SPCA) is a technique for finding principal components with a small number of non-zero loadings. Our contribution to this methodology is twofold. First we derive the sparse solutions that minimise the least squares criterion subject to sparsity requirements. Second, recognising that sparsity is not the only requirement for achieving simplicity, we suggest a backward elimination algorithm that computes sparse solutions with large loadings. This algorithm can be run without specifying the number of non-zero loadings in advance. It is also possible to impose the requirement that a minimum amount of variance be explained by the components. We give thorough comparisons with existing SPCA methods and present several examples using real datasets. [ABSTRACT FROM AUTHOR]

In this work we propose new randomized rounding algorithms for matroid intersection and matroid base polytopes. We prove concentration inequalities for polynomial objective functions and constraints that has numerous applications and can be used in approximation algorithms for Minimum Quadratic Spanning Tree, Unrelated Parallel Machines Scheduling and scheduling with time windows and nonlinear objectives. We also show applications related to Constraint Satisfaction and dense polynomial optimization. [ABSTRACT FROM AUTHOR]

We consider the maximum flow problem with minimum quantities (MFPMQ), which is a variant of the maximum flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound (a minimum quantity), which may depend on the arc. This problem has recently been shown to be weakly NP -complete even on series-parallel graphs. In this article, we provide further complexity and approximability results for MFPMQ and several special cases. We first show that it is strongly NP -hard to approximate MFPMQ on general graphs (and even bipartite graphs) within any positive factor. On series-parallel graphs, however, we present a pseudo-polynomial time dynamic programming algorithm for the problem. We then study the case that the minimum quantity is the same for each arc in the network and show that, under this restriction, the problem is still weakly NP -complete on general graphs, but can be solved in strongly polynomial time on series-parallel graphs. On general graphs, we present a \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}(2-\frac{1}{\lambda})\end{align*}\end{document} -approximation algorithm for this case, where λ denotes the common minimum quantity of all arcs. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013 [ABSTRACT FROM AUTHOR]

The analysis of computationally cheap algorithms to approximate the infimum of optimal control problems with discrete‐valued controls has been improved in recent literature. The overall method is often referred to as combinatorial integral approximation decomposition and the algorithms are often referred to as rounding algorithms. The studied algorithms have in common that they seek to minimize or at least bound a quantity called integrated control deviation. The algorithms operate on a grid (often called rounding grid) and the integrated control deviation vanishes when the grid constant of the grid on tends to zero. Assuming a suitable spatial coherence property of the grid refinement implies weak∗ convergence of the computed controls in L∞. When the integer optimal control problem features additional pointwise mixed state‐control constraints, the aforementioned rounding algorithms cannot be applied directly. There exist examples for which the observed infeasibility of the constraint after applying the algorithms does not vanish in an L∞‐sense when the grid constant is driven to zero. While modifications of the algorithms exist that resolve this problem, the asymptotics of the infeasibility without those modifications have not been analyzed so far. This work closes this gap in the existing literature and we show that the infeasibility vanishes in a pointwise almost everywhere sense. [ABSTRACT FROM AUTHOR]

Summary: We study the problem of executing an application represented by a precedence task graph on a parallel machine composed of standard computing cores and accelerators. Both off‐line and on‐line settings are addressed by proposing generic scheduling approaches. In the first case, we establish strong lower bounds on the worst‐case performance of a known approach based on Linear Programming and replace the greedy List Scheduling policy used in this approach by a better task ordering. Although this modification leads to the same approximability guarantees, it performs much better in practice. We also extend this algorithm to more types of computing units, achieving an approximation ratio which depends on the number of different types. In the on‐line case, tasks arrive in any order which respects the precedence relations and the scheduler has to take irrevocable decisions about their allocation and execution. We propose the first on‐line scheduling algorithm taking into account precedences, which is based on adequate rules for selecting the type of processor where to allocate the tasks. Finally, all the previous algorithms have been experimented on a large number of simulations built on actual libraries, assessing their good practical behavior with respect to the state‐of‐the‐art solutions and baseline algorithms. [ABSTRACT FROM AUTHOR]

The table of contents for the Volume 48, Number 2, March 2016 issue of the periodical "Random Structures & Algorithms" is presented.