ALBERT

Beschreibung: In this survey paper, we review various concepts of graph density, as well as associated theorems and algorithms. Our goal is motivated by the fact that, in many applications, it is a key algorithmic task to extract a densest subgraph from an input graph, according to some appropriate definition of graph density. While this problem has been the subject of active research for over half of a century, with many proposed variants and solutions, new results still continuously emerge in the literature. This shows both the importance and the richness of the subject. We also identify some interesting open problems in the field.

Beschreibung: The skyline query and its variant queries are useful functions in the early stages of a knowledge-discovery processes. The skyline query and its variant queries select a set of important objects, which are better than other common objects in the dataset. In order to handle big data, such knowledge-discovery queries must be computed in parallel distributed environments. In this paper, we consider an efficient parallel algorithm for the “K-skyband query” and the “top-k dominating query”, which are popular variants of skyline query. We propose a method for computing both queries simultaneously in a parallel distributed framework called MapReduce, which is a popular framework for processing “big data” problems. Our extensive evaluation results validate the effectiveness and efficiency of the proposed algorithm on both real and synthetic datasets.

Beschreibung: A generalization of Ding’s construction is proposed that employs as a defining set the collection of the sth powers ( s ≥ 2 ) of all nonzero elements in G F ( p m ) , where p ≥ 2 is prime. Some of the resulting codes are optimal or near-optimal and include projective codes over G F ( 4 ) that give rise to optimal or near optimal quantum codes. In addition, the codes yield interesting combinatorial structures, such as strongly regular graphs and block designs.

Beschreibung: Balanced partitioning is often a crucial first step in solving large-scale graph optimization problems, for example, in some cases, a big graph can be chopped into pieces that fit on one machine to be processed independently before stitching the results together, leading to certain suboptimality from the interaction among different pieces. In other cases, links between different parts may show up in the running time and/or network communications cost, hence the desire to have small cut size. We study a distributed balanced-partitioning problem where the goal is to partition the vertices of a given graph into k pieces so as to minimize the total cut size. Our algorithm is composed of a few steps that are easily implementable in distributed computation frameworks such as MapReduce. The algorithm first embeds nodes of the graph onto a line, and then processes nodes in a distributed manner guided by the linear embedding order. We examine various ways to find the first embedding, for example, via a hierarchical clustering or Hilbert curves. Then we apply four different techniques including local swaps, and minimum cuts on the boundaries of partitions, as well as contraction and dynamic programming. As our empirical study, we compare the above techniques with each other, and also to previous work in distributed graph algorithms, for example, a label-propagation method, FENNEL and Spinner. We report our results both on a private map graph and several public social networks, and show that our results beat previous distributed algorithms: For instance, compared to the label-propagation algorithm, we report an improvement of 15–25% in the cut value. We also observe that our algorithms admit scalable distributed implementation for any number of partitions. Finally, we explain three applications of this work at Google: (1) Balanced partitioning is used to route multi-term queries to different replicas in Google Search backend in a way that reduces the cache miss rates by ≈ 0.5 % , which leads to a double-digit gain in throughput of production clusters. (2) Applied to the Google Maps Driving Directions, balanced partitioning minimizes the number of cross-shard queries with the goal of saving in CPU usage. This system achieves load balancing by dividing the world graph into several “shards”. Live experiments demonstrate an ≈ 40 % drop in the number of cross-shard queries when compared to a standard geography-based method. (3) In a job scheduling problem for our data centers, we use balanced partitioning to evenly distribute the work while minimizing the amount of communication across geographically distant servers. In fact, the hierarchical nature of our solution goes well with the layering of data center servers, where certain machines are closer to each other and have faster links to one another.

Beschreibung: Analyzing the structure of a social network helps in gaining insights into interactions and relationships among users while revealing the patterns of their online behavior. Network centrality is a metric of importance of a network node in a network, which allows revealing the structural patterns and morphology of networks. We propose a distributed computing approach for the calculation of network centrality value for each user using the MapReduce approach in the Hadoop platform, which allows faster and more efficient computation as compared to the conventional implementation. A distributed approach is scalable and helps in efficient computations of large-scale datasets, such as social network data. The proposed approach improves the calculation performance of degree centrality by 39.8%, closeness centrality by 40.7% and eigenvalue centrality by 41.1% using a Twitter dataset.

Beschreibung: Deep neural networks are successful learning tools for building nonlinear models. However, a robust deep learning-based classification model needs a large dataset. Indeed, these models are often unstable when they use small datasets. To solve this issue, which is particularly critical in light of the possible clinical applications of these predictive models, researchers have developed approaches such as virtual sample generation. Virtual sample generation significantly improves learning and classification performance when working with small samples. The main objective of this study is to evaluate the ability of the proposed virtual sample generation to overcome the small sample size problem, which is a feature of the automated detection of a neurodevelopmental disorder, namely autism spectrum disorder. Results show that our method enhances diagnostic accuracy from 84%–95% using virtual samples generated on the basis of five actual clinical samples. The present findings show the feasibility of using the proposed technique to improve classification performance even in cases of clinical samples of limited size. Accounting for concerns in relation to small sample sizes, our technique represents a meaningful step forward in terms of pattern recognition methodology, particularly when it is applied to diagnostic classifications of neurodevelopmental disorders. Besides, the proposed technique has been tested with other available benchmark datasets. The experimental outcomes showed that the accuracy of the classification that used virtual samples was superior to the one that used original training data without virtual samples.

Beschreibung: Parameterized complexity theory has led to a wide range of algorithmic breakthroughs within the last few decades, but the practicability of these methods for real-world problems is still not well understood. We investigate the practicability of one of the fundamental approaches of this field: dynamic programming on tree decompositions. Indisputably, this is a key technique in parameterized algorithms and modern algorithm design. Despite the enormous impact of this approach in theory, it still has very little influence on practical implementations. The reasons for this phenomenon are manifold. One of them is the simple fact that such an implementation requires a long chain of non-trivial tasks (as computing the decomposition, preparing it, …). We provide an easy way to implement such dynamic programs that only requires the definition of the update rules. With this interface, dynamic programs for various problems, such as 3-coloring, can be implemented easily in about 100 lines of structured Java code. The theoretical foundation of the success of dynamic programming on tree decompositions is well understood due to Courcelle’s celebrated theorem, which states that every MSO-definable problem can be efficiently solved if a tree decomposition of small width is given. We seek to provide practical access to this theorem as well, by presenting a lightweight model checker for a small fragment of MSO 1 (that is, we do not consider “edge-set-based” problems). This fragment is powerful enough to describe many natural problems, and our model checker turns out to be very competitive against similar state-of-the-art tools.

Beschreibung: Let V be a finite set of positive integers with sum equal to a multiple of the integer b . When does V have a partition into b parts so that all parts have equal sums? We develop algorithmic constructions which yield positive, albeit incomplete, answers for the following classes of set V , where n is a given positive integer: (1) an initial interval { a ∈ ℤ + : a ≤ n } ; (2) an initial interval of primes { p ∈ ℙ : p ≤ n } , where ℙ is the set of primes; (3) a divisor set { d ∈ ℤ + : d | n } ; (4) an aliquot set { d ∈ ℤ + : d | n ,   d 〈 n } . Open general questions and conjectures are included for each of these classes.

Beschreibung: The blockchain technique is becoming more and more popular due to its advantages such as stability and dispersed nature. This is an idea based on blockchain activity paradigms. Another important field is machine learning, which is increasingly used in practice. Unfortunately, the training or overtraining artificial neural networks is very time-consuming and requires high computing power. In this paper, we proposed using a blockchain technique to train neural networks. This type of activity is important due to the possible search for initial weights in the network, which affect faster training, due to gradient decrease. We performed the tests with much heavier calculations to indicate that such an action is possible. However, this type of solution can also be used for less demanding calculations, i.e., only a few iterations of training and finding a better configuration of initial weights.

Beschreibung: In this study, we address the problem of compaction of Church numerals. Church numerals are unary representations of natural numbers on the scheme of lambda terms. We propose a novel decomposition scheme from a given natural number into an arithmetic expression using tetration, which enables us to obtain a compact representation of lambda terms that leads to the Church numeral of the natural number. For natural number n, we prove that the size of the lambda term obtained by the proposed method is O ( ( slog 2 n ) ( log n / log log n ) ) . Moreover, we experimentally confirmed that the proposed method outperforms binary representation of Church numerals on average, when n is less than approximately 10,000.

Beschreibung: In the vehicle routing problem with simultaneous pickup and delivery (VRPSPD), customers demanding both delivery and pickup operations have to be visited once by a single vehicle. In this work, we propose a fast randomized algorithm using a nearest neighbor strategy to tackle an extension of the VRPSPD in which the fleet of vehicles is heterogeneous. This variant is an NP-hard problem, which in practice makes it impossible to be solved to proven optimality for large instances. To evaluate the proposal, we use benchmark instances from the literature and compare our results to those obtained by a state-of-the-art algorithm. Our approach presents very competitive results, not only improving several of the known solutions, but also running in a shorter time.

Beschreibung: Nowadays, the amount of digitally available information has tremendously grown, with real-world data graphs outreaching the millions or even billions of vertices. Hence, community detection, where groups of vertices are formed according to a well-defined similarity measure, has never been more essential affecting a vast range of scientific fields such as bio-informatics, sociology, discrete mathematics, nonlinear dynamics, digital marketing, and computer science. Even if an impressive amount of research has yet been published to tackle this NP-hard class problem, the existing methods and algorithms have virtually been proven inefficient and severely unscalable. In this regard, the purpose of this manuscript is to combine the network topology properties expressed by the loose similarity and the local edge betweenness, which is a currently proposed Girvan–Newman’s edge betweenness measure alternative, along with the intrinsic user content information, in order to introduce a novel and highly distributed hybrid community detection methodology. The proposed approach has been thoroughly tested on various real social graphs, roundly compared to other classic divisive community detection algorithms that serve as baselines and practically proven exceptionally scalable, highly efficient, and adequately accurate in terms of revealing the subjacent network hierarchy.

Beschreibung: Herein, robust pole placement controller design for linear uncertain discrete time dynamic systems is addressed. The adopted approach uses the so called “D regions” where the closed loop system poles are determined to lie. The discrete time pole regions corresponding to the prescribed damping of the resulting closed loop system are studied. The key issue is to determine the appropriate convex approximation to the originally non-convex discrete-time system pole region, so that numerically efficient robust controller design algorithms based on Linear Matrix Inequalities (LMI) can be used. Several alternatives for relatively simple inner approximations and their corresponding LMI descriptions are presented. The developed LMI region for the prescribed damping can be arbitrarily combined with other LMI pole limitations (e.g., stability degree). Simple algorithms to calculate the matrices for LMI representation of the proposed convex pole regions are provided in a concise way. The results and their use in a robust controller design are illustrated on a case study of a laboratory magnetic levitation system.

Beschreibung: The objective of the cell suppression problem (CSP) is to protect sensitive cell values in tabular data under the presence of linear relations concerning marginal sums. Previous algorithms for solving CSPs ensure that every sensitive cell has enough uncertainty on its values based on the interval width of all possible values. However, we find that every deterministic CSP algorithm is vulnerable to an adversary who possesses the knowledge of that algorithm. We devise a matching attack scheme that narrows down the ranges of sensitive cell values by matching the suppression pattern of an original table with that of each candidate table. Our experiments show that actual ranges of sensitive cell values are significantly narrower than those assumed by the previous CSP algorithms.

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉We consider a general load balancing problem on parallel machines. Our machine environment in particular generalizes the standard models of identical machines, and the model of uniformly related machines, as well as machines with a constant number of types, and machines with activation costs. The objective functions that we consider contain in particular the makespan objective and the minimization of the 〈span〉 〈span〉\(\ell _p\)〈/span〉 〈/span〉-norm of the vector of loads of the machines, and each case allows the possibility of job rejection. We consider this general model and design an efficient polynomial time approximation scheme (EPTAS) that applies for all its previously-studied special cases. This EPTAS improves the current best approximation scheme for some of these cases where only a polynomial time approximation scheme was known into an EPTAS.〈/p〉

Beschreibung: There are two main challenges in wireless multimedia sensors networks: energy constraints and providing DiffServ. In this paper, a joint flow control, routing, scheduling, and power control scheme based on a Lyapunov optimization framework is proposed to increase network lifetime and scheduling fairness. For an adaptive distribution of transmission opportunities, a differentiated queueing services (DQS) scheme is adopted for maintaining data queues. In the Lyapunov function, different types of queues are normalized for a unified dimension. To prolong network lifetime, control coefficients are designed according to the characteristics of the wireless sensor networks. The power control problem is proved to be a convex optimization problem and two optimal algorithms are discussed. Simulation results show that, compared with existing schemes, the proposed scheme can achieve a better trade-off between QoS performances and network lifetime. The simulation results also show that the scheme utilizing the distributed media access control scheme in scheduling performs best in the transmission of real-time services.

Beschreibung: We propose in this paper a two-phase approach that decomposes the process of solving the three-dimensional single Container Loading Problem (CLP) into subsequent tasks: (i) the generation of blocks of boxes and (ii) the loading of blocks into the container. The first phase is deterministic, and it is performed by means of constructive algorithms from the literature. The second phase is non-deterministic, and it is performed with the use of Generate-and-Solve (GS), a problem-independent hybrid optimization framework based on problem instance reduction that combines a metaheuristic with an exact solver. Computational experiments performed on benchmark instances indicate that our approach presents competitive results compared to those found by state-of-the-art algorithms, particularly for problem instances consisting of a few types of boxes. In fact, we present new best solutions for classical instances from groups BR1 and BR2.

Beschreibung: In this paper, a novel constraint-following control for uncertain robot manipulators that is inspired by analytical dynamics is developed. The motion can be regarded as external constraints of the system. However, it is not easy to obtain explicit equations for dynamic modeling of constrained systems. For a multibody system subject to motion constraints, it is a common practice to introduce Lagrange multipliers, but using these to obtain explicit dynamical equations is a very difficult task. In order to obtain such equations more simply, motion constraints are handled here using the Udwadia-Kalaba equation(UKE). Then, considering real-life robot manipulators are usually uncertain(but bounded), by using continuous controllers compensate for the uncertainties. No linearizations/approximations of the robot manipulators systems are made throughout, and the tracking errors are bounds. A redundant manipulator of the SCARA type as the example to illustrates the methodology. Numerical results are demonstrates the simplicity and ease of implementation of the methodology.

