Search

Personalized travel itinerary recommendation algorithms are the focus of research in smart tourism and tourism GIS. Aiming to address issues present in travel itinerary recommendations for the increasingly popular "self-drive tour" mode, this study proposes an algorithm based on comprehensive tourist satisfaction to mitigate problems such as the neglect of important relevant factors and low degree of personalization. First, we construct a model of tourist satisfaction for travel itineraries by comprehensively considering factors including time utilization, the attractiveness of attractions, itinerary feasibility, and the diversity of attraction types. Unlike previous studies, we consider dining and accommodation time during the itinerary, the physical condition of tourists, and the diversity of attraction types, and establish penalty functions to flexibly constrain deviations from the expected conditions in itinerary planning. Then, with the optimization of comprehensive tourist satisfaction as the objective, we design a new algorithm to address the itinerary recommendation problem, supporting tourists in selecting must-visit attractions, restaurants, and hotels, as well as personalized preferences such as the sightseeing sequence. The experimental results demonstrate that our proposed algorithm outperforms two baseline algorithms, providing higher comprehensive tourist satisfaction while also exhibiting greater feasibility in itinerary planning. The proposed algorithm effectively addresses the issue of personalized travel itinerary recommendation, presenting an efficient, feasible, and practical solution. [ABSTRACT FROM AUTHOR]

Solving combinatorial problems on complex networks represents a primary issue which, on a large scale, requires the use of heuristics and approximate algorithms. Recently, neural methods have been proposed in this context to find feasible solutions for relevant computational problems over graphs. However, such methods have some drawbacks: (1) they use the same neural architecture for different combinatorial problems without introducing customizations that reflects the specificity of each problem; (2) they only use a nodes local information to compute the solution; (3) they do not take advantage of common heuristics or exact algorithms. Following this interest, in this research we address these three main points by designing a customized attention-based mechanism that uses both local and global information from the adjacency matrix to find approximate solutions for the Minimum Vertex Cover Problem. We evaluate our proposal with respect to a fast two-factor approximation algorithm and a widely adopted state-of-the-art heuristic both on synthetically generated instances and on benchmark graphs with different scales. Experimental results demonstrate that, on the one hand, the proposed methodology is able to outperform both the two-factor approximation algorithm and the heuristic on the test datasets, scaling even better than the heuristic with harder instances and, on the other hand, is able to provide a representation of the nodes which reflects the combinatorial structure of the problem. [ABSTRACT FROM AUTHOR]

Aiming to address problems such as low sampling success rate and long computation time in the motion planning of a dual-arm cooperative system with multiple constraints, this paper proposes an Informed-Bi-Quick RRT* algorithm based on offline sampling. First, in the process of pre-sampling, the new algorithm relaxes the approximation of constrained manifolds by introducing the idea of incremental construction, and it incorporates the stochastic gradient descent method to replace global random sampling with local random sampling, which enriches the data set and shortens the offline sampling time of the data set. Second, the new algorithm improves the original Quick-RRT* algorithm by combining the two-tree idea and the multi-target bias expansion strategy, and it improves the adaptability of the algorithm to different obstacle environments. In addition, the loosely constrained motion and tightly constrained motion in the two-arm cooperative system are analyzed, and the adaptive planning of the two-arm trajectory in different motions is described in detail. In this paper, the two-arm cooperative model constructed with UR5 and UR10 robot arms is studied, and the ability of the proposed algorithm to deal with multiple constraints is verified by simulating assembly and handling tasks. The experimental results show that compared with other methods, the proposed algorithm has obvious advantages in path quality and planning efficiency. [ABSTRACT FROM AUTHOR]

Conceptual distance refers to the degree of proximity between two concepts within a conceptualization. It is closely related to semantic similarity and relationships, but its measurement strongly depends on the context of the given concepts. DIS-C represents an advancement in the computation of semantic similarity/relationships that is independent of the type of knowledge structure and semantic relations when generating a graph from a knowledge base (ontologies, semantic networks, and hierarchies, among others). This approach determines the semantic similarity between two indirectly connected concepts in an ontology by propagating local distances by applying an algorithm based on the All Pairs Shortest Path (APSP) problem. This process is implemented for each pair of concepts to establish the most effective and efficient paths to connect these concepts. The algorithm identifies the shortest path between concepts, which allows for an inference of the most relevant relationships between them. However, one of the critical issues with this process is computational complexity, combined with the design of APSP algorithms, such as Dijkstra, which is n 3 . This paper studies different alternatives to improve the DIS-C approach by adapting approximation algorithms, focusing on Dijkstra, pruned Dijkstra, and sketch-based methods, to compute the conceptual distance according to the need to scale DIS-C to analyze very large graphs; therefore, reducing the related computational complexity is critical. Tests were performed using different datasets to calculate the conceptual distance when using the original version of DIS-C and when using the influence area of nodes. In situations where time optimization is necessary for generating results, using the original DIS-C model is not the optimal method. Therefore, we propose a simplified version of DIS-C to calculate conceptual distances based on centrality estimation. The obtained results for the simple version of DIS-C indicated that the processing time decreased 2.381 times when compared to the original DIS-C version. Additionally, for both versions of DIS-C (normal and simple), the APSP algorithm decreased the computational cost when using a two-hop coverage-based approach. [ABSTRACT FROM AUTHOR]

The identifying code problem for a given graph involves finding a minimum subset of vertices such that each vertex of the graph is uniquely specified by its nonempty neighborhood within the identifying code. The combinatorial optimization problem has a wide variety of applications in location and detection schemes. Finding an identifying code of minimum possible size is a difficult task. In fact, it has been proven to be computationally intractable (NP-complete). Therefore, the use of heuristics to provide good approximations in a reasonable amount of time is justified. In this work, we present a new population-based local search algorithm for finding identifying codes of minimum cost. Computational experiments show that the proposed approach was found to be more effective than other state-of-the-art algorithms at generating high-quality solutions in different types of graphs with varying numbers of vertices. [ABSTRACT FROM AUTHOR]

Recently, complicated spatial search algorithms have emerged as spatial-information-based applications, such as location-based services (LBS), and have become very diverse and frequent. The aggregate nearest neighbor (ANN) search is an extension of the existing nearest neighbor (NN) search; it finds the object p * that minimizes G { d (p * , q i) , q i ∈ Q } from a set Q of M (≥1) query objects, where G is an aggregate function and d () is the distance between two objects. The flexible aggregate nearest neighbor (FANN) search is an extension of the ANN search by introducing flexibility factor  ϕ (0 < ϕ ≤ 1) ; it finds the object p * that minimizes G { d (p * , q i) , q i ∈ Q ϕ } from Q ϕ , a subset of Q with | Q ϕ | = ϕ | Q | . This paper proposes an efficient ϵ -approximate k-FANN (k ≥ 1) search algorithm for an arbitrary approximation ratio ϵ (≥1) in road networks. In general, ϵ -approximate algorithms are expected to give an improved search performance at the cost of allowing an error ratio of up to the given ϵ. Since the optimal value of ϵ varies greatly depending on applications and cases, the approximate algorithm for an arbitrary ϵ is essential. We prove that the error ratios of the approximate FANN objects returned by our algorithm do not exceed the given ϵ. To the best of our knowledge, our algorithm is the first ϵ -approximate k-FANN search algorithm in road networks for an arbitrary ϵ. Through a series of experiments using various real-world road network datasets, we demonstrated that our approximate algorithm always outperformed the previous state-of-the-art exact algorithm and that the error ratios of the approximate FANN objects were significantly lower than the given ϵ value. [ABSTRACT FROM AUTHOR]

Fuzzy rough set theory has been successfully applied to many attribute reduction methods, in which the lower approximation set plays a pivotal role. However, the definition of lower approximation used has ignored the information conveyed by the upper approximation and the boundary region. This oversight has resulted in an unreasonable relation representation of the target set. Despite the fact that scholars have proposed numerous enhancements to rough set models, such as the variable precision model, none have successfully resolved the issues inherent in the classical models. To address this limitation, this paper proposes an unsupervised attribute reduction algorithm for mixed data based on an improved optimal approximation set. Firstly, the theory of an improved optimal approximation set and its associated algorithm are proposed. Subsequently, we extend the classical theory of optimal approximation sets to fuzzy rough set theory, leading to the development of a fuzzy improved approximation set method. Finally, building on the proposed theory, we introduce a novel, fuzzy optimal approximation-set-based unsupervised attribute reduction algorithm (FOUAR). Comparative experiments conducted with all the proposed algorithms indicate the efficacy of FOUAR in selecting fewer attributes while maintaining and improving the performance of the machine learning algorithm. Furthermore, they highlight the advantage of the improved optimal approximation set algorithm, which offers higher similarity to the target set and provides a more concise expression. [ABSTRACT FROM AUTHOR]