Beschreibung: To improve the overall accuracy of tidal forecasting and ameliorate the low accuracy of single harmonic analysis, this paper proposes a combined tidal forecasting model based on harmonic analysis and autoregressive integrated moving average–support vector regression (ARIMA-SVR). In tidal analysis, the resultant tide can be considered as a superposition of the astronomical tide level and the non-astronomical tidal level, which are affected by the tide-generating force and environmental factors, respectively. The tidal data are de-noised via wavelet analysis, and the astronomical tide level is subsequently calculated via harmonic analysis. The residual sequence generated via harmonic analysis is used as the sample dataset of the non-astronomical tidal level, and the tidal height of the system is calculated by the ARIMA-SVR model. Finally, the tidal values are predicted by linearly summing the calculated results of both systems. The simulation results were validated against the measured tidal data at the tidal station of Bay Waveland Yacht Club, USA. By considering the residual non-astronomical tide level effects (which are ignored in traditional harmonic analysis), the combined model improves the accuracy of tidal prediction. Moreover, the combined model is feasible and efficient.

Beschreibung: Software defect prediction is an important means to guarantee software quality. Because there are no sufficient historical data within a project to train the classifier, cross-project defect prediction (CPDP) has been recognized as a fundamental approach. However, traditional defect prediction methods use feature attributes to represent samples, which cannot avoid negative transferring, may result in poor performance model in CPDP. This paper proposes a multi-source cross-project defect prediction method based on dissimilarity space (DM-CPDP). This method not only retains the original information, but also obtains the relationship with other objects. So it can enhances the discriminant ability of the sample attributes to the class label. This method firstly uses the density-based clustering method to construct the prototype set with the cluster center of samples in the target set. Then, the arc-cosine kernel is used to calculate the sample dissimilarities between the prototype set and the source domain or the target set to form the dissimilarity space. In this space, the training set is obtained with the earth mover’s distance (EMD) method. For the unlabeled samples converted from the target set, the k-Nearest Neighbor (KNN) algorithm is used to label those samples. Finally, the model is learned from training data based on TrAdaBoost method and used to predict new potential defects. The experimental results show that this approach has better performance than other traditional CPDP methods.

Beschreibung: Link prediction is a task predicting whether there is a link between two nodes in a network. Traditional link prediction methods that assume handcrafted features (such as common neighbors) as the link’s formation mechanism are not universal. Other popular methods tend to learn the link’s representation, but they cannot represent the link fully. In this paper, we propose Edge-Nodes Representation Neural Machine (ENRNM), a novel method which can learn abundant topological features from the network as the link’s representation to promote the formation of the link. The ENRNM learns the link’s formation mechanism by combining the representation of edge and the representations of nodes on the two sides of the edge as link’s full representation. To predict the link’s existence, we train a fully connected neural network which can learn meaningful and abundant patterns. We prove that the features of edge and two nodes have the same importance in link’s formation. Comprehensive experiments are conducted on eight networks, experiment results demonstrate that the method ENRNM not only exceeds plenty of state-of-the-art link prediction methods but also performs very well on diverse networks with different structures and characteristics.

Beschreibung: The conveyor belt is an indispensable piece of conveying equipment for a mine whose deviation caused by roller sticky material and uneven load distribution is the most common failure during operation. In this paper, a real-time conveyor belt detection algorithm based on a multi-scale feature fusion network is proposed, which mainly includes two parts: the feature extraction module and the deviation detection module. The feature extraction module uses a multi-scale feature fusion network structure to fuse low-level features with rich position and detail information and high-level features with stronger semantic information to improve network detection performance. Depthwise separable convolutions are used to achieve real-time detection. The deviation detection module identifies and monitors the deviation fault by calculating the offset of conveyor belt. In particular, a new weighted loss function is designed to optimize the network and to improve the detection effect of the conveyor belt edge. In order to evaluate the effectiveness of the proposed method, the Canny algorithm, FCNs, UNet and Deeplab v3 networks are selected for comparison. The experimental results show that the proposed algorithm achieves 78.92% in terms of pixel accuracy (PA), and reaches 13.4 FPS (Frames per Second) with the error of less than 3.2 mm, which outperforms the other four algorithms.

Beschreibung: Aimed at the one-to-one certification problem of unsteady state iris at different shooting times, a multi-algorithm parallel integration general model structure is proposed in this paper. The iris in the lightweight constrained state affected by defocusing, deflection, and illumination is taken as the research object, the existing algorithms are combined into the model structure effectively, and a one-to-one certification algorithm for lightweight constrained state unsteady iris was designed based on multi-algorithm integration and maximum trusted decision. In this algorithm, a sufficient number of iris internal feature points from the unstable state texture were extracted as effective iris information through the image processing layer composed of various filtering processing algorithms, thereby eliminating defocused interference. In the feature recognition layer, iris deflection interference was excluded by the improved methods of Gabor and Hamming and Haar and BP for the stable features extracted by the image processing layer, and two certification results were obtained by means of parallel recognition. The correct number of certifications for an algorithm under a certain lighting condition were counted. The method with the most correct number was set as the maximum trusted method under this lighting condition, and the results of the maximum trusted method were taken as the final decision, thereby eliminating the effect of illumination. Experiments using the JLU and CASIA iris libraries under the prerequisites in this paper show that the correct recognition rate of the algorithm can reach a high level of 98% or more, indicating that the algorithm can effectively improve the accuracy of the one-to-one certification of lightweight constrained state unsteady iris. Compared with the latest architecture algorithms, such as CNN and deep learning, the proposed algorithm is more suitable for the prerequisites presented in this paper, which has good environmental inclusiveness and can better improve existing traditional algorithms’ effectiveness through the design of a parallel integration model structure.

Beschreibung: The development of robotic applications for agricultural environments has several problems which are not present in the robotic systems used for indoor environments. Some of these problems can be solved with an efficient navigation system. In this paper, a new system is introduced to improve the navigation tasks for those robots which operate in agricultural environments. Concretely, the paper focuses on the problem related to the autonomous mapping of agricultural parcels (i.e., an orange grove). The map created by the system will be used to help the robots navigate into the parcel to perform maintenance tasks such as weed removal, harvest, or pest inspection. The proposed system connects to a satellite positioning service to obtain the real coordinates where the robotic system is placed. With these coordinates, the parcel information is downloaded from an online map service in order to autonomously obtain a map of the parcel in a readable format for the robot. Finally, path planning is performed by means of Fast Marching techniques using the robot or a team of two robots. This paper introduces the proof-of-concept and describes all the necessary steps and algorithms to obtain the path planning just from the initial coordinates of the robot.

Beschreibung: The characteristic of the satellite repeat shift time can reflect the status of the satellite operation, and is also one of the key factors of the sidereal filtering multipath correction. Although some methods have been developed to calculate the repeat shift time, few efforts have been made to analyze and compare the performance of this feature for the GPS (Global Positioning System), BDS (BeiDou System), and Galileo in depth. Hence, three methods used for calculating the repeat shift time are presented, and used to compare and analyze the three global systems in depth, named the broadcast ephemeris method (BEM), correlation coefficient method (CCM), and aspect repeat time method (ARTM). The experiment results show that the repeat shift time of each satellite is different. Also, the difference between the maximum and minimum varies from different systems. The maximum difference is about 25 s for the BDS IGSO (Inclined Geosynchronous Orbit) and the minimum is merely 10 s for the GPS system. Furthermore, for the same satellite, the shift time calculated by the three methods is almost identical, and the maximum difference is only about 7 s between the CCM and the ARTM method for the BDS MEO (Medium Earth Orbit) satellite. Although the repeat shift time is different daily for the same satellite and the same method, the changes are very small. Moreover, in terms of the STD (Standard Deviation) of the BS (between satellites) and MS (mean shift for the same satellite), the GPS system is the best, the performance of the BDS system is medium, and the Galileo performs slightly worse than the GPS and BDS.

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉The parameterised complexity of various consensus string problems (〈span〉Closest String〈/span〉, 〈span〉Closest Substring〈/span〉, 〈span〉Closest String with Outliers〈/span〉) is investigated in a more general setting, i. e., with a bound on the maximum Hamming distance 〈em〉and〈/em〉 a bound on the sum of Hamming distances between solution and input strings. We completely settle the parameterised complexity of these generalised variants of 〈span〉Closest String〈/span〉 and 〈span〉Closest Substring〈/span〉, and partly for 〈span〉Closest String with Outliers〈/span〉; in addition, we answer some open questions from the literature regarding the classical problem variants with only one distance bound. Finally, we investigate the question of polynomial kernels and respective lower bounds.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉Let 〈span〉 〈span〉\(P \subset \mathbb {R}^d\)〈/span〉 〈/span〉 be a set of 〈em〉n〈/em〉 points in 〈em〉d〈/em〉 dimensions such that each point 〈span〉 〈span〉\(p \in P\)〈/span〉 〈/span〉 has an 〈em〉associated radius〈/em〉〈span〉 〈span〉\(r_p 〉 0\)〈/span〉 〈/span〉. The 〈em〉transmission graph〈/em〉〈em〉G〈/em〉 for 〈em〉P〈/em〉 is the directed graph with vertex set 〈em〉P〈/em〉 such that there is an edge from 〈em〉p〈/em〉 to 〈em〉q〈/em〉 if and only if 〈span〉 〈span〉\(|pq| \le r_p\)〈/span〉 〈/span〉, for any 〈span〉 〈span〉\(p, q \in P\)〈/span〉 〈/span〉. A 〈em〉reachability oracle〈/em〉 is a data structure that decides for any two vertices 〈span〉 〈span〉\(p, q \in G\)〈/span〉 〈/span〉 whether 〈em〉G〈/em〉 has a path from 〈em〉p〈/em〉 to 〈em〉q〈/em〉. The quality of the oracle is measured by the space requirement 〈em〉S〈/em〉(〈em〉n〈/em〉), the query time 〈em〉Q〈/em〉(〈em〉n〈/em〉), and the preprocessing time. For transmission graphs of one-dimensional point sets, we can construct in 〈span〉 〈span〉\(O(n \log n)\)〈/span〉 〈/span〉 time an oracle with 〈span〉 〈span〉\(Q(n) = O(1)\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(S(n) = O(n)\)〈/span〉 〈/span〉. For planar point sets, the ratio 〈span〉 〈span〉\(\Psi \)〈/span〉 〈/span〉 between the largest and the smallest associated radius turns out to be an important parameter. We present three data structures whose quality depends on 〈span〉 〈span〉\(\Psi \)〈/span〉 〈/span〉: the first works only for 〈span〉 〈span〉\(\Psi 〈 \sqrt{3}\)〈/span〉 〈/span〉 and achieves 〈span〉 〈span〉\(Q(n) = O(1)\)〈/span〉 〈/span〉 with 〈span〉 〈span〉\(S(n) = O(n)\)〈/span〉 〈/span〉 and preprocessing time 〈span〉 〈span〉\(O(n\log n)\)〈/span〉 〈/span〉; the second data structure gives 〈span〉 〈span〉\(Q(n) = O(\Psi ^3 \sqrt{n})\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(S(n) = O(\Psi ^3 n^{3/2})\)〈/span〉 〈/span〉; the third data structure is randomized with 〈span〉 〈span〉\(Q(n) = O(n^{2/3}\log ^{1/3} \Psi \log ^{2/3} n)\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(S(n) = O(n^{5/3}\log ^{1/3} \Psi \log ^{2/3} n)\)〈/span〉 〈/span〉 and answers queries correctly with high probability.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉We consider the construction of the 〈em〉suffix tree〈/em〉 and the 〈em〉directed acyclic word graph〈/em〉 (〈em〉DAWG〈/em〉) indexing data structures for a collection 〈span〉 〈span〉\(\mathcal {T}\)〈/span〉 〈/span〉 of texts, where a new symbol may be appended to any text in 〈span〉 〈span〉\(\mathcal {T} = \{T_1, \ldots , T_K\}\)〈/span〉 〈/span〉, 〈em〉at any time〈/em〉. This 〈em〉fully-online〈/em〉 scenario, which arises in dynamically indexing multi-sensor data, is a natural generalization of the long solved 〈em〉semi-online〈/em〉 text indexing problem, where texts 〈span〉 〈span〉\(T_1, \ldots , T_{k}\)〈/span〉 〈/span〉 are permanently fixed before the next text 〈span〉 〈span〉\(T_{k+1}\)〈/span〉 〈/span〉 is processed for each 〈em〉k〈/em〉 (〈span〉 〈span〉\(1 \le k 〈 K\)〈/span〉 〈/span〉). We first show that a direct application of Weiner’s right-to-left online construction for the suffix tree of a single text to fully-online multiple texts requires superlinear time. This also means that Blumer et al.’s left-to-right online construction for the DAWG of a single text requires superlinear time in the fully-online setting. We then present our fully-online versions of these algorithms that run in 〈span〉 〈span〉\(O(N \log \sigma )\)〈/span〉 〈/span〉 time and 〈em〉O〈/em〉(〈em〉N〈/em〉) space, where 〈em〉N〈/em〉 is the total length of the texts in 〈span〉 〈span〉\(\mathcal {T}\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(\sigma \)〈/span〉 〈/span〉 is their alphabet size. We then show how to extend Ukkonen’s left-to-right online suffix tree construction to fully-online multiple strings, with the aid of Weiner’s suffix tree for the reversed texts. 〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉〈em〉Stochastic dominance〈/em〉 is a technique for evaluating the performance of online algorithms that provides an intuitive, yet powerful stochastic order between the compared algorithms. When there is a uniform distribution over the request sequences, this technique reduces to 〈em〉bijective analysis〈/em〉. These methods have been applied in problems such as paging, list update, bin colouring, routing in array mesh networks, and in connection with Bloom filters, and have often provided a clear separation between algorithms whose performance varies significantly in practice. Despite their appealing properties, the above techniques are quite stringent, in that a relation between online algorithms may be either too difficult to establish analytically, or worse, may not even exist. In this paper, we propose remedies to these shortcomings. Our objective is to make all online algorithms amenable to the techniques of stochastic dominance and bijective analysis. First, we establish sufficient conditions that allow us to prove the bijective optimality of a certain class of algorithms for a wide range of problems; we demonstrate this approach in the context of well-studied online problems such as weighted paging, reordering buffer management, and 2-server on the circle. Second, to account for situations in which two algorithms are incomparable or there is no clear optimum, we introduce the 〈em〉bijective ratio〈/em〉 as a natural extension of (exact) bijective analysis. Our definition readily generalizes to stochastic dominance. This makes it possible to compare two arbitrary online algorithms for an arbitrary online problem. In addition, the bijective ratio is a generalization of the Max/Max ratio (due to Ben-David and Borodin), and allows for the incorporation of other useful techniques such as amortized analysis. We demonstrate the applicability of the bijective ratio to one of the fundamental online problems, namely the continuous 〈em〉k〈/em〉-server problem on metrics such as the line, the circle, and the star. Among other results, we show that the greedy algorithm attains bijective ratios of 〈em〉O〈/em〉(〈em〉k〈/em〉) across these metrics.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉In this article, 〈em〉q〈/em〉-regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor. Each of these terms corresponds to an eigenvalue of the sum of matrices of a linear representation of the sequence; only the eigenvalues of absolute value larger than the joint spectral radius of the matrices contribute terms which grow faster than the error term. The paper has a particular focus on the Fourier coefficients of the periodic fluctuations: they are expressed as residues of the corresponding Dirichlet generating function. This makes it possible to compute them in an efficient way. The asymptotic analysis deals with Mellin–Perron summations and uses two arguments to overcome convergence issues, namely Hölder regularity of the fluctuations together with a pseudo-Tauberian argument. Apart from the very general result, three examples are discussed in more detail:〈/p〉 〈ul〉 〈li〉 〈p〉sequences defined as the sum of outputs written by a transducer when reading a 〈em〉q〈/em〉-ary expansion of the input;〈/p〉 〈/li〉 〈li〉 〈p〉the amount of esthetic numbers in the first 〈em〉N〈/em〉 natural numbers; and〈/p〉 〈/li〉 〈li〉 〈p〉the number of odd entries in the rows of Pascal’s rhombus.〈/p〉 〈/li〉 〈/ul〉 For these examples, very precise asymptotic formulæ are presented. In the latter two examples, prior to this analysis only rough estimates were known.

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉For any integer 〈span〉 〈span〉\(n\ge 1\)〈/span〉 〈/span〉, a 〈em〉middle levels Gray code〈/em〉 is a cyclic listing of all 〈em〉n〈/em〉-element and 〈span〉 〈span〉\((n+1)\)〈/span〉 〈/span〉-element subsets of 〈span〉 〈span〉\(\{1,2,\ldots ,2n+1\}\)〈/span〉 〈/span〉 such that any two consecutive sets differ in adding or removing a single element. The question whether such a Gray code exists for any 〈span〉 〈span〉\(n\ge 1\)〈/span〉 〈/span〉 has been the subject of intensive research during the last 30 years, and has been answered affirmatively only recently [T. Mütze. Proof of the middle levels conjecture. 〈em〉Proc. London Math. Soc.〈/em〉, 112(4):677–713, 2016]. In a follow-up paper [T. Mütze and J. Nummenpalo. An efficient algorithm for computing a middle levels Gray code. 〈em〉ACM Trans. Algorithms〈/em〉, 14(2):29 pp., 2018] this existence proof was turned into an algorithm that computes each new set in the Gray code in time 〈span〉 〈span〉\({{\mathcal {O}}}(n)\)〈/span〉 〈/span〉 on average. In this work we present an algorithm for computing a middle levels Gray code in optimal time and space: each new set is generated in time 〈span〉 〈span〉\({{\mathcal {O}}}(1)\)〈/span〉 〈/span〉 on average, and the required space is 〈span〉 〈span〉\({{\mathcal {O}}}(n)\)〈/span〉 〈/span〉.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉〈span〉QuickXsort〈/span〉 is a highly efficient in-place sequential sorting scheme that mixes Hoare’s 〈span〉Quicksort〈/span〉 algorithm with X, where X can be chosen from a wider range of other known sorting algorithms, like 〈span〉Heapsort〈/span〉, 〈span〉Insertionsort〈/span〉 and 〈span〉Mergesort〈/span〉. Its major advantage is that 〈span〉QuickXsort〈/span〉 can be in-place even if X is not. In this work we provide general transfer theorems expressing the number of comparisons of 〈span〉QuickXsort〈/span〉 in terms of the number of comparisons of X. More specifically, if pivots are chosen as medians of (not too fast) growing size samples, the average number of comparisons of 〈span〉QuickXsort〈/span〉 and X differ only by 〈em〉o〈/em〉(〈em〉n〈/em〉)-terms. For median-of-〈em〉k〈/em〉 pivot selection for some constant 〈em〉k〈/em〉, the difference is a linear term whose coefficient we compute precisely. For instance, median-of-three 〈span〉QuickMergesort〈/span〉 uses at most 〈span〉 〈span〉\(n \lg n - 0.8358n + {\mathcal {O}}(\log n)\)〈/span〉 〈/span〉 comparisons. Furthermore, we examine the possibility of sorting base cases with some other algorithm using even less comparisons. By doing so the average-case number of comparisons can be reduced down to 〈span〉 〈span〉\(n \lg n - 1.4112n + o(n)\)〈/span〉 〈/span〉 for a remaining gap of only 0.0315〈em〉n〈/em〉 comparisons to the known lower bound (while using only 〈span〉 〈span〉\({\mathcal {O}}(\log n)\)〈/span〉 〈/span〉 additional space and 〈span〉 〈span〉\({\mathcal {O}}(n\log n)\)〈/span〉 〈/span〉 time overall). Implementations of these sorting strategies show that the algorithms challenge well-established library implementations like Musser’s 〈span〉Introsort〈/span〉.〈/p〉

Beschreibung: This paper proposes an adaptive backstepping control algorithm for electric braking systems with electromechanical actuators (EMAs). First, the ideal mathematical model of the EMA is established, and the nonlinear factors are analyzed, such as the deformation of the reduction gear. Subsequently, the actual mathematical model of the EMA is rebuilt by combining the ideal model and the nonlinear factors. To realize high performance braking pressure control, the backstepping control method is adopted to address the mismatched uncertainties in the electric braking system, and a radial basis function (RBF) neural network is established to estimate the nonlinear functions in the control system. The experimental results indicate that the proposed braking pressure control strategy can improve the servo performance of the electric braking system. In addition, the hardware-in-loop (HIL) experimental results show that the proposed EMA controller can satisfy the requirements of the aircraft antilock braking systems.

Beschreibung: Objects that possess mass (e.g., automobiles, manufactured items, etc.) translationally accelerate in direct proportion to the force applied scaled by the object’s mass in accordance with Newton’s Law, while the rotational companion is Euler’s moment equations relating angular acceleration of objects that possess mass moments of inertia. Michel Chasles’s theorem allows us to simply invoke Newton and Euler’s equations to fully describe the six degrees of freedom of mechanical motion. Many options are available to control the motion of objects by controlling the applied force and moment. A long, distinguished list of references has matured the field of controlling a mechanical motion, which culminates in the burgeoning field of deterministic artificial intelligence as a natural progression of the laudable goal of adaptive and/or model predictive controllers that can be proven to be optimal subsequent to their development. Deterministic A.I. uses Chasle’s claim to assert Newton’s and Euler’s relations as deterministic self-awareness statements that are optimal with respect to state errors. Predictive controllers (both continuous and sampled-data) derived from the outset to be optimal by first solving an optimization problem with the governing dynamic equations of motion lead to several controllers (including a controller that twice invokes optimization to formulate robust, predictive control). These controllers are compared to each other with noise and modeling errors, and the many figures of merit are used: tracking error and rate error deviations and means, in addition to total mean cost. Robustness is evaluated using Monte Carlo analysis where plant parameters are randomly assumed to be incorrectly modeled. Six instances of controllers are compared against these methods and interpretations, which allow engineers to select a tailored control for their given circumstances. Novel versions of the ubiquitous classical proportional-derivative, “PD” controller, is developed from the optimization statement at the outset by using a novel re-parameterization of the optimal results from time-to-state parameterization. Furthermore, time-optimal controllers, continuous predictive controllers, and sampled-data predictive controllers, as well as combined feedforward plus feedback controllers, and the two degree of freedom controllers (i.e., 2DOF). The context of the term “feedforward” used in this study is the context of deterministic artificial intelligence, where analytic self-awareness statements are strictly determined by the governing physics (of mechanics in this case, e.g., Chasle, Newton, and Euler). When feedforward is combined with feedback per the previously mentioned method (provenance foremost in optimization), the combination is referred to as “2DOF” or two degrees of freedom to indicate the twice invocation of optimization at the genesis of the feedforward and the feedback, respectively. The feedforward plus feedback case is augmented by an online (real time) comparison to the optimal case. This manuscript compares these many optional control strategies against each other. Nominal plants are used, but the addition of plant noise reveals the robustness of each controller, even without optimally rejecting assumed-Gaussian noise (e.g., via the Kalman filter). In other words, noise terms are intentionally left unaddressed in the problem formulation to evaluate the robustness of the proposed method when the real-world noise is added. Lastly, mismodeled plants controlled by each strategy reveal relative performance. Well-anticipated results include the lowest cost, which is achieved by the optimal controller (with very poor robustness), while low mean errors and deviations are achieved by the classical controllers (at the highest cost). Both continuous predictive control and sampled-data predictive control perform well at both cost as well as errors and deviations, while the 2DOF controller performance was the best overall.

Beschreibung: This paper presents a space mission planning tool, which was developed for LEO (Low Earth Orbit) observation satellites. The tool is focused on a two-phase planning strategy with clustering preprocessing and mission planning, where an improved clustering algorithm is applied, and a hybrid algorithm that combines the genetic algorithm with the simulated annealing algorithm (GA–SA) is given and discussed. Experimental simulation studies demonstrate that the GA–SA algorithm with the improved clique partition algorithm based on the graph theory model exhibits higher fitness value and better optimization performance and reliability than the GA or SA algorithms alone.

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉In a recent breakthrough paper Braverman et al. (in: STOC’13, pp 151–160, 〈span〉2013〈/span〉) developed a local characterization for the zero-error information complexity in the two-party model, and used it to compute the exact internal and external information complexity of the 2-bit AND function. In this article, we extend their results on AND function to the multi-party number-in-hand model by proving that the generalization of their protocol has optimal internal and external information cost for certain natural distributions. Our proof has new components, and in particular, it fixes a minor gap in the proof of Braverman et al.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉The Johnson–Lindenstrauss lemma is one of the cornerstone results in dimensionality reduction. A common formulation of it, is that there exists a random linear mapping 〈span〉 〈span〉\(f : {\mathbb {R}}^n \rightarrow {\mathbb {R}}^m\)〈/span〉 〈/span〉 such that for any vector 〈span〉 〈span〉\(x \in {\mathbb {R}}^n\)〈/span〉 〈/span〉, 〈em〉f〈/em〉 preserves its norm to within 〈span〉 〈span〉\((1 {\pm } \varepsilon )\)〈/span〉 〈/span〉 with probability 〈span〉 〈span〉\(1 - \delta \)〈/span〉 〈/span〉 if 〈span〉 〈span〉\(m = \varTheta (\varepsilon ^{-2} \lg (1/\delta ))\)〈/span〉 〈/span〉. Much effort has gone into developing fast embedding algorithms, with the Fast Johnson–Lindenstrauss transform of Ailon and Chazelle being one of the most well-known techniques. The current fastest algorithm that yields the optimal 〈span〉 〈span〉\(m = {\mathcal {O}}(\varepsilon ^{-2}\lg (1/\delta ))\)〈/span〉 〈/span〉 dimensions has an embedding time of 〈span〉 〈span〉\({\mathcal {O}}(n \lg n + \varepsilon ^{-2} \lg ^3 (1/\delta ))\)〈/span〉 〈/span〉. An exciting approach towards improving this, due to Hinrichs and Vybíral, is to use a random 〈span〉 〈span〉\(m \times n\)〈/span〉 〈/span〉 Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in 〈span〉 〈span〉\({\mathcal {O}}(n \lg m)\)〈/span〉 〈/span〉 time. The big question is of course whether 〈span〉 〈span〉\(m = {\mathcal {O}}(\varepsilon ^{-2} \lg (1/\delta ))\)〈/span〉 〈/span〉 dimensions suffice for this technique. If so, this would end a decades long quest to obtain faster and faster Johnson–Lindenstrauss transforms. The current best analysis of the embedding of Hinrichs and Vybíral shows that 〈span〉 〈span〉\(m = {\mathcal {O}}(\varepsilon ^{-2}\lg ^2 (1/\delta ))\)〈/span〉 〈/span〉 dimensions suffice. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exist vectors requiring 〈span〉 〈span〉\(m = \varOmega (\varepsilon ^{-2} \lg ^2 (1/\delta ))\)〈/span〉 〈/span〉 for the Toeplitz approach to work.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉We consider a two-way trading problem, where investors buy and sell a stock whose price moves within a certain range. Naturally they want to maximize their profit. Investors can perform up to 〈em〉k〈/em〉 trades, where each trade must involve the full amount. We give optimal algorithms for three different models which differ in the knowledge of how the price fluctuates. In the first model, there are global minimum and maximum bounds 〈em〉m〈/em〉 and 〈em〉M〈/em〉. We first show an optimal lower bound of 〈span〉 〈span〉\(\varphi \)〈/span〉 〈/span〉 (where 〈span〉 〈span〉\(\varphi =M/m\)〈/span〉 〈/span〉) on the competitive ratio for one trade, which is the bound achieved by trivial algorithms. Perhaps surprisingly, when we consider more than one trade, we can give a better algorithm that loses only a factor of 〈span〉 〈span〉\(\varphi ^{2/3}\)〈/span〉 〈/span〉 (rather than 〈span〉 〈span〉\(\varphi \)〈/span〉 〈/span〉) per additional trade. Specifically, for 〈em〉k〈/em〉 trades the algorithm has competitive ratio 〈span〉 〈span〉\(\varphi ^{(2k+1)/3}\)〈/span〉 〈/span〉. Furthermore we show that this ratio is the best possible by giving a matching lower bound. In the second model, 〈em〉m〈/em〉 and 〈em〉M〈/em〉 are not known in advance, and just 〈span〉 〈span〉\(\varphi \)〈/span〉 〈/span〉 is known. We show that this only costs us an extra factor of 〈span〉 〈span〉\(\varphi ^{1/3}\)〈/span〉 〈/span〉, i.e., both upper and lower bounds become 〈span〉 〈span〉\(\varphi ^{(2k+2)/3}\)〈/span〉 〈/span〉. Finally, we consider the bounded daily return model where instead of a global limit, the fluctuation from one day to the next is bounded, and again we give optimal algorithms, and interestingly one of them resembles common trading strategies that involve stop loss limits.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉A splittable good provided in 〈em〉n〈/em〉 pieces shall be divided as evenly as possible among 〈em〉m〈/em〉 agents, where every agent can take shares from at most 〈em〉F〈/em〉 pieces. We call 〈em〉F〈/em〉 the fragmentation and mainly restrict attention to the cases 〈span〉 〈span〉\(F=1\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(F=2\)〈/span〉 〈/span〉. For 〈span〉 〈span〉\(F=1\)〈/span〉 〈/span〉, the max–min and min–max problems are solvable in linear time. The case 〈span〉 〈span〉\(F=2\)〈/span〉 〈/span〉 has neat formulations and structural characterizations in terms of weighted graphs. First we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if 〈span〉 〈span〉\(m\ge n-1\)〈/span〉 〈/span〉, and a solution always exists in this case, in contrast to 〈span〉 〈span〉\(F=1\)〈/span〉 〈/span〉. Moreover, the problem is fixed-parameter tractable in the parameter 〈span〉 〈span〉\(2m-n\)〈/span〉 〈/span〉. (Note that this parameter measures the number of agents above the trivial threshold 〈span〉 〈span〉\(m=n/2\)〈/span〉 〈/span〉.) The structural results suggest another related problem where unsplittable items shall be assigned to subsets so as to balance the average sizes (rather than the total sizes) in these subsets. We give an approximation-preserving reduction from our original splitting problem with fragmentation 〈span〉 〈span〉\(F=2\)〈/span〉 〈/span〉 to this averaging problem, and some approximation results in cases when 〈em〉m〈/em〉 is close to either 〈em〉n〈/em〉 or 〈em〉n〈/em〉 / 2.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉We introduce a compressed suffix array representation that, on a text 〈em〉T〈/em〉 of length 〈em〉n〈/em〉 over an alphabet of size 〈span〉 〈span〉\(\sigma \)〈/span〉 〈/span〉, can be built in 〈em〉O〈/em〉(〈em〉n〈/em〉) deterministic time, within 〈span〉 〈span〉\(O(n\log \sigma )\)〈/span〉 〈/span〉 bits of working space, and counts the number of occurrences of any pattern 〈em〉P〈/em〉 in 〈em〉T〈/em〉 in time 〈span〉 〈span〉\(O(|P| + \log \log _w \sigma )\)〈/span〉 〈/span〉 on a RAM machine of 〈span〉 〈span〉\(w=\Omega (\log n)\)〈/span〉 〈/span〉-bit words. This time is almost optimal for large alphabets (〈span〉 〈span〉\(\log \sigma =\Theta (\log n)\)〈/span〉 〈/span〉), and it outperforms all the other compressed indexes that can be built in linear deterministic time, as well as some others. The only faster indexes can be built in linear time only in expectation, or require 〈span〉 〈span〉\(\Theta (n\log n)\)〈/span〉 〈/span〉 bits. For smaller alphabets, where 〈span〉 〈span〉\(\log \sigma = o(\log n)\)〈/span〉 〈/span〉, we show how, by using space proportional to a compressed representation of the text, we can build in linear time an index that counts in time 〈span〉 〈span〉\(O(|P|/\log _\sigma n + \log _\sigma ^\epsilon n)\)〈/span〉 〈/span〉 for any constant 〈span〉 〈span〉\(\epsilon 〉0\)〈/span〉 〈/span〉. This is almost RAM-optimal in the typical case where 〈span〉 〈span〉\(w=\Theta (\log n)\)〈/span〉 〈/span〉. 〈/p〉

Beschreibung: Network representation learning is a key research field in network data mining. In this paper, we propose a novel multi-view network representation algorithm (MVNR), which embeds multi-scale relations of network vertices into the low dimensional representation space. In contrast to existing approaches, MVNR explicitly encodes higher order information using k-step networks. In addition, we introduce the matrix forest index as a kind of network feature, which can be applied to balance the representation weights of different network views. We also research the relevance amongst MVNR and several excellent research achievements, including DeepWalk, node2vec and GraRep and so forth. We conduct our experiment on several real-world citation datasets and demonstrate that MVNR outperforms some new approaches using neural matrix factorization. Specifically, we demonstrate the efficiency of MVNR on network classification, visualization and link prediction tasks.

Beschreibung: In the real word, optimization problems in multi-objective optimization (MOP) and dynamic optimization can be seen everywhere. During the last decade, among various swarm intelligence algorithms for multi-objective optimization problems, glowworm swarm optimization (GSO) and bacterial foraging algorithm (BFO) have attracted increasing attention from scholars. Although many scholars have proposed improvement strategies for GSO and BFO to keep a good balance between convergence and diversity, there are still many problems to be solved carefully. In this paper, a new coupling algorithm based on GSO and BFO (MGSOBFO) is proposed for solving dynamic multi-objective optimization problems (dMOP). MGSOBFO is proposed to achieve a good balance between exploration and exploitation by dividing into two parts. Part I is in charge of exploitation by GSO and Part II is in charge of exploration by BFO. At the same time, the simulation binary crossover (SBX) and polynomial mutation are introduced into the MGSOBFO to enhance the convergence and diversity ability of the algorithm. In order to show the excellent performance of the algorithm, we experimentally compare MGSOBFO with three algorithms on the benchmark function. The results suggests that such a coupling algorithm has good performance and outperforms other algorithms which deal with dMOP.

Beschreibung: Clustering is an important task in data mining that has become more challenging due to the ever-increasing size of available datasets. To cope with these big data scenarios, a high-performance clustering approach is required. Sparse grid clustering is a density-based clustering method that uses a sparse grid density estimation as its central building block. The underlying density estimation approach enables the detection of clusters with non-convex shapes and without a predetermined number of clusters. In this work, we introduce a new distributed and performance-portable variant of the sparse grid clustering algorithm that is suited for big data settings. Our computed kernels were implemented in OpenCL to enable portability across a wide range of architectures. For distributed environments, we added a manager–worker scheme that was implemented using MPI. In experiments on two supercomputers, Piz Daint and Hazel Hen, with up to 100 million data points in a ten-dimensional dataset, we show the performance and scalability of our approach. The dataset with 100 million data points was clustered in 1198 s using 128 nodes of Piz Daint. This translates to an overall performance of 352 TFLOPS . On the node-level, we provide results for two GPUs, Nvidia’s Tesla P100 and the AMD FirePro W8100, and one processor-based platform that uses Intel Xeon E5-2680v3 processors. In these experiments, we achieved between 43% and 66% of the peak performance across all computed kernels and devices, demonstrating the performance portability of our approach.

Beschreibung: In order to solve the poor control accuracy problem of the traditional synchronous control algorithm for a double-cylinder forging hydraulic press, a synchronous control algorithm for double-cylinder forging hydraulic press based on a fuzzy neural network was proposed. According to the flow equation of valve and hydraulic cylinder, the balance equation and force balance equation of forging hydraulic cylinder are established by using the theory of electro-hydraulic servo systems, and the cylinder-controlled transfer function of forging hydraulic cylinder is deduced. By properly simplifying the transfer function, the mathematical model of synchronous control of double cylinder forging hydraulic press is established. According to the implementation process of traditional fuzzy neural networks, the properties of compensation operation are introduced. The traditional fuzzy neural network is optimized, and the optimized neural network is used to realize the synchronous control of the double cylinder forging hydraulic press. The experimental results show that the amplitude curve of the algorithm is very close to the expected amplitude curve, the error amplitude is only 0.3 mm, and the average control time is about 140 s, which fully shows that the algorithm has high accuracy and a good control effect.

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph 〈span〉 〈span〉\(G=(V,E)\)〈/span〉 〈/span〉 with 〈span〉 〈span〉\(n=|V|\)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(m=|E|\)〈/span〉 〈/span〉, and an integer value 〈span〉 〈span〉\(k\ge 1\)〈/span〉 〈/span〉, there is an algorithm that computes in 〈span〉 〈span〉\(O(2^{k}n\log ^2 n)\)〈/span〉 〈/span〉 time for any set 〈em〉F〈/em〉 of size at most 〈em〉k〈/em〉 the strongly connected components of the graph 〈span〉 〈span〉\(G{\setminus }F\)〈/span〉 〈/span〉. The running time of our algorithm is almost optimal since the time for outputting the SCCs of 〈span〉 〈span〉\(G{\setminus } F\)〈/span〉 〈/span〉 is at least 〈span〉 〈span〉\(\varOmega (n)\)〈/span〉 〈/span〉. The algorithm uses a data structure that is computed in a preprocessing phase in polynomial time and is of size 〈span〉 〈span〉\(O(2^{k} n^2)\)〈/span〉 〈/span〉. Our result is obtained using a new observation on the relation between strongly connected components (SCCs) and reachability. More specifically, one of the main building blocks in our result is a restricted variant of the problem in which we only compute strongly connected components that intersect a certain path. Restricting our attention to a path allows us to implicitly compute reachability between the path vertices and the rest of the graph in time that depends logarithmically rather than linearly in the size of the path. This new observation alone, however, is not enough, since we need to find an efficient way to represent the strongly connected components using paths. For this purpose we use a mixture of old and classical techniques such as the heavy path decomposition of Sleator and Tarjan (J Comput Syst Sci 26:362–391, 〈span〉1983〈/span〉) and the classical Depth-First-Search algorithm. Although, these are by now standard techniques, we are not aware of any usage of them in the context of dynamic maintenance of SCCs. Therefore, we expect that our new insights and mixture of new and old techniques will be of independent interest.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉We study popular matchings in the many-to-many matching problem, which is given by a graph 〈span〉 〈span〉\(G = (V,E)\)〈/span〉 〈/span〉 and, for every agent 〈span〉 〈span〉\(u\in V\)〈/span〉 〈/span〉, a capacity 〈span〉 〈span〉\(\textsf {cap}(u) \ge 1\)〈/span〉 〈/span〉 and a preference list strictly ranking her neighbors. A matching in 〈em〉G〈/em〉 is popular if it weakly beats every matching in a majority vote when agents cast votes for one matching versus the other according to their preferences. First, we show that when 〈span〉 〈span〉\(G = (A\cup B,E)\)〈/span〉 〈/span〉 is bipartite, e.g., when matching students to courses, every pairwise stable matching is popular. In particular, popular matchings are guaranteed to exist. Our main contribution is to show that a max-size popular matching in 〈em〉G〈/em〉 can be computed in linear time by the 〈em〉2-level Gale–Shapley〈/em〉 algorithm, which is an extension of the classical Gale–Shapley algorithm. We prove its correctness via linear programming. Second, we consider the problem of computing a max-size popular matching in 〈span〉 〈span〉\(G = (V,E)\)〈/span〉 〈/span〉 (not necessarily bipartite) when every agent has capacity 1, e.g., when matching students to dorm rooms. We show that even when 〈em〉G〈/em〉 admits a stable matching, this problem is 〈span〉 〈span〉\(\mathsf {NP}\)〈/span〉 〈/span〉-hard, which is in contrast to the tractability result in bipartite graphs.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉We study problems that integrate buy-at-bulk network design into the classical (connected) facility location problem. In such problems, we need to open facilities, build a routing network, and route every client demand to an open facility. Furthermore, capacities of the edges can be purchased in discrete units from 〈em〉K〈/em〉 different cable types with costs that satisfy economies of scale. We extend the linear programming framework of Talwar (IPCO 2002) for the single-source buy-at-bulk problem to these variants and prove integrality gap upper bounds for both facility location and connected facility location buy-at-bulk problems. For the unconnected variant we prove an integrality gap bound of 〈em〉O〈/em〉(〈em〉K〈/em〉), and for the connected version, we get the first LP-based bound of 〈em〉O〈/em〉(1).〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low independence. A series of papers, beginning with work by Luby (1988), showed that in many cases these techniques can be combined to give deterministic parallel (NC) algorithms for a variety of combinatorial optimization problems, with low time- and processor-complexity. We extend and generalize a technique of Luby for efficiently handling bilinear objective functions. One noteworthy application is an NC algorithm for maximal independent set. On a graph 〈em〉G〈/em〉 with 〈em〉m〈/em〉 edges and 〈em〉n〈/em〉 vertices, this takes 〈span〉 〈span〉\({\tilde{O}}(\log ^2 n)\)〈/span〉 〈/span〉 time and 〈span〉 〈span〉\((m + n) n^{o(1)}\)〈/span〉 〈/span〉 processors, nearly matching the best randomized parallel algorithms. Other applications include reduced processor counts for algorithms of Berger (SIAM J Comput 26:1188–1207, 〈span〉1997〈/span〉) for maximum acyclic subgraph and Gale–Berlekamp switching games. This bilinear factorization also gives better algorithms for problems involving discrepancy. An important application of this is to automata-fooling probability spaces, which are the basis of a notable derandomization technique of Sivakumar (In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp 619–626, 〈span〉2002〈/span〉). Our method leads to large reduction in processor complexity for a number of derandomization algorithms based on automata-fooling, including set discrepancy and the Johnson–Lindenstrauss Lemma.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉Let 〈span〉 〈span〉\(\mathcal {P}(G,X)\)〈/span〉 〈/span〉 be a property associating a boolean value to each pair (〈em〉G〈/em〉, 〈em〉X〈/em〉) where 〈em〉G〈/em〉 is a graph and 〈em〉X〈/em〉 is a vertex subset. Assume that 〈span〉 〈span〉\(\mathcal {P}\)〈/span〉 〈/span〉 is expressible in counting monadic second order logic (CMSO) and let 〈em〉t〈/em〉 be an integer constant. We consider the following optimization problem: given an input graph 〈span〉 〈span〉\(G=(V,E)\)〈/span〉 〈/span〉, find subsets 〈span〉 〈span〉\(X\subseteq F \subseteq V\)〈/span〉 〈/span〉 such that the treewidth of 〈em〉G〈/em〉[〈em〉F〈/em〉] is at most 〈em〉t〈/em〉, property 〈span〉 〈span〉\(\mathcal {P}(G[F],X)\)〈/span〉 〈/span〉 is true and 〈em〉X〈/em〉 is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., 〈span〉Longest Induced Path〈/span〉, 〈span〉Maximum Induced Forest〈/span〉, 〈span〉Independent〈/span〉〈span〉 〈span〉\(\mathcal {H}\)〈/span〉 〈/span〉-〈span〉Packing〈/span〉, etc. Fomin et al. (SIAM J Comput 44(1):54–87, 〈span〉2015〈/span〉) proved that the problem is polynomial on the class of graph 〈span〉 〈span〉\({\mathcal {G}}_{{\text {poly}}}\)〈/span〉 〈/span〉, i.e. the graphs having at most 〈span〉 〈span〉\({\text {poly}}(n)\)〈/span〉 〈/span〉 minimal separators for some polynomial 〈span〉 〈span〉\({\text {poly}}\)〈/span〉 〈/span〉. Here we consider the class 〈span〉 〈span〉\({\mathcal {G}}_{{\text {poly}}}+ kv\)〈/span〉 〈/span〉, formed by graphs of 〈span〉 〈span〉\({\mathcal {G}}_{{\text {poly}}}\)〈/span〉 〈/span〉 to which we add a set of at most 〈em〉k〈/em〉 vertices with arbitrary adjacencies, called 〈em〉modulator〈/em〉. We prove that the generic optimization problem is fixed parameter tractable on 〈span〉 〈span〉\({\mathcal {G}}_{{\text {poly}}}+ kv\)〈/span〉 〈/span〉, with parameter 〈em〉k〈/em〉, if the modulator is also part of the input.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is 〈span〉NP〈/span〉-complete, substantial effort has been dedicated to determining the complexity of deciding if a graph has a square root belonging to some specific graph class 〈span〉 〈span〉\({{\mathcal {H}}}\)〈/span〉 〈/span〉. There are both polynomial-time solvable and 〈span〉NP〈/span〉-complete results in this direction, depending on 〈span〉 〈span〉\({{\mathcal {H}}}\)〈/span〉 〈/span〉. We present a general framework for the problem if 〈span〉 〈span〉\(\mathcal{H}\)〈/span〉 〈/span〉 is a class of sparse graphs. This enables us to generalize a number of known results and to give polynomial-time algorithms for the cases where 〈span〉 〈span〉\({{\mathcal {H}}}\)〈/span〉 〈/span〉 is the class of outerplanar graphs and 〈span〉 〈span〉\({{\mathcal {H}}}\)〈/span〉 〈/span〉 is the class of graphs of pathwidth at most 2.〈/p〉

Beschreibung: This paper proposes a low-carbon location routing problem (LCLRP) model with simultaneous delivery and pick up, time windows, and heterogeneous fleets to reduce the logistics cost and carbon emissions and improve customer satisfaction. The correctness of the model is tested by a simple example of CPLEX (optimization software for mathematical programming). To solve this problem, a hyper-heuristic algorithm is designed based on a secondary exponential smoothing strategy and adaptive receiving mechanism. The algorithm can achieve fast convergence and is highly robust. This case study analyzes the impact of depot distribution and cost, heterogeneous fleets (HF), and customer distribution and time windows on logistics costs, carbon emissions, and customer satisfaction. The experimental results show that the proposed model can reduce logistics costs by 1.72%, carbon emissions by 11.23%, and vehicle travel distance by 9.69%, and show that the proposed model has guiding significance for reducing logistics costs.

Beschreibung: The compressed sensing theory has been widely used in solving undetermined equations in various fields and has made remarkable achievements. The regularized smooth L0 (ReSL0) reconstruction algorithm adds an error regularization term to the smooth L0(SL0) algorithm, achieving the reconstruction of the signal well in the presence of noise. However, the ReSL0 reconstruction algorithm still has some flaws. It still chooses the original optimization method of SL0 and the Gauss approximation function, but this method has the problem of a sawtooth effect in the later optimization stage, and the convergence effect is not ideal. Therefore, we make two adjustments to the basis of the ReSL0 reconstruction algorithm: firstly, we introduce another CIPF function which has a better approximation effect than Gauss function; secondly, we combine the steepest descent method and Newton method in terms of the algorithm optimization. Then, a novel regularized recovery algorithm named combined regularized smooth L0 (CReSL0) is proposed. Under the same experimental conditions, the CReSL0 algorithm is compared with other popular reconstruction algorithms. Overall, the CReSL0 algorithm achieves excellent reconstruction performance in terms of the peak signal-to-noise ratio (PSNR) and run-time for both a one-dimensional Gauss signal and two-dimensional image reconstruction tasks.

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉We consider space efficient hash tables that can grow and shrink dynamically and are always highly space efficient, i.e., their space consumption is always close to the lower bound even while growing and when taking into account storage that is only needed temporarily. None of the traditionally used hash tables have this property. We show how known approaches like linear probing and bucket cuckoo hashing can be adapted to this scenario by subdividing them into many subtables or using virtual memory overcommitting. However, these rather straightforward solutions suffer from slow amortized insertion times due to frequent reallocation in small increments. Our main result is Dynamic Space Efficient Cuckoo Table (DySECT ) which avoids these problems. DySECT consists of many subtables which grow by doubling their size. The resulting inhomogeneity in subtable sizes is counterbalanced by the flexibility available in bucket cuckoo hashing where each element can go to several buckets each of which containing several cells. Experiments indicate that DySECT works well with loads up to 98%. With up to 1.9 times better performance than the next best solution. Additionally, we give a tight theoretical analysis for the possible load threshold of DySECT, i.e., a bound where with high probability the table can be filled up to that load but not above said load. This load also matches our experimental findings.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉Let 〈em〉P〈/em〉 be a finite set of points in the plane and 〈em〉S〈/em〉 a set of non-crossing line segments with endpoints in 〈em〉P〈/em〉. The visibility graph of 〈em〉P〈/em〉 with respect to 〈em〉S〈/em〉, denoted 〈span〉 〈span〉\(\mathord { Vis}(P,S)\)〈/span〉 〈/span〉, has vertex set 〈em〉P〈/em〉 and an edge for each pair of vertices 〈em〉u〈/em〉, 〈em〉v〈/em〉 in 〈em〉P〈/em〉 for which no line segment of 〈em〉S〈/em〉 properly intersects 〈em〉uv〈/em〉. We show that the constrained half-〈span〉 〈span〉\(\theta _6\)〈/span〉 〈/span〉-graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of 〈span〉 〈span〉\(\mathord { Vis}(P,S)\)〈/span〉 〈/span〉. We then show how to construct a plane 6-spanner of 〈span〉 〈span〉\(\mathord { Vis}(P,S)\)〈/span〉 〈/span〉 with maximum degree 〈span〉 〈span〉\(6+c\)〈/span〉 〈/span〉, where 〈em〉c〈/em〉 is the maximum number of segments of 〈em〉S〈/em〉 incident to a vertex.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉A directed multigraph is said 〈em〉vulnerable〈/em〉 if it can generate 〈em〉Braess paradox〈/em〉 in traffic networks. In this paper, we give a graph–theoretic characterisation of vulnerable directed multigraphs. Analogous results appeared in the literature only for undirected multigraphs and for a specific family of directed multigraphs. The proof of our characterisation provides the first polynomial time algorithm that checks if a general directed multigraph is vulnerable in 〈span〉 〈span〉\(\mathcal{O}(|V| \cdot |E|^2)\)〈/span〉 〈/span〉. Our algorithm also contributes to the directed subgraph homeomorphism problem without node mapping, by providing another pattern graph for which a polynomial time algorithm exists.〈/p〉

Beschreibung: As of today, bioinformatics is one of the most exciting fields of scientific research. There is a wide-ranging list of challenging problems to face, i.e., pairwise and multiple alignments, motif detection/discrimination/classification, phylogenetic tree reconstruction, protein secondary and tertiary structure prediction, protein function prediction, DNA microarray analysis, gene regulation/regulatory networks, just to mention a few, and an army of researchers, coming from several scientific backgrounds, focus their efforts on developing models to properly address these problems. In this paper, we aim to briefly review some of the huge amount of machine learning methods, developed in the last two decades, suited for the analysis of gene microarray data that have a strong impact on molecular biology. In particular, we focus on the wide-ranging list of data clustering and visualization techniques able to find homogeneous data groupings, and also provide the possibility to discover its connections in terms of structure, function and evolution.

Beschreibung: A multi-track string is a tuple of strings of the same length. Given the pattern and text of two multi-track strings, the permuted pattern matching problem is to find the occurrence positions of all permutations of the pattern in the text. In this paper, we propose several algorithms for permuted pattern matching. Our first algorithm, which is based on the Knuth–Morris–Pratt (KMP) algorithm, has a fast theoretical computing time with O ( m k ) as the preprocessing time and O ( n k log σ ) as the matching time, where n, m, k, σ , and occ denote the length of the text, the length of the pattern, the number of strings in the multi-track, the alphabet size, and the number of occurrences of the pattern, respectively. We then improve the KMP-based algorithm by using an automaton, which has a better experimental running time. The next proposed algorithms are based on the Boyer–Moore algorithm and the Horspool algorithm that try to perform pattern matching. These algorithms are the fastest experimental algorithms. Furthermore, we propose an extension of the AC-automaton algorithm that can solve dictionary matching on multi-tracks, which is a task to find multiple multi-track patterns in a multi-track text. Finally, we propose filtering algorithms that can perform permuted pattern matching quickly in practice.

Beschreibung: The Ensemble Empirical Mode Decomposition (EEMD) algorithm has been used in bearing fault diagnosis. In order to overcome the blindness in the selection of white noise amplitude coefficient e in EEMD, an improved artificial bee colony algorithm (IABC) is proposed to obtain it adaptively, which providing a new idea for the selection of EEMD parameters. In the improved algorithm, chaos initialization is introduced in the artificial bee colony (ABC) algorithm to insure the diversity of the population and the ergodicity of the population search process. On the other hand, the collecting bees are divided into two parts in the improved algorithm, one part collects the optimal information of the region according to the original algorithm, the other does Levy flight around the current global best solution to improve its global search capabilities. Four standard test functions are used to show the superiority of the proposed method. The application of the IABC and EEMD algorithm in bearing fault diagnosis proves its effectiveness.

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any 〈span〉 〈span〉\(d〉0\)〈/span〉 〈/span〉, the first algorithm maintains a proper 〈span〉 〈span〉\(O(\mathcal {C} dN ^{1/d})\)〈/span〉 〈/span〉-coloring while recoloring at most 〈em〉O〈/em〉(〈em〉d〈/em〉) vertices per update, where 〈span〉 〈span〉\(\mathcal {C} \)〈/span〉 〈/span〉 and 〈span〉 〈span〉\(N \)〈/span〉 〈/span〉 are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an 〈span〉 〈span〉\(O(\mathcal {C} d)\)〈/span〉 〈/span〉-coloring with 〈span〉 〈span〉\(O(dN ^{1/d})\)〈/span〉 〈/span〉 recolorings per update. The two converge when 〈span〉 〈span〉\(d = \log N \)〈/span〉 〈/span〉, maintaining an 〈span〉 〈span〉\(O(\mathcal {C} \log N)\)〈/span〉 〈/span〉-coloring with 〈span〉 〈span〉\(O(\log N)\)〈/span〉 〈/span〉 recolorings per update. We also present a lower bound, showing that any algorithm that maintains a 〈em〉c〈/em〉-coloring of a 2-colorable graph on 〈span〉 〈span〉\(N \)〈/span〉 〈/span〉 vertices must recolor at least 〈span〉 〈span〉\(\varOmega (N ^\frac{2}{c(c-1)})\)〈/span〉 〈/span〉 vertices per update, for any constant 〈span〉 〈span〉\(c \ge 2\)〈/span〉 〈/span〉.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉In this paper, we study the NP-complete 〈em〉colorful〈/em〉 variant of the classical 〈span〉Matching〈/span〉 problem, namely, the 〈span〉Rainbow Matching〈/span〉 problem. Given an edge-colored graph 〈em〉G〈/em〉 and a positive integer 〈em〉k〈/em〉, this problem asks whether there exists a matching of size at least 〈em〉k〈/em〉 such that all the edges in the matching have distinct colors. We first develop a deterministic algorithm that solves 〈span〉Rainbow Matching〈/span〉 on paths in time 〈span〉 〈span〉\(\mathcal{O}^\star \left( \left( \frac{1+\sqrt{5}}{2}\right) ^k\right) \)〈/span〉 〈/span〉 and polynomial space. This algorithm is based on a curious combination of the method of bounded search trees and a “divide-and-conquer-like” approach, where the branching process is guided by the maintenance of an auxiliary bipartite graph where one side captures “divided-and-conquered” pieces of the path. Our second result is a randomized algorithm that solves 〈span〉Rainbow Matching〈/span〉 on general graphs in time 〈span〉 〈span〉\(\mathcal {O} ^\star (2^k)\)〈/span〉 〈/span〉 and polynomial-space. Here, we show how a result by Björklund et al. (J Comput Syst Sci 87:119–139, 〈span〉2017〈/span〉) can be invoked as a black box, wrapped by a probability-based analysis tailored to our problem. We also complement our two main results by designing kernels for 〈span〉Rainbow Matching〈/span〉 on general and bounded-degree graphs.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉We study the problem of fair division of a heterogeneous resource among strategic players. Given a divisible heterogeneous cake, we wish to divide the cake among 〈em〉n〈/em〉 players to meet these conditions: (I) every player (weakly) prefers his allocated cake to any other player’s share (such notion is known as envy-freeness), (II) the allocation is dominant strategy-proof (truthful) (III) the number of cuts made on the cake is small. We provide methods for dividing the cake under different assumptions on the valuation functions of the players. First, we suppose that the valuation function of every player is a single interval with a special property, namely 〈em〉ordering property〈/em〉. For this case, we propose a process called 〈em〉expansion process〈/em〉 and show that it results in an envy-free and truthful allocation that cuts the cake into exactly 〈em〉n〈/em〉 pieces. Next, we remove the ordering restriction and show that for this case, an extended form of the expansion process, called 〈em〉expansion process with unlocking〈/em〉 yields an envy-free allocation of the cake with at most 〈span〉 〈span〉\(2(n-1)\)〈/span〉 〈/span〉 cuts. Furthermore, we show that in the 〈em〉expansion process with unlocking〈/em〉, the players may misrepresent their valuations to earn more share. In addition, we use a more complex form of the 〈em〉expansion process with unlocking〈/em〉 to obtain an envy-free and truthful allocation that cuts the cake in at most 〈span〉 〈span〉\(2(n-1)\)〈/span〉 〈/span〉 locations. We also, evaluate our expansion method in practice. In the empirical results, we compare the number of cuts made by our method to the number of cuts in the optimal solution (〈span〉 〈span〉\(n-1\)〈/span〉 〈/span〉). The experiments reveal that the number of cuts made by the expansion and unlocking process for envy-free division of the cake is very close to the optimal solution. Finally, we study piecewise constant and piecewise uniform valuation functions with 〈em〉m〈/em〉 pieces and present the conditions, under which a generalized form of expansion process can allocate the cake via 〈em〉O〈/em〉(〈em〉nm〈/em〉) cuts.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉There has been intensive work on the parameterized complexity of the typically NP-hard task to edit undirected graphs into graphs fulfilling certain given vertex degree constraints. In this work, we lift the investigations to the case of directed graphs; herein, we focus on arc insertions. To this end, we develop a general two-stage framework which consists of efficiently solving a problem-specific number problem and transferring its solution to a solution for the graph problem by applying flow computations. In this way, we obtain fixed-parameter tractability and polynomial kernelizability results, with the central parameter being the maximum vertex in- or outdegree of the output digraph. Although there are certain similarities with the much better studied undirected case, the flow computation used in the directed case seems not to work for the undirected case while 〈em〉f〈/em〉-factor computations as used in the undirected case seem not to work for the directed case.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Combined with simple counter-examples for other patterns, we make significant progress towards a complete classification.〈/p〉

Beschreibung: Advancing the background-subtraction method in dynamic scenes is an ongoing timely goal for many researchers. Recently, background subtraction methods have been developed with deep convolutional features, which have improved their performance. However, most of these deep methods are supervised, only available for a certain scene, and have high computational cost. In contrast, the traditional background subtraction methods have low computational costs and can be applied to general scenes. Therefore, in this paper, we propose an unsupervised and concise method based on the features learned from a deep convolutional neural network to refine the traditional background subtraction methods. For the proposed method, the low-level features of an input image are extracted from the lower layer of a pretrained convolutional neural network, and the main features are retained to further establish the dynamic background model. The evaluation of the experiments on dynamic scenes demonstrates that the proposed method significantly improves the performance of traditional background subtraction methods.

Beschreibung: The authors wish to make the following corrections to their paper[...]

Beschreibung: We present two modifications of Duval’s algorithm for computing the Lyndon factorization of a string. One of the algorithms has been designed for strings containing runs of the smallest character. It works best for small alphabets and it is able to skip a significant number of characters of the string. Moreover, it can be engineered to have linear time complexity in the worst case. When there is a run-length encoded string R of length ρ , the other algorithm computes the Lyndon factorization of R in O ( ρ ) time and in constant space. It is shown by experimental results that the new variations are faster than Duval’s original algorithm in many scenarios.

Beschreibung: We study two problems in computational phylogenetics. The first is tree compatibility. The input is a collection P of phylogenetic trees over different partially-overlapping sets of species. The goal is to find a single phylogenetic tree that displays all the evolutionary relationships implied by P . The second problem is incomplete directed perfect phylogeny (IDPP). The input is a data matrix describing a collection of species by a set of characters, where some of the information is missing. The question is whether there exists a way to fill in the missing information so that the resulting matrix can be explained by a phylogenetic tree satisfying certain conditions. We explain the connection between tree compatibility and IDPP and show that a recent tree compatibility algorithm is effectively a generalization of an earlier IDPP algorithm. Both algorithms rely heavily on maintaining the connected components of a graph under a sequence of edge and vertex deletions, for which they use the dynamic connectivity data structure of Holm et al., known as HDT. We present a computational study of algorithms for tree compatibility and IDPP. We show experimentally that substituting HDT by a much simpler data structure—essentially, a single-level version of HDT—improves the performance of both of these algorithm in practice. We give partial empirical and theoretical justifications for this observation.

Beschreibung: This article describes an optimization methodology based on a model of competitiveness between different metaheuristic methods. The main contribution is a strategy to dynamically find the algorithm that obtains the best result based on the competitiveness of methods to solve a specific problem using different performance metrics depending on the problem. The algorithms used in the preliminary tests are: the firefly algorithm (FA), which is inspired by blinking fireflies; wind-driven optimization (WDO), which is inspired by the movement of the wind in the atmosphere, and in which the positions and velocities of the wind packages are updated; and finally, drone squadron optimization (DSO)—the inspiration for this method is new and interesting—based on artifacts, where drones have a command center that sends information to individual drones and updates their software to optimize the objective function. The proposed model helps discover the best method to solve a specific problem, and also reduces the time that it takes to search for methods before finding the one that obtains the most satisfactory results. The main idea is that with this competitiveness approach, methods are tested at the same time until the best one to solve the problem in question is found. As preliminary tests of the model, the optimization of the benchmark mathematical functions and membership functions of a fuzzy controller of an autonomous mobile robot was used.

Beschreibung: In this paper we introduced a new class of strong negations, which were generated via conical sections. This paper focuses on the fact that simple mathematical and computational processes generate new strong fuzzy negations, through purely geometrical concepts such as the ellipse and the hyperbola. Well-known negations like the classical negation, Sugeno negation, etc., were produced via the suggested conical sections. The strong negations were a structural element in the production of fuzzy implications. Thus, we have a machine for producing fuzzy implications, which can be useful in many areas, as in artificial intelligence, neural networks, etc. Strong Fuzzy Negations refers to the discrepancy between the degree of difficulty of the effort and the significance of its results. Innovative results may, therefore, derive for use in literature in the specific field of mathematics. These data are, moreover, generated in an effortless, concise, as well as self-evident manner.

Beschreibung: Electrical impedance tomography (EIT) has been a hot topic among researchers for the last 30 years. It is a new imaging method and has evolved over the last few decades. By injecting a small amount of current, the electrical properties of tissues are determined and measurements of the resulting voltages are taken. By using a reconstructing algorithm these voltages then transformed into a tomographic image. EIT contains no identified threats and as compared to magnetic resonance imaging (MRI) and computed tomography (CT) scans (imaging techniques), it is cheaper in cost as well. In this paper, a comprehensive review of efforts and advancements undertaken and achieved in recent work to improve this technology and the role of artificial intelligence to solve this non-linear, ill-posed problem are presented. In addition, a review of EIT clinical based applications has also been presented.

Beschreibung: The grounding grid of a substation is important for the safety of substation equipment. Especially to address the difficulty of parameter design in the auxiliary anode system of a grounding grid, an algorithm is proposed that is an optimization algorithm for the auxiliary anode system of a grounding grid based on improved simulated annealing. The mathematical model of the auxiliary anode system is inferred from the mathematical model of cathodic protection. On that basis, the parameters of the finite element model are optimized with the improved simulated annealing algorithm, thereby the auxiliary anode system of a grounding grid with optimized parameters is structured. Then the algorithm is proven as valid through experiments. The precision of the optimized parameters is improved by about 1.55% with respect to the Variable Metric Method and the Genetic Algorithm, so it can provide a basis for parameter design in the auxiliary anode system of a grounding grid.

Beschreibung: In this paper, we propose a novel spatial image error concealment (EC) method based on deep neural network. Considering that the natural images have local correlation and non-local self-similarity, we use the local information to predict the missing pixels and the non-local information to correct the predictions. The deep neural network we utilize can be divided into two parts: the prediction part and the auto-encoder (AE) part. The first part utilizes the local correlation among pixels to predict the missing ones. The second part extracts image features, which are used to collect similar samples from the whole image. In addition, a novel adaptive scan order based on the joint credibility of the support area and reconstruction is also proposed to alleviate the error propagation problem. The experimental results show that the proposed method can reconstruct corrupted images effectively and outperform the compared state-of-the-art methods in terms of objective and perceptual metrics.

Beschreibung: During the last few decades, machine learning has constituted a significant tool in extracting useful knowledge from economic data for assisting decision-making. In this work, we evaluate the performance of weight-constrained recurrent neural networks in forecasting economic classification problems. These networks are efficiently trained with a recently-proposed training algorithm, which has two major advantages. Firstly, it exploits the numerical efficiency and very low memory requirements of the limited memory BFGS matrices; secondly, it utilizes a gradient-projection strategy for handling the bounds on the weights. The reported numerical experiments present the classification accuracy of the proposed model, providing empirical evidence that the application of the bounds on the weights of the recurrent neural network provides more stable and reliable learning.

Beschreibung: The horizontal bending angle of scraper conveyor has a great influence on the running resistance, the current consumption, coal winning efficiency of the working surface, etc. Approximately 1–3° is usually the range of horizontal bending angle, but does not indicate the optimum bending angle of the coal mining face. To find the optimal horizontal bending angle, an optimization method is proposed. A mathematical calculation model of the running resistance of the scraper is established based on the direction of the shearer operation. Then, a method of adjusting the step size of the search by inertia weight and expanding fly distance range obeying the t-distribution is proposed based on the basic bat algorithm (BA). Finally, an industrial application was conducted in 21220 Changcun fully mechanized coal mining face, Henan Province. The results show that the current consumption by the scraper conveyor was reduced by 31% when the horizontal bending angle of the S-bending area was 0.66°. Meanwhile, the theoretical current has good consistency with the experimental data, and the average absolute error was 3%.

Beschreibung: During the last decades, intensive efforts have been devoted to the extraction of useful knowledge from large volumes of medical data employing advanced machine learning and data mining techniques. Advances in digital chest radiography have enabled research and medical centers to accumulate large repositories of classified (labeled) images and mostly of unclassified (unlabeled) images from human experts. Machine learning methods such as semi-supervised learning algorithms have been proposed as a new direction to address the problem of shortage of available labeled data, by exploiting the explicit classification information of labeled data with the information hidden in the unlabeled data. In the present work, we propose a new ensemble semi-supervised learning algorithm for the classification of lung abnormalities from chest X-rays based on a new weighted voting scheme. The proposed algorithm assigns a vector of weights on each component classifier of the ensemble based on its accuracy on each class. Our numerical experiments illustrate the efficiency of the proposed ensemble methodology against other state-of-the-art classification methods.

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉In this paper, we discuss the design and analysis of polynomial time algorithms for two problems associated with a linearly infeasible system of Unit Two Variable Per Inequality (UTVPI) constraints, viz., (a) the read-once refutation (ROR) problem, and (b) the literal-once refutation (LOR) problem. Recall that a UTVPI constraint is a linear relationship of the form: 〈span〉 〈span〉\(a_{i}\cdot x_{i}+a_{j} \cdot x_{j} \le b_{ij}\)〈/span〉 〈/span〉, where 〈span〉 〈span〉\(a_{i},a_{j} \in \{0,1,-1\}\)〈/span〉 〈/span〉. A conjunction of such constraints is called a UTVPI constraint system (UCS) and can be represented in matrix form as: 〈span〉 〈span〉\(\mathbf{A \cdot x \le b}\)〈/span〉 〈/span〉. These constraints find applications in a host of domains including but not limited to operations research and program verification. For the linear system 〈span〉 〈span〉\(\mathbf{A\cdot x \le b}\)〈/span〉 〈/span〉, a refutation is a collection of 〈em〉m〈/em〉 variables 〈span〉 〈span〉\(\mathbf{y}=[y_{1},y_{2},\ldots , y_{m}]^{T} \in \mathfrak {R}^{m}_{+}\)〈/span〉 〈/span〉, such that 〈span〉 〈span〉\(\mathbf{y\cdot A =0}\)〈/span〉 〈/span〉, 〈span〉 〈span〉\(\mathbf{y \cdot b } 〈 0\)〈/span〉 〈/span〉. Such a refutation is guaranteed to exist for any infeasible linear program, as per Farkas’ lemma. The refutation is said to be read-once, if each 〈span〉 〈span〉\(y_{i} \in \{0,1\}\)〈/span〉 〈/span〉. Read-once refutations are 〈strong〉incomplete〈/strong〉 in that their existence is not guaranteed for infeasible linear programs, in general. Indeed they are not complete, even for UCSs. Hence, the question of whether an arbitrary UCS has an ROR is both interesting and non-trivial. In this paper, we reduce this problem to the problem of computing a minimum weight perfect matching (MWPM) in an undirected graph. This transformation results in an algorithm that runs in in time polynomial in the size of the input UCS. Additionally, we design a polynomial time algorithm (also via a reduction to the MWPM problem) for a variant of read-once resolution called literal-once resolution. The advantage of reducing our problems to the MWPM problem is that we can leverage recent advances in algorithm design for the MWPM problem towards solving the ROR and LOR problems in UCSs. Finally, we show that another variant of read-once refutation problem called the non-literal read-once refutation (NLROR) problem is 〈strong〉NP-complete〈/strong〉 in UCSs.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉The classic 〈span〉 〈span〉\(K\)〈/span〉 〈/span〉-〈span〉Cycle〈/span〉 problem asks if a graph 〈em〉G〈/em〉, with vertex-set 〈em〉V〈/em〉(〈em〉G〈/em〉), has a simple cycle containing all vertices of a given set 〈span〉 〈span〉\(K\subseteq V(G)\)〈/span〉 〈/span〉. In terms of colored graphs, it can be rephrased as follows: Given a graph 〈em〉G〈/em〉, a set 〈span〉 〈span〉\(K\subseteq V(G)\)〈/span〉 〈/span〉 and an injective coloring 〈span〉 〈span〉\(c: K\rightarrow \{1,2,\ldots ,|K|\}\)〈/span〉 〈/span〉, decide if 〈em〉G〈/em〉 has a simple cycle containing each color in 〈span〉 〈span〉\(\{1,2,\ldots ,|K|\}\)〈/span〉 〈/span〉 exactly once. Another problem widely known since the introduction of color coding is 〈span〉Colorful Cycle〈/span〉. Given a graph 〈em〉G〈/em〉 and a coloring 〈span〉 〈span〉\(c: V(G)\rightarrow \{1,2,\ldots ,k\}\)〈/span〉 〈/span〉 for some 〈span〉 〈span〉\(k\in \mathbb {N}\)〈/span〉 〈/span〉, it asks if 〈em〉G〈/em〉 has a simple cycle of length 〈em〉k〈/em〉 containing each color in 〈span〉 〈span〉\(\{1,2,\ldots ,k\}\)〈/span〉 〈/span〉 exactly once. We study a generalization of these problems: Given a graph 〈em〉G〈/em〉, a set 〈span〉 〈span〉\(K\subseteq V(G)\)〈/span〉 〈/span〉, a list-coloring 〈span〉 〈span〉\(L: K\rightarrow 2^{\{1,2,\ldots ,k^*\}}\)〈/span〉 〈/span〉 for some 〈span〉 〈span〉\(k^*\in \mathbb {N}\)〈/span〉 〈/span〉 and a parameter 〈span〉 〈span〉\(k\in \mathbb {N}\)〈/span〉 〈/span〉, 〈span〉List〈/span〉〈span〉 〈span〉\(K\)〈/span〉 〈/span〉-〈span〉Cycle〈/span〉 asks if one can assign a color to each vertex in 〈em〉K〈/em〉 so that 〈em〉G〈/em〉 has a simple cycle (of arbitrary length) containing exactly 〈em〉k〈/em〉 vertices from 〈em〉K〈/em〉 with distinct colors. We design a randomized algorithm for 〈span〉List〈/span〉〈span〉 〈span〉\(K\)〈/span〉 〈/span〉-〈span〉Cycle〈/span〉 running in time 〈span〉 〈span〉\(2^kn^{{{\mathcal {O}}}(1)}\)〈/span〉 〈/span〉 on an 〈em〉n〈/em〉-vertex graph, matching the best known running times of algorithms for both 〈span〉 〈span〉\(K\)〈/span〉 〈/span〉-〈span〉Cycle〈/span〉 and 〈span〉Colorful Cycle〈/span〉. Moreover, unless the Set Cover Conjecture is false, our algorithm is essentially optimal. We also study a variant of 〈span〉List〈/span〉〈span〉 〈span〉\(K\)〈/span〉 〈/span〉-〈span〉Cycle〈/span〉 that generalizes the classic 〈span〉Hamiltonicity〈/span〉 problem, where one specifies the size of a solution. Our results integrate three related algebraic approaches, introduced by Björklund, Husfeldt and Taslaman (SODA’12), Björklund, Kaski and Kowalik (STACS’13), and Björklund (FOCS’10).〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉We consider the 〈em〉k〈/em〉-〈span〉Center〈/span〉 problem and some generalizations. For 〈em〉k〈/em〉-〈span〉Center〈/span〉 a set of 〈em〉k〈/em〉〈em〉center vertices〈/em〉 needs to be found in a graph 〈em〉G〈/em〉 with edge lengths, such that the distance from any vertex of 〈em〉G〈/em〉 to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded 〈em〉highway dimension〈/em〉, as proposed by Abraham et al. (SODA, pp 782–793, 〈span〉2010〈/span〉). We show both approximation and fixed-parameter hardness results, and how to overcome them using 〈em〉fixed-parameter approximations〈/em〉, where the two paradigms are combined. In particular, we prove that for any 〈span〉 〈span〉\({\varepsilon }〉0\)〈/span〉 〈/span〉 computing a 〈span〉 〈span〉\((2-{\varepsilon })\)〈/span〉 〈/span〉-approximation is W[2]-hard for parameter 〈em〉k〈/em〉, and NP-hard for graphs with highway dimension 〈span〉 〈span〉\(O(\log ^2 n)\)〈/span〉 〈/span〉. The latter does not rule out fixed-parameter 〈span〉 〈span〉\((2-{\varepsilon })\)〈/span〉 〈/span〉-approximations for the highway dimension parameter 〈em〉h〈/em〉, but implies that such an algorithm must have at least doubly exponential running time in 〈em〉h〈/em〉 if it exists, unless ETH fails. On the positive side, we show how to get below the approximation factor of 2 by combining the parameters 〈em〉k〈/em〉 and 〈em〉h〈/em〉: we develop a fixed-parameter 3 / 2-approximation with running time 〈span〉 〈span〉\(2^{O(kh\log h)}\cdot n^{O(1)}\)〈/span〉 〈/span〉. Additionally we prove that, unless P=NP, our techniques cannot be used to compute fixed-parameter 〈span〉 〈span〉\((2-{\varepsilon })\)〈/span〉 〈/span〉-approximations for only the parameter 〈em〉h〈/em〉. We also provide similar fixed-parameter approximations for the 〈span〉weighted〈/span〉〈em〉k〈/em〉-〈span〉Center〈/span〉 and 〈span〉 〈span〉\((k,{\mathcal {F}})\)〈/span〉 〈/span〉-〈span〉Partition〈/span〉 problems, which generalize 〈em〉k〈/em〉-〈span〉Center〈/span〉.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉Given a read-only memory for input and a write-only stream for output, an 〈em〉s〈/em〉-workspace algorithm, for a positive integer parameter 〈em〉s〈/em〉, is an algorithm using only 〈em〉O〈/em〉(〈em〉s〈/em〉) words of workspace in addition to the memory for the input. In this paper, we present an 〈span〉 〈span〉\(O(n^2/s)\)〈/span〉 〈/span〉-time 〈em〉s〈/em〉-workspace algorithm for subdividing a simple 〈em〉n〈/em〉-gon into 〈span〉 〈span〉\(O(\min \{n/s,s\})\)〈/span〉 〈/span〉 subpolygons of complexity 〈span〉 〈span〉\(O(\max \{n/s,s\})\)〈/span〉 〈/span〉. As applications of the subdivision, the previously best known time-space trade-offs for the following three geometric problems are improved immediately by adopting the proposed subdivision: (1) computing the shortest path between two points inside a simple 〈em〉n〈/em〉-gon, (2) computing the shortest-path tree from a point inside a simple 〈em〉n〈/em〉-gon, (3) computing a triangulation of a simple 〈em〉n〈/em〉-gon. In addition, we improve the algorithm for problem (2) further by applying different approaches depending on the size of the workspace.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉We present space-efficient algorithms for computing cut vertices in a given graph with 〈em〉n〈/em〉 vertices and 〈em〉m〈/em〉 edges in linear time using 〈span〉 〈span〉\(O(n+\min \{m,n\log \log n\})\)〈/span〉 〈/span〉 bits. With the same time and using 〈span〉 〈span〉\(O(n+m)\)〈/span〉 〈/span〉 bits, we can compute the biconnected components of a graph. We use this result to show an algorithm for the recognition of (maximal) outerplanar graphs in 〈span〉 〈span〉\(O(n\log \log n)\)〈/span〉 〈/span〉 time using 〈em〉O〈/em〉(〈em〉n〈/em〉) bits.〈/p〉

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same time (for example, by solving a single LP that combines the two players’ payoffs), our algorithm first solves two independent LPs, each of which is derived from one of the two payoff matrices, and then computes an approximate Nash equilibrium using only limited communication between the players. Our method gives improved bounds on the complexity of computing approximate Nash equilibria in a number of different settings. Firstly, it gives a polynomial-time algorithm for computing 〈em〉approximate well supported Nash equilibria (WSNE)〈/em〉 that always finds a 0.6528-WSNE, beating the previous best guarantee of 0.6608. Secondly, since our algorithm solves the two LPs separately, it can be applied to give an improved bound in the limited communication setting, giving a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and finds a 0.6528-WSNE, which beats the previous best known guarantee of 0.732. It can also be applied to the case of 〈em〉approximate Nash equilibria〈/em〉, where we obtain a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and always finds a 0.382-approximate Nash equilibrium, which improves the previous best guarantee of 0.438. Finally, the method can also be applied in the query complexity setting to give an algorithm that makes 〈span〉 〈span〉\(O(n \log n)\)〈/span〉 〈/span〉 payoff queries and always finds a 0.6528-WSNE, which improves the previous best known guarantee of 2/3.〈/p〉

Beschreibung: This paper deals with the modeling and optimization of a bi-level multi-objective production planning problem, where some of the coefficients of objective functions and parameters of constraints are multi-choice. A general transformation technique based on a binary variable has been used to transform the multi-choices parameters of the problem into their equivalent deterministic form. Finally, two different types of secularization technique have been used to achieve the maximum degree of individually membership goals by minimizing their deviational variables and obtained the most satisfactory solution of the formulated problem. An illustrative real case study of production planning has been discussed and, also compared to validate the efficiency and usefulness of the proposed work.

Beschreibung: The automatic train operation system is a significant component of the intelligent railway transportation. As a fundamental problem, the construction of the train dynamic model has been extensively researched using parametric approaches. The parametric based models may have poor performances due to unrealistic assumptions and changeable environments. In this paper, a long short-term memory network is carefully developed to build the train dynamic model in a nonparametric way. By optimizing the hyperparameters of the proposed model, more accurate outputs can be obtained with the same inputs of the parametric approaches. The proposed model was compared with two parametric methods using actual data. Experimental results suggest that the model performance is better than those of traditional models due to the strong learning ability. By exploring a detailed feature engineering process, the proposed long short-term memory network based algorithm was extended to predict train speed for multiple steps ahead.

Beschreibung: With the rapid expansion of applied 3D computational vision, shape descriptors have become increasingly important for a wide variety of applications and objects from molecules to planets. Appropriate shape descriptors are critical for accurate (and efficient) shape retrieval and 3D model classification. Several spectral-based shape descriptors have been introduced by solving various physical equations over a 3D surface model. In this paper, for the first time, we incorporate a specific manifold learning technique, introduced in statistics and machine learning, to develop a global, spectral-based shape descriptor in the computer graphics domain. The proposed descriptor utilizes the Laplacian Eigenmap technique in which the Laplacian eigenvalue problem is discretized using an exponential weighting scheme. As a result, our descriptor eliminates the limitations tied to the existing spectral descriptors, namely dependency on triangular mesh representation and high intra-class quality of 3D models. We also present a straightforward normalization method to obtain a scale-invariant and noise-resistant descriptor. The extensive experiments performed in this study using two standard 3D shape benchmarks—high-resolution TOSCA and McGill datasets—demonstrate that the present contribution provides a highly discriminative and robust shape descriptor under the presence of a high level of noise, random scale variations, and low sampling rate, in addition to the known isometric-invariance property of the Laplace–Beltrami operator. The proposed method significantly outperforms state-of-the-art spectral descriptors in shape retrieval and classification. The proposed descriptor is limited to closed manifolds due to its inherited inability to accurately handle manifolds with boundaries.

Beschreibung: Computed tomography (CT) image reconstruction and restoration are very important in medical image processing, and are associated together to be an inverse problem. Image iterative reconstruction is a key tool to increase the applicability of CT imaging and reduce radiation dose. Nevertheless, traditional image iterative reconstruction methods are limited by the sampling theorem and also the blurring of projection data will propagate unhampered artifact in the reconstructed image. To overcome these problems, image restoration techniques should be developed to accurately correct a wide variety of image degrading effects in order to effectively improve image reconstruction. In this paper, a blind image restoration technique is embedded in the compressive sensing CT image reconstruction, which can result in a high-quality reconstruction image using fewer projection data. Because a small amount of data can be obtained by radiation in a shorter time, high-quality image reconstruction with less data is equivalent to reducing radiation dose. Technically, both the blurring process and the sparse representation of the sharp CT image are first modeled as a serial of parameters. The sharp CT image will be obtained from the estimated sparse representation. Then, the model parameters are estimated by a hierarchical Bayesian maximum posteriori formulation. Finally, the estimated model parameters are optimized to obtain the final image reconstruction. We demonstrate the effectiveness of the proposed method with the simulation experiments in terms of the peak signal to noise ratio (PSNR), and structural similarity index (SSIM).

Beschreibung: This work addresses the physical layer channel code design for an uncoordinated, frame- and slot-asynchronous random access protocol. Starting from the observation that collisions between two users yield very specific interference patterns, we define a surrogate channel model and propose different protograph low-density parity-check code designs. The proposed codes are both tested in a setup where the physical layer is abstracted, as well as on a more realistic channel model, where finite-length physical layer simulations of the entire asynchronous random access scheme, including decoding, are carried out. We find that the abstracted physical layer model overestimates the performance when short blocks are considered. Additionally, the optimized codes show gains in supported channel traffic, a measure of the number of terminals that can be concurrently accommodated on the channel, of around 17% at a packet loss rate of 10 − 2 w.r.t. off-the-shelf codes.

Beschreibung: Aiming at the problems of low efficiency, heavy quality, and high cost of traditional components, it is necessary to study a design and analysis method of non-standard components. Taking the non-standard parts-turret loading and -unloading device as the carrier, the key parts of the non-standard parts are extracted for structural design and the multi-objective mathematical model and modal theory model are established. The optimization analysis of the key parts is carried out by genetic algorithm. Finally, the optimization results are compared and simulated by ANSYS Workbench. The results show that: in this case, the genetic algorithm optimized data with other data, the overall quality difference is 4.1%. The first six order modal values in the optimized results are in the range of 68 Hz to 130 Hz, which provides a basis for similar research in the future.

Beschreibung: Most of the architectural design problems are basically real-parameter optimization problems. So, any type of evolutionary and swarm algorithms can be used in this field. However, there is a little attention on using optimization methods within the computer aided design (CAD) programs. In this paper, we present Optimus, which is a new optimization tool for grasshopper algorithmic modeling in Rhinoceros CAD software. Optimus implements self-adaptive differential evolution algorithm with ensemble of mutation strategies (jEDE). We made an experiment using standard test problems in the literature and some of the test problems proposed in IEEE CEC 2005. We reported minimum, maximum, average, standard deviations and number of function evaluations of five replications for each function. Experimental results on the benchmark suite showed that Optimus (jEDE) outperforms other optimization tools, namely Galapagos (genetic algorithm), SilverEye (particle swarm optimization), and Opossum (RbfOpt) by finding better results for 19 out of 20 problems. For only one function, Galapagos presented slightly better result than Optimus. Ultimately, we presented an architectural design problem and compared the tools for testing Optimus in the design domain. We reported minimum, maximum, average and number of function evaluations of one replication for each tool. Galapagos and Silvereye presented infeasible results, whereas Optimus and Opossum found feasible solutions. However, Optimus discovered a much better fitness result than Opossum. As a conclusion, we discuss advantages and limitations of Optimus in comparison to other tools. The target audience of this paper is frequent users of parametric design modelling e.g., architects, engineers, designers. The main contribution of this paper is summarized as follows. Optimus showed that near-optimal solutions of architectural design problems can be improved by testing different types of algorithms with respect to no-free lunch theorem. Moreover, Optimus facilitates implementing different type of algorithms due to its modular system.

Beschreibung: For many parallel and distributed systems, automatic data redistribution improves its locality and increases system performance for various computer problems and applications. In general, an array can be distributed to multiple processing systems by using regular or irregular distributions. Some data distribution adopts BLOCK, CYCLIC, or BLOCK-CYCLIC to specify data array decomposition and distribution. On the other hand, irregular distributions specify a different-size data array distribution according to user-defined commands or procedures. In this work, we propose three bipartite graph problems, including the “maximum edge coloring problem”, the “maximum degree edge coloring problem”, and the “cost-sharing maximum edge coloring problem” to formulate these kinds of distribution problems. Next, we propose an approximation algorithm with a ratio bound of two for the maximum edge coloring problem when the input graph is biplanar. Moreover, we also prove that the “cost-sharing maximum edge coloring problem” is an NP-complete problem even when the input graph is biplanar.

Beschreibung: Augmented Reality is increasingly used for enhancing user experiences in different tasks. The present paper describes a model combining augmented reality and artificial intelligence algorithms in a 3D model of an area of the city of Coimbra, based on information extracted from OpenStreetMap. The augmented reality effect is achieved using a video projection over a 3D printed map. Users can interact with the model using a smart phone or similar device and simulate itineraries which are optimized using a genetic algorithm and A*. Among other applications, the model can be used for tourists or travelers to simulate travels with realism, as well as virtual reconstructions of historical places or remote areas.

Beschreibung: One of the most important functions of an export credit agency (ECA) is to act as an intermediary between national governments and exporters. These organizations provide financing to reduce the political and commercial risks in international trade. The agents assess the buyers based on financial and non-financial indicators to determine whether it is advisable to grant them credit. Because many of these indicators are qualitative and inherently linguistically ambiguous, the agents must make decisions in uncertain environments. Therefore, to make the most accurate decision possible, they often utilize fuzzy inference systems. The purpose of this research was to design a credit rating model in an uncertain environment using the fuzzy inference system (FIS). In this research, we used suitable variables of agency ratings from previous studies and then screened them via the Delphi method. Finally, we created a credit rating model using these variables and FIS including related IF-THEN rules which can be applied in a practical setting.

Beschreibung: Image clustering involves the process of mapping an archive image into a cluster such that the set of clusters has the same information. It is an important field of machine learning and computer vision. While traditional clustering methods, such as k-means or the agglomerative clustering method, have been widely used for the task of clustering, it is difficult for them to handle image data due to having no predefined distance metrics and high dimensionality. Recently, deep unsupervised feature learning methods, such as the autoencoder (AE), have been employed for image clustering with great success. However, each model has its specialty and advantages for image clustering. Hence, we combine three AE-based models—the convolutional autoencoder (CAE), adversarial autoencoder (AAE), and stacked autoencoder (SAE)—to form a hybrid autoencoder (BAE) model for image clustering. The MNIST and CIFAR-10 datasets are used to test the result of the proposed models and compare the results with others. The results of the clustering criteria indicate that the proposed models outperform others in the numerical experiment.

Beschreibung: The field of network science is a highly interdisciplinary area; for the empirical analysis of network data, it draws algorithmic methodologies from several research fields. Hence, research procedures and descriptions of the technical results often differ, sometimes widely. In this paper we focus on methodologies for the experimental part of algorithm engineering for network analysis—an important ingredient for a research area with empirical focus. More precisely, we unify and adapt existing recommendations from different fields and propose universal guidelines—including statistical analyses—for the systematic evaluation of network analysis algorithms. This way, the behavior of newly proposed algorithms can be properly assessed and comparisons to existing solutions become meaningful. Moreover, as the main technical contribution, we provide , a highly automated tool to perform and analyze experiments following our guidelines. To illustrate the merits of and our guidelines, we apply them in a case study: we design, perform, visualize and evaluate experiments of a recent algorithm for approximating betweenness centrality, an important problem in network analysis. In summary, both our guidelines and shall modernize and complement previous efforts in experimental algorithmics; they are not only useful for network analysis, but also in related contexts.

Beschreibung: 〈h3〉Abstract〈/h3〉 〈p〉The paper considers scheduling jobs online to minimize the objective 〈span〉 〈span〉\(\sum _{i \in [n]}w_ig(C_i-r_i)\)〈/span〉 〈/span〉, where 〈span〉 〈span〉\(w_i\)〈/span〉 〈/span〉 is the weight of job 〈em〉i〈/em〉, 〈span〉 〈span〉\(r_i\)〈/span〉 〈/span〉 is its release time, 〈span〉 〈span〉\(C_i\)〈/span〉 〈/span〉 is its completion time and 〈em〉g〈/em〉 is any non-decreasing convex function. It is known that the clairvoyant algorithm Highest-Density-First (HDF) is 〈span〉 〈span〉\((2+\epsilon )\)〈/span〉 〈/span〉-speed 〈em〉O〈/em〉(1)-competitive for this objective on a single machine for any fixed 〈span〉 〈span〉\( 0〈 \epsilon 〈 1\)〈/span〉 〈/span〉 (Im et al., in: ACM-SIAM symposium on discrete algorithms, pp 1254–1265, 〈span〉2012〈/span〉). In this paper, we give the first non-trivial results for this problem when 〈em〉g〈/em〉 is a non-decreasing convex function and the algorithm must be 〈em〉non-clairvoyant〈/em〉. More specifically, our results include:〈/p〉 〈ul〉 〈li〉 〈p〉A 〈span〉 〈span〉\((2+\epsilon )\)〈/span〉 〈/span〉-speed 〈em〉O〈/em〉(1)-competitive non-clairovyant algorithm on a single machine for all non-decreasing convex 〈em〉g〈/em〉, matching the performance of HDF for any fixed 〈span〉 〈span〉\( 0〈 \epsilon 〈 1\)〈/span〉 〈/span〉.〈/p〉 〈/li〉 〈li〉 〈p〉A 〈span〉 〈span〉\((3+\epsilon )\)〈/span〉 〈/span〉-speed 〈em〉O〈/em〉(1)-competitive non-clairovyant algorithm on multiple identical machines for all non-decreasing convex 〈em〉g〈/em〉 for any fixed 〈span〉 〈span〉\( 0〈 \epsilon 〈 1\)〈/span〉 〈/span〉.〈/p〉 〈/li〉 〈/ul〉 The paper gives the first non-trivial upper-bound on multiple machines even if the algorithm is allowed to be clairvoyant. All performance guarantees above hold for all non-decreasing convex functions 〈em〉g〈/em〉〈em〉simultaneously〈/em〉. The positive results are supplemented by almost matching lower bounds. We show that any algorithm that is oblivious to 〈em〉g〈/em〉 is not 〈em〉O〈/em〉(1)-competitive with speed augmentation less than 2 on a single machine. Further, any non-clairvoyent algorithm that knows the function 〈em〉g〈/em〉 cannot be 〈em〉O〈/em〉(1)-competitive with speed augmentation less than 〈span〉 〈span〉\(\sqrt{2}\)〈/span〉 〈/span〉 on a single machine or  〈span〉 〈span〉\((2-\frac{1}{m})\)〈/span〉 〈/span〉 on 〈em〉m〈/em〉 identical machines.

Beschreibung: A novel approach to defacement detection is proposed in this paper, addressing explicitly the possible presence of a passive adversary. Defacement detection is an important security measure for Web Sites and Applications, aimed at avoiding unwanted modifications that would result in significant reputational damage. As in many other anomaly detection contexts, the algorithm used to identify possible defacements is obtained via an Adversarial Machine Learning process. We consider an exploratory setting, where the adversary can observe the detector’s alarm-generating behaviour, with the purpose of devising and injecting defacements that will pass undetected. It is then necessary to make to learning process unpredictable, so that the adversary will be unable to replicate it and predict the classifier’s behaviour. We achieve this goal by introducing a secret key—a key that our adversary does not know. The key will influence the learning process in a number of different ways, that are precisely defined in this paper. This includes the subset of examples and features that are actually used, the time of learning and testing, as well as the learning algorithm’s hyper-parameters. This learning methodology is successfully applied in this context, by using the system with both real and artificially modified Web sites. A year-long experimentation is also described, referred to the monitoring of the new Web Site of a major manufacturing company.

Beschreibung: For a graph G = ( V , E ) , the γ -graph of G, denoted G ( γ ) = ( V ( γ ) , E ( γ ) ) , is the graph whose vertex set is the collection of minimum dominating sets, or γ -sets of G, and two γ -sets are adjacent in G ( γ ) if they differ by a single vertex and the two different vertices are adjacent in G. In this paper, we consider γ -graphs of trees. We develop an algorithm for determining the γ -graph of a tree, characterize which trees are γ -graphs of trees, and further comment on the structure of γ -graphs of trees and its connections with Cartesian product graphs, the set of graphs which can be obtained from the Cartesian product of graphs of order at least two.

Beschreibung: Home Healthcare (HHC) is an emerging and fast-expanding service sector that gives rise to challenging vehicle routing and scheduling problems. Each day, HHC structures must schedule the visits of caregivers to patients requiring specific medical and paramedical services at home. These operations have the potential to be unsuitable if the visits are not planned correctly, leading hence to high logistics costs and/or deteriorated service level. In this article, this issue is modeled as a vehicle routing problem where a set of routes has to be built to visit patients asking for one or more specific service within a given time window and during a fixed service time. Each patient has a preference value associated with each available caregiver. The problem addressed in this paper considers two objectives to optimize simultaneously: minimize the caregivers’ travel costs and maximize the patients’ preferences. In this paper, different methods based on the bi-objective non-dominated sorting algorithm are proposed to solve the vehicle routing problem with time windows, preferences, and timing constraints. Numerical results are presented for instances with up to 73 clients. Metrics such as the distance measure, hyper-volume, and the number of non-dominated solutions in the Pareto front are used to assess the quality of the proposed approaches.

Beschreibung: The satellite system is one of the most efficient means for broadcasting due to its wide service coverage as well as the fact that it can provide high data rate services by using high frequency bands. However, there are a number of problems in the satellite system, such as a long round trip delay (RTD) and heterogeneity of the channel conditions of the earth stations. Even though utilizing adaptive coding and modulation (ACM) is almost mandatory for the satellite systems using high frequency bands due to the serious rain fading, the long RTD makes it difficult to quickly respond to channel quality information, resulting in a decrease in the efficiency of ACM. A high heterogeneity of earth stations caused by a wide service coverage also makes it difficult to apply a uniform transmission mode, and thus satellite systems require receiver-dependent transmission modes. A rateless code can be an effective means to compensate for these disadvantages of satellite systems compared to terrestrial wireless systems. This paper presents soft iterative decoding algorithms for efficient application of rateless codes in satellite systems and demonstrates that rateless codes can be effectively used for hybrid automatic repeat request schemes.

Beschreibung: Intel recently introduced the Heterogeneous Architecture Research Platform, HARP. In this platform, the Central Processing Unit and a Field-Programmable Gate Array are connected through a high-bandwidth, low-latency interconnect and both share DRAM memory. For this platform, Open Computing Language (OpenCL), a High-Level Synthesis (HLS) language, is made available. By making use of HLS, a faster design cycle can be achieved compared to programming in a traditional hardware description language. This, however, comes at the cost of having less control over the hardware implementation. We will investigate how OpenCL can be applied to implement a real-time guided image filter on the HARP platform. In the first phase, the performance-critical parameters of the OpenCL programming model are defined using several specialized benchmarks. In a second phase, the guided image filter algorithm is implemented using the insights gained in the first phase. Both a floating-point and a fixed-point implementation were developed for this algorithm, based on a sliding window implementation. This resulted in a maximum floating-point performance of 135 GFLOPS, a maximum fixed-point performance of 430 GOPS and a throughput of HD color images at 74 frames per second.