The article presents the development of new physics-informed evolutionary neural network learning algorithms. These algorithms aim to address the challenges of ill-posed problems by constructing a population close to the Pareto front. The study focuses on comparing the algorithm's capabilities based on three quality criteria of solutions. To evaluate the algorithms' performance, two benchmark problems have been used. The first involved solving the Laplace equation in square regions with discontinuous boundary conditions. The second problem considered the absence of boundary conditions but with the presence of measurements. Additionally, the study investigates the influence of hyperparameters on the final results. Comparisons have been made between the proposed algorithms and standard algorithms for constructing neural networks based on physics (commonly referred to as vanilla's algorithms). The results demonstrate the advantage of the proposed algorithms in achieving better performance when solving incorrectly posed problems. Furthermore, the proposed algorithms have the ability to identify specific solutions with the desired smoothness. [ABSTRACT FROM AUTHOR]

In multi-access edge computing (MEC) networks, parallelized service function chains (P-SFCs) can provide low-delay network services for mobile users by deploying virtualized network functions (VNFs) to process user requests in parallel. These VNFs are unreliable due to software faults and server failures. A practical way to address this is to deploy idle backup VNFs (BVNFs) near these active VNFs and activate them when active VNFs fail. However, deploying BVNFs preempts server resources and decreases the number of accepted user requests. Thus, this paper proposes a reliability enhancement approach that uses BVNFs satisfying the delay requirement as active VNFs to form P-SFCs, which contributes to the delay reduction and reliability enhancement. Since the resource capacities of edge servers can only deploy a certain number of P-SFCs and BVNFs, establishing how to deploy the minimum number of P-SFCs and BVNFs to satisfy the delay and reliability requirements of mobile users and maximize the number of accepted user requests is a challenging problem. In this paper, we first model the dynamics of delay and reliability caused by VNF parallelization and BVNFs deployment, then formulate the joint deployment problem of P-SFCs and BVNFs. Next, we design an approximation algorithm to deploy critical VNFs and BVNFs on a target edge server and schedule the data traffic of user requests processed by P-SFCs. Experimental results based on real-world datasets show that our proposed algorithm outperforms two benchmark algorithms in terms of throughput, delay, reliability, and resource utilization. [ABSTRACT FROM AUTHOR]

The Internet of Things (IoT) has become increasingly popular, and its communication requirements have grown beyond what traditional ground networks can handle. The space–air–ground (SAG) integrated network has been proposed as a potential solution, where unmanned aerial vehicles (UAVs) collect data from IoT devices and transmit them to satellites. However, the limited energy of UAVs is one of the key factors restricting communication performance, so it is necessary to consider communication energy efficiency (EE). In addition, the improvement of EE will bring about the decline of spectral efficiency (SE). Therefore we consider the tradeoff between EE and SE. Considering a SAG-IoT network, the focus of the paper is to optimize sub-channel selection, power control, and UAV position deployment to maximize EE and SE of the network, which is a multi-objective optimization (MOO) problem. On this premise, we try to improve the data throughput between IoT devices and UAVs. To solve this MOO problem, we use the ϵ -constraint to convert it into a single-objective optimization problem. We then employ various optimization algorithms such as the Dinkelbach algorithm, successive convex approximation algorithm, Lagrange dual algorithm, and block coordinate descent algorithm to solve the mixed integer non-convex problem. Simulation results show that the proposed algorithm converges to at least one sub-optimal solution. [ABSTRACT FROM AUTHOR]

Featured Application: This article assesses different text representations for labeling unmarked dialog data, which can be applied to identify user intents directly relevant to dialog systems. Chatbots are becoming increasingly popular and require the ability to interpret natural language to provide clear communication with humans. To achieve this, intent detection is crucial. However, current applications typically need a significant amount of annotated data, which is time-consuming and expensive to acquire. This article assesses the effectiveness of different text representations for annotating unlabeled dialog data through a pipeline that examines both classical approaches and pre-trained transformer models for word embedding. The resulting embeddings were then used to create sentence embeddings through pooling, followed by dimensionality reduction, before being fed into a clustering algorithm to determine the user's intents. Therefore, various pooling, dimension reduction, and clustering algorithms were evaluated to determine the most appropriate approach. The evaluation dataset contains a variety of user intents across different domains, with varying intent taxonomies within the same domain. Results demonstrate that transformer-based models perform better text representation than classical approaches. However, combining several clustering algorithms and embeddings from dissimilar origins through ensemble clustering considerably improves the final clustering solution. Additionally, applying the uniform manifold approximation and projection algorithm for dimension reduction can substantially improve performance (up to 20%) while using a much smaller representation. [ABSTRACT FROM AUTHOR]

We consider a variant of the k-center clustering problem in I R d , where the centers can be divided into two subsets—one, the red centers of size p, and the other, the blue centers of size q, such that p + q = k , and each red center and each blue center must be a distance of at least some given α ≥ 0 apart. The aim is to minimize the covering radius. We provide a bi-criteria approximation algorithm for the problem and a polynomial time algorithm for the constrained problem where all centers must lie on a given line ℓ. Additionally, we present a polynomial time algorithm for the case where only the orientation of the line is fixed in the plane ( d = 2 ), although the algorithm works even in I R d by constraining the line to lie in a plane and with a fixed orientation. [ABSTRACT FROM AUTHOR]

The variational quantum algorithm (VQA) is a hybrid classical–quantum algorithm. It can actually run in an intermediate-scale quantum device where the number of available qubits is too limited to perform quantum error correction, so it is one of the most promising quantum algorithms in the noisy intermediate-scale quantum era. In this paper, two ideas for solving the learning with errors problem (LWE) using VQA are proposed. First, after reducing the LWE problem into the bounded distance decoding problem, the quantum approximation optimization algorithm (QAOA) is introduced to improve classical methods. Second, after the LWE problem is reduced into the unique shortest vector problem, the variational quantum eigensolver (VQE) is used to solve it, and the number of qubits required is calculated in detail. Small-scale experiments are carried out for the two LWE variational quantum algorithms, and the experiments show that VQA improves the quality of the classical solutions. [ABSTRACT FROM AUTHOR]

In atmospheric laser communication, a beam is transmitted through an atmospheric channel, and the photocurrent output from a quadrant detector (QD) used as the tracking sensor fluctuates significantly. To ensure uninterrupted communication and to adapt to such fluctuations, in this paper we apply logarithmic amplifiers to process the output signals of a QD. To further improve the measurement accuracy of the spot position, we firstly propose an integral infinite log-ratio algorithm (IILRA) and an integral infinity log-ratio algorithm based on the signal-to-noise ratio (BSNR-IILRA) through analysis of the factors influencing the measurement error considering the signal-to-noise ratio (SNR) parameter. Secondly, the measurement error of the two algorithms under different SNRs and their variations are analyzed. Finally, a spot position detection experiment platform is built to correctly and efficiently verify the two algorithms. The experimental results show that when the SNR is 54.10 dB, the maximum error and root mean square error of the spot position of the IILRA are 0.0054 mm and 0.0039 mm, respectively, which are less than half those of the center approximation algorithm (CAA). When the SNR is 23.88 dB, the maximum error and root mean square error of the spot position of the BSNR-IILRA are 0.0046 mm and 0.0034 mm, respectively, which are one-thirtieth and one-twentieth of the CAA, respectively. The spot position measurement accuracy of the two proposed algorithms is significantly improved compared with the CAA. [ABSTRACT FROM AUTHOR]

Research into the recent developments for solving fractional mathematical equations requires accurate and efficient numerical methods. Although many numerical methods based on Caputo's fractional derivative have been proposed to solve fractional mathematical equations, the efficiency of obtaining solutions using these methods when dealing with a large matrix requires further study. The matrix size influences the accuracy of the solution. Therefore, this paper proposes a quarter-sweep finite difference scheme with a preconditioned relaxation-based approximation to efficiently solve a large matrix, which is based on the establishment of a linear system for a fractional mathematical equation. The paper presents the formulation of the quarter-sweep finite difference scheme that is used to approximate the selected fractional mathematical equation. Then, the derivation of a preconditioned relaxation method based on a quarter-sweep scheme is discussed. The design of a C++ algorithm of the proposed quarter-sweep preconditioned relaxation method is shown and, finally, efficiency analysis comparing the proposed method with several tested methods is presented. The contributions of this paper are the presentation of a new preconditioned matrix to restructure the developed linear system, and the derivation of an efficient preconditioned relaxation iterative method for solving a fractional mathematical equation. By simulating the solutions of timefractional diffusion problems with the proposed numerical method, the study found that computing solutions using the quarter-sweep preconditioned relaxation method is more efficient than using the tested methods. The proposed numerical method is able to solve the selected problems with fewer iterations and a faster execution time than the tested existing methods. The efficiency of the methods was evaluated using different matrix sizes. Thus, the combination of a quarter-sweep finite difference method, Caputo's time-fractional derivative, and the preconditioned successive over-relaxation method showed good potential for solving different types of fractional mathematical equations, and provides a future direction for this field of research. [ABSTRACT FROM AUTHOR]

In this study, the MODerate resolution Imaging Spectroradiometer (MODIS) Collections 6 and 6.1 merged Dark Target (DT) and Deep Blue (DB) aerosol products (DTBC6 and DTBC6.1) at 0.55 μm were validated from 2004-2014 against Aerosol Robotic Network (AERONET) Version 2 Level 2.0 AOD obtained from 68 global sites located over diverse vegetated surfaces. These surfaces were categorized by static values of monthly Normalized Difference Vegetation Index (NDVI) observations obtained for the same time period from the MODIS level-3 monthly NDVI product (MOD13A3), i.e., partially/non-vegetated (NDVIP ≤ 0.3), moderately-vegetated (0.3 < NDVIM ≤ 0.5) and densely-vegetated (NDVID > 0.5) surfaces. The DTBC6 and DTBC6.1 AOD products are accomplished by the NDVI criteria: (i) use the DT AOD retrievals for NDVI > 0.3, (ii) use the DB AOD retrievals for NDVI < 0.2, and (iii) use an average of the DT and DB AOD retrievals or the available one with highest quality assurance flag (DT: QAF = 3; DB: QAF ≥ 2) for 0.2 ≤ NDVI ≤ 0.3. For comparison purpose, the DTBSMS AOD retrievals were included which were accomplished using the Simplified Merge Scheme, i.e., use an average of the DTC6.1 and DBC6.1 AOD retrievals or the available one for all the NDVI values. For NDVIP surfaces, results showed that the DTBC6 and DTBC6.1 AOD retrievals performed poorly over North and South America in terms of the agreement with AERONET AOD, and over Asian region in terms of retrievals quality as the small percentage of AOD retrievals were within the expected error (EE = ± (0.05 + 0.15 × AOD). For NDVIM surfaces, retrieval errors and poor quality in DTBC6 and DTBC6.1 were observed for Asian, North American and South American sites, whereas good performance, was observed for European and African sites. For NDVID surfaces, DTBC6 does not perform well over the Asian and North American sites, although it contains retrievals only from the DT algorithm which was developed for dark surfaces. Overall, the performance of the DTBC6.1 AOD retrievals was significantly improved compared to the DTBC6, but still more improvements are required over NDVIP, NDVIM and NDVID surfaces of Asia, NDVIM and NDVID surfaces of North America, and NDVIM surfaces of South America. The performance of the DTBSMS retrievals was better than the DTBC6 and DTBC6.1 retrievals with 11-13% (31%) greater number of coincident observations, 6-9% (14-22%) greater percentage of retrievals within the EE, and 30-100% (46-100%) smaller relative mean bias compared to the DTBC6.1 (DTBC6) at a global scale. [ABSTRACT FROM AUTHOR]

Mastermind is a two players zero sum game of imperfect information. Starting with Erdős and Rényi (1963), its combinatorics have been studied to date by several authors, e.g., Knuth (1977), Chvátal (1983), Goodrich (2009). The first player, called "codemaker", chooses a secret code and the second player, called "codebreaker", tries to break the secret code by making as few guesses as possible, exploiting information that is given by the codemaker after each guess. For variants that allow color repetition, Doerr et al. (2016) showed optimal results. In this paper, we consider the so called Black-Peg variant of Mastermind, where the only information concerning a guess is the number of positions in which the guess coincides with the secret code. More precisely, we deal with a special version of the Black-Peg game with n holes and k ≥ n colors where no repetition of colors is allowed. We present upper and lower bounds on the number of guesses necessary to break the secret code. For the case k = n, the secret code can be algorithmically identified within less than (n - 3)dlog2 ne + 52 n - 1 queries. This result improves the result of Ker-I Ko and Shia-Chung Teng (1985) by almost a factor of 2. For the case k = n, we prove an upper bound of (n - 2)[log2] + k +1. Furthermore, we prove a new lower bound of n for the case k = n, which improves the recent n - log log(n) bound of Berger et al. (2016). We then generalize this lower bound to k queries for the case k ≥ n. [ABSTRACT FROM AUTHOR]

Metric k-center clustering is a fundamental unsupervised learning primitive. Although widely used, this primitive is heavily affected by noise in the data, so a more sensible variant seeks for the best solution that disregards a given number z of points of the dataset, which are called outliers. We provide efficient algorithms for this important variant in the streaming model under the sliding window setting, where, at each time step, the dataset to be clustered is the window W of the most recent data items. For general metric spaces, our algorithms achieve O 1 approximation and, remarkably, require a working memory linear in k + z and only logarithmic in | W | . For spaces of bounded doubling dimension, the approximation can be made arbitrarily close to 3. For these latter spaces, we show, as a by-product, how to estimate the effective diameter of the window W, which is a measure of the spread of the window points, disregarding a given fraction of noisy distances. We also provide experimental evidence of the practical viability of the improved clustering and diameter estimation algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we consider parallel-machine scheduling with release times and submodular penalties ( P | r j , r e j e c t | C max + π (R) ), in which each job can be accepted and processed on one of m identical parallel machines or rejected, but a penalty must paid if a job is rejected. Each job has a release time and a processing time, and the job can not be processed before its release time. The objective of P | r j , r e j e c t | C max + π (R) is to minimize the makespan of the accepted jobs plus the penalty of the rejected jobs, where the penalty is determined by a submodular function. This problem generalizes a multiprocessor scheduling problem with rejection, the parallel-machine scheduling with submodular penalties, and the single machine scheduling problem with release dates and submodular rejection penalties. In this paper, inspired by the primal-dual method, we present a combinatorial 2-approximation algorithm to P | r j , r e j e c t | C max + π (R) . This ratio coincides with the best known ratio for the parallel-machine scheduling with submodular penalties and the single machine scheduling problem with release dates and submodular rejection penalties. [ABSTRACT FROM AUTHOR]

In this work, we give provable sieving algorithms for the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) on lattices in ℓ p norm ( 1 ≤ p ≤ ∞ ). The running time we obtain is better than existing provable sieving algorithms. We give a new linear sieving procedure that works for all ℓ p norm ( 1 ≤ p ≤ ∞ ). The main idea is to divide the space into hypercubes such that each vector can be mapped efficiently to a sub-region. We achieve a time complexity of 2 2.751 n + o (n) , which is much less than the 2 3.849 n + o (n) complexity of the previous best algorithm. We also introduce a mixed sieving procedure, where a point is mapped to a hypercube within a ball and then a quadratic sieve is performed within each hypercube. This improves the running time, especially in the ℓ 2 norm, where we achieve a time complexity of 2 2.25 n + o (n) , while the List Sieve Birthday algorithm has a running time of 2 2.465 n + o (n) . We adopt our sieving techniques to approximation algorithms for SVP and CVP in ℓ p norm ( 1 ≤ p ≤ ∞ ) and show that our algorithm has a running time of 2 2.001 n + o (n) , while previous algorithms have a time complexity of 2 3.169 n + o (n) . [ABSTRACT FROM AUTHOR]

This paper investigates resource optimization schemes in a marine communication scenario based on non-orthogonal multiple access (NOMA). According to the offshore environment of the South China Sea, we first establish a Longley–Rice-based channel model. Then, the weighted achievable rate (WAR) is considered as the optimization objective to weigh the information rate and user fairness effectively. Our work introduces an improved joint power and user allocation scheme (RBPUA) based on a single resource block. Taking RBPUA as a basic module, we propose three joint multi-subchannel power and marine user allocation algorithms. The gradient descent algorithm (GRAD) is used as the reference standard for WAR optimization. The multi-choice knapsack algorithm combined with dynamic programming (MCKP-DP) obtains a WAR optimization result almost equal to that of GRAD. These two NOMA-based solutions are able to improve WAR performance by 7.47% compared with OMA. Due to the high computational complexity of the MCKP-DP, we further propose a DP-based fully polynomial-time approximation algorithm (DP-FPTA). The simulation results show that DP-FPTA can reduce the complexity by 84.3% while achieving an approximate optimized performance of 99.55%. This advantage of realizing the trade-off between performance optimization and complexity meets the requirements of practical low-latency systems. [ABSTRACT FROM AUTHOR]

Coreset is usually a small weighted subset of an input set of items, that provably approximates their loss function for a given set of queries (models, classifiers, hypothesis). That is, the maximum (worst-case) error over all queries is bounded. To obtain smaller coresets, we suggest a natural relaxation: coresets whose average error over the given set of queries is bounded. We provide both deterministic and randomized (generic) algorithms for computing such a coreset for any finite set of queries. Unlike most corresponding coresets for the worst-case error, the size of the coreset in this work is independent of both the input size and its Vapnik–Chervonenkis (VC) dimension. The main technique is to reduce the average-case coreset into the vector summarization problem, where the goal is to compute a weighted subset of the n input vectors which approximates their sum. We then suggest the first algorithm for computing this weighted subset in time that is linear in the input size, for n ≫ 1 / ε , where ε is the approximation error, improving, e.g., both [ICML'17] and applications for principal component analysis (PCA) [NIPS'16]. Experimental results show significant and consistent improvement also in practice. Open source code is provided. [ABSTRACT FROM AUTHOR]

A common technique for compressing a neural network is to compute the k-rank ℓ 2 approximation A k of the matrix A ∈ R n × d via SVD that corresponds to a fully connected layer (or embedding layer). Here, d is the number of input neurons in the layer, n is the number in the next one, and A k is stored in O ((n + d) k) memory instead of O (n d) . Then, a fine-tuning step is used to improve this initial compression. However, end users may not have the required computation resources, time, or budget to run this fine-tuning stage. Furthermore, the original training set may not be available. In this paper, we provide an algorithm for compressing neural networks using a similar initial compression time (to common techniques) but without the fine-tuning step. The main idea is replacing the k-rank ℓ 2 approximation with ℓ p , for p ∈ [ 1 , 2 ] , which is known to be less sensitive to outliers but much harder to compute. Our main technical result is a practical and provable approximation algorithm to compute it for any p ≥ 1 , based on modern techniques in computational geometry. Extensive experimental results on the GLUE benchmark for compressing the networks BERT, DistilBERT, XLNet, and RoBERTa confirm this theoretical advantage. [ABSTRACT FROM AUTHOR]

In this note, given a matrix A ∈ C n × n (or a general matrix polynomial P (z) , z ∈ C ) and an arbitrary scalar λ 0 ∈ C , we show how to define a sequence μ k k ∈ N which converges to some element of its spectrum. The scalar λ 0 serves as initial term ( μ 0 = λ 0 ), while additional terms are constructed through a recursive procedure, exploiting the fact that each term μ k of this sequence is in fact a point lying on the boundary curve of some pseudospectral set of A (or P (z) ). Then, the next term in the sequence is detected in the direction which is normal to this curve at the point μ k . Repeating the construction for additional initial points, it is possible to approximate peripheral eigenvalues, localize the spectrum and even obtain spectral enclosures. Hence, as a by-product of our method, a computationally cheap procedure for approximate pseudospectra computations emerges. An advantage of the proposed approach is that it does not make any assumptions on the location of the spectrum. The fact that all computations are performed on some dynamically chosen locations on the complex plane which converge to the eigenvalues, rather than on a large number of predefined points on a rigid grid, can be used to accelerate conventional grid algorithms. Parallel implementation of the method or use in conjunction with randomization techniques can lead to further computational savings when applied to large-scale matrices. [ABSTRACT FROM AUTHOR]

The stochastic approximation algorithm (SAA), starting from the pioneer work by Robbins and Monro in 1950s, has been successfully applied in systems and control, statistics, machine learning, and so forth. In this paper, we will review the development of SAA in China, to be specific, the stochastic approximation algorithm with expanding truncations (SAAWET) developed by Han-Fu Chen and his colleagues during the past 35 years. We first review the historical development for the centralized algorithm including the probabilistic method (PM) and the ordinary differential equation (ODE) method for SAA and the trajectory-subsequence method for SAAWET. Then, we will give an application example of SAAWET to the recursive principal component analysis. We will also introduce the recent progress on SAAWET in a networked and distributed setting, named the distributed SAAWET (DSAAWET). [ABSTRACT FROM AUTHOR]

The dwell time algorithm is one of the key technologies that determines the accuracy of a workpiece in the field of ultra-precision computer-controlled optical surfacing. Existing algorithms mainly consider meticulous mathematics theory and high convergence rates, making the computation process more uneven, and the flatness cannot be further improved. In this paper, a reasonable elementary approximation algorithm of dwell time is proposed on the basis of the theoretical requirement of a removal function in the subaperture polishing and single-peak rotational symmetry character of its practical distribution. Then, the algorithm is well discussed with theoretical analysis and numerical simulation in cases of one-dimension and two-dimensions. In contrast to conventional dwell time algorithms, this proposed algorithm transforms superposition and coupling features of the deconvolution problem into an elementary approximation issue of function value. Compared with the conventional methods, it has obvious advantages for improving calculation efficiency and flatness, and is of great significance for the efficient computation of large-aperture optical polishing. The flatness of φ150 mm and φ100 mm workpieces have achieved PVr150 = 0.028 λ and PVcr100 = 0.014 λ respectively. [ABSTRACT FROM AUTHOR]

The Lattice String Approximation algorithm (or LSA algorithm) of M. L. Lapidus and M. van Frankenhuijsen is a procedure that approximates the complex dimensions of a nonlattice self-similar fractal string by the complex dimensions of a lattice self-similar fractal string. The implication of this procedure is that the set of complex dimensions of a nonlattice string has a quasiperiodic pattern. Using the LSA algorithm, together with the multiprecision polynomial solver MPSolve which is due to D. A. Bini, G. Fiorentino and L. Robol, we give a new and significantly more powerful presentation of the quasiperiodic patterns of the sets of complex dimensions of nonlattice self-similar fractal strings. The implementation of this algorithm requires a practical method for generating simultaneous Diophantine approximations, which in some cases we can accomplish by the continued fraction process. Otherwise, as was suggested by Lapidus and van Frankenhuijsen, we use the LLL algorithm of A. K. Lenstra, H. W. Lenstra, and L. Lovász. [ABSTRACT FROM AUTHOR]

This paper studies a semilinear parabolic equation in 1D along with nonlocal boundary conditions. The value at each boundary point is associated with the value at an interior point of the domain, which is known as a four-point boundary condition. First, the solvability of a steady-state problem is addressed and a constructive algorithm for finding a solution is proposed. Combining this schema with the semi-discretization in time, a constructive algorithm for approximation of a solution to a transient problem is developed. The well-posedness of the problem is shown using the semigroup theory in C-spaces. Numerical experiments support the theoretical algorithms. [ABSTRACT FROM AUTHOR]

We present an algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. In order to be efficient in terms of both time and space, our algorithm is based on a decomposition strategy which partitions the graph into disjoint clusters of bounded radius. Theoretically, our algorithm uses linear space and yields a polylogarithmic approximation guarantee; most importantly, for a large family of graphs, it features a round complexity asymptotically smaller than the one exhibited by a natural approximation algorithm based on the state-of-the-art Δ -stepping SSSP algorithm, which is its only practical, linear-space competitor in the distributed setting. We complement our theoretical findings with a proof-of-concept experimental analysis on large benchmark graphs, which suggests that our algorithm may attain substantial improvements in terms of running time compared to the aforementioned competitor, while featuring, in practice, a similar approximation ratio. [ABSTRACT FROM AUTHOR]

The Influence Maximization (IM) problem, which finds a set of k nodes (called seedset) in a social network to initiate the influence spread so that the number of influenced nodes after propagation process is maximized, is an important problem in information propagation and social network analysis. However, previous studies ignored the constraint of priority that led to inefficient seed collections. In some real situations, companies or organizations often prioritize influencing potential users during their influence diffusion campaigns. With a new approach to these existing works, we propose a new problem called Influence Maximization with Priority (IMP) which finds out a set seed of k nodes in a social network to be able to influence the largest number of nodes subject to the influence spread to a specific set of nodes U (called priority set) at least a given threshold T in this paper. We show that the problem is NP-hard under well-known IC model. To find the solution, we propose two efficient algorithms, called Integrated Greedy (IG) and Integrated Greedy Sampling (IGS) with provable theoretical guarantees. IG provides a 1 − (1 − 1 k) t -approximation solution with t is an outcome of algorithm and t ≥ 1 . The worst-case approximation ratio is obtained when t = 1 and it is equal to 1 / k . In addition, IGS is an efficient randomized approximation algorithm based on sampling method that provides a 1 − (1 − 1 k) t − ϵ -approximation solution with probability at least 1 − δ with ϵ > 0 , δ ∈ (0 , 1) as input parameters of the problem. We conduct extensive experiments on various real networks to compare our IGS algorithm to the state-of-the-art algorithms in IM problem. The results indicate that our algorithm provides better solutions interns of influence on the priority sets when approximately give twice to ten times higher than threshold T while running time, memory usage and the influence spread also give considerable results compared to the others. [ABSTRACT FROM AUTHOR]

We suggest a provable and practical approximation algorithm for fitting a set P of n points in R d to a sphere. Here, a sphere is represented by its center x ∈ R d and radius r > 0 . The goal is to minimize the sum ∑ p ∈ P ∣ p − x − r ∣ of distances to the points up to a multiplicative factor of 1 ± ε , for a given constant ε > 0 , over every such r and x. Our main technical result is a data summarization of the input set, called coreset, that approximates the above sum of distances on the original (big) set P for every sphere. Then, an accurate sphere can be extracted quickly via an inefficient exhaustive search from the small coreset. Most articles focus mainly on sphere identification (e.g., circles in 2 D image) rather than finding the exact match (in the sense of extent measures), and do not provide approximation guarantees. We implement our algorithm and provide extensive experimental results on both synthetic and real-world data. We then combine our algorithm in a mechanical pressure control system whose main bottleneck is tracking a falling ball. Full open source is also provided. [ABSTRACT FROM AUTHOR]

We propose two new iterative algorithms for solving K-pseudomonotone variational inequality problems in the framework of real Hilbert spaces. These newly proposed methods are obtained by combining the viscosity approximation algorithm, the Picard Mann algorithm and the inertial subgradient extragradient method. We establish some strong convergence theorems for our newly developed methods under certain restriction. Our results extend and improve several recently announced results. Furthermore, we give several numerical experiments to show that our proposed algorithms performs better in comparison with several existing methods. [ABSTRACT FROM AUTHOR]

Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions. [ABSTRACT FROM AUTHOR]

The real implementation of the maximum power point tracking (MPPT) controllers for the photovoltaic (PV) systems is still a big challenge for researchers working in this field. Often, they use simulation tools to assess the performance of their MPPT algorithms before actual implementation. In this context, this paper aims to propose a trusted simulation of a PV system designed under Proteus software. The proposed PV simulator can be used to verify and evaluate the performance of MPPT algorithms with a closer approximation to the real implementation. The main advantage of this model that it contains a real microcontroller, as can be found in reality, so that same code for the MPPT algorithm used in the simulation will be used in real implementation. In contrast, when using (Powersim Software) PSIM or Matlab/Simulink, the code of the algorithm must be rewritten once the real experiment begins, because these tools don't provide a microcontroller or an electronic board in which our algorithm can be implemented and tested in the same way as the real experiment. After this section, a modified Hill-Climbing (HC) algorithm is introduced. The proposed algorithm can avoid the drift problem posed by conventional HC under a fast variation in insolation. The simulation results show that this method presents good performance in terms of efficiency (99.21%) and response time (10 ms), which improved by 1.2% and 70 ms respectively compared to the conventional HC algorithm. [ABSTRACT FROM AUTHOR]

Proposed algorithms for calculating the shortest paths such as Dijikstra and Flowd-Warshall's algorithms are limited to small networks due to computational complexity and cost. We propose an efficient and a more accurate approximation algorithm that is applicable to large scale networks. Our algorithm iteratively constructs levels of hierarchical networks by a node condensing procedure to construct hierarchical graphs until threshold. The shortest paths between nodes in the original network are approximated by considering their corresponding shortest paths in the highest hierarchy. Experiments on real life data show that our algorithm records high efficiency and accuracy compared with other algorithms. [ABSTRACT FROM AUTHOR]

The purpose of this special issue of Algorithms was to attract papers presenting original research in the area of algorithm engineering. In particular, submissions concerning the design, analysis, implementation, tuning, and experimental evaluation of discrete algorithms and data structures, and/or addressing methodological issues and standards in algorithmic experimentation were encouraged. Papers dealing with advanced models of computing, including memory hierarchies, cloud architectures, and parallel processing were also welcome. In this regard, we solicited contributions from all most prominent areas of applied algorithmic research, which include but are not limited to graphs, databases, computational geometry, big data, networking, combinatorial aspects of scientific computing, and computational problems in the natural sciences or engineering. [ABSTRACT FROM AUTHOR]

The split feasibility problem models inverse problems arising from phase retrievals problems and intensity-modulated radiation therapy. For solving the split feasibility problem, Xu proposed a relaxed CQ algorithm that only involves projections onto half-spaces. In this paper, we use the dual variable to propose a new relaxed CQ iterative algorithm that generalizes Xu's relaxed CQ algorithm in real Hilbert spaces. By using projections onto half-spaces instead of those onto closed convex sets, the proposed algorithm is implementable. Moreover, we present modified relaxed CQ algorithm with viscosity approximation method. Under suitable conditions, global weak and strong convergence of the proposed algorithms are proved. Some numerical experiments are also presented to illustrate the effectiveness of the proposed algorithms. Our results improve and extend the corresponding results of Xu and some others. [ABSTRACT FROM AUTHOR]

Covering the edges of a bipartite graph by a minimum set of bipartite complete graphs (bicliques) is a basic graph theoretic problem, with numerous applications. In particular, it is used to characterize parsimonious models of a set of observations (each biclique corresponds to a factor or feature that relates the observations in the two sets of nodes connected by the biclique). The decision version of the minimum biclique cover problem is NP-Complete, and unless P = N P , the cover size cannot be approximated in general within less than a sub-linear factor of the number of nodes (or edges) in the graph. In this work, we consider two natural restrictions to the problem, motivated by practical applications. In the first case, we restrict the number of bicliques a node can belong to. We show that when this number is at least 5, the problem is still NP-hard. In contrast, we show that when nodes belong to no more than two bicliques, the problem has efficient approximations. The second model we consider corresponds to observing a set of independent samples from an unknown model, governed by a possibly large number of factors. The model is defined by a bipartite graph G = ( L , R , E ) , where each node in L is assigned to an arbitrary subset of up to a constant f factors, while the nodes in R (the independent observations) are assigned to random subsets of the set of k factors where k can grow with size of the graph. We show that this practical version of the biclique cover problem is amenable to efficient approximations. [ABSTRACT FROM AUTHOR]

Demographic estimation of human face images involves estimation of age group, gender, and race, which finds many applications, such as access control, forensics, and surveillance. Demographic estimation can help in designing such algorithms which lead to better understanding of the facial aging process and face recognition. Such a study has two parts—demographic estimation and subsequent face recognition and retrieval. In this paper, first we extract facial-asymmetry-based demographic informative features to estimate the age group, gender, and race of a given face image. The demographic features are then used to recognize and retrieve face images. Comparison of the demographic estimates from a state-of-the-art algorithm and the proposed approach is also presented. Experimental results on two longitudinal face datasets, the MORPH II and FERET, show that the proposed approach can compete the existing methods to recognize face images across aging variations. [ABSTRACT FROM AUTHOR]

This special issue of Algorithms is devoted to the design and analysis of algorithms for solving combinatorial problems of a theoretical or practical nature involving graphs, with a focus on computational complexity. [ABSTRACT FROM AUTHOR]