Search

A simplified bubble model and its solver optimization method are proposed to solve the problem of poor realistic simulation and complex solutions for bubble-motion behavior in water. Firstly, the internal velocity of the bubble was avoided, and the bubble model was established by only considering the net flux of the inlet and outlet bubbles, which reduced the computational complexity. The bubble constraint was then introduced into the motion equation of water, and the mixed Euler–Lagrangian method was used to solve it. FLIP particles tracked the bubble position, velocity, and deformation, and the mesh updated the vector field. At the same time, the viscosity term was simplified. Finally, it was combined with implicit incompressible SPH particles to achieve the purpose of volume correction. The experimental results show that the method in this paper can present a simulation effect of bubbles in water with rich detail and a realistic sense, whether compared with actual pictures or with existing methods. [ABSTRACT FROM AUTHOR]

The cryptographic system is the foundation of blockchain security mechanisms. This paper constructs a blockchain security mechanism based on the Chinese national cryptographic SM2 algorithm, involving the generation of public–private key pairs and the signing of block information using key pairs. However, the original SM2 algorithm has a high computational complexity, which cannot meet the requirements of low on-chain delay in blockchain applications. To solve this problem, this paper optimizes the SM2 digital signature algorithm. The scalar multiplication operation in the digital signature algorithm has a large computational complexity, which affects the efficiency of a digital signature. To reduce its computational complexity, this paper improves the traditional window non-adjacent form (w-NAF) algorithm for the scalar multiplication operation and proposes a low computational complexity Fw-NAF algorithm based on the prime number precomputation window, which greatly reduces its computational complexity. [ABSTRACT FROM AUTHOR]

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

In order to solve the problems of large amounts of calculation and long calculation times of the A-star algorithm in three-dimensional space, based on the R5DOS model, this paper proposes a three-dimensional space UAV path planning model. The improved R5DOS intersection model is combined with the improved A-star algorithm. Together, they construct a local search process, and the R5DOS path planning model is established by reducing the number of search nodes. The path planning model is simulated through MATLAB software and the model can greatly reduce the number of nodes and computational complexity of the A-star algorithm in three-dimensional spaces, while also reducing the calculation time of the UAV. Finally, we compare the improved A-star algorithm with the original A-star algorithm and the geometric A-star algorithm. The final fitting result proves that the improved A-star algorithm has a shorter computation time and fewer node visits. Overall, the simulation results confirm the effectiveness of the improved A-star algorithm and they can be used as a reference for future research on path planning algorithms. [ABSTRACT FROM AUTHOR]

In the era of big data, a large amount of unstructured text data springs up every day. Entity linking involves relating the mentions found in the texts to the corresponding entities, which stand for objective things in the real world, in a knowledge base. This task can help computers understand semantics in the texts correctly. Although there have been numerous approaches employed in research such as this, some challenges are still unresolved. Most current approaches utilize neural models to learn important features of the entity and mention context. However, the topic coherence among the referred entities is frequently ignored, which leads to a clear preference for popular entities but poor accuracy for less popular ones. Moreover, the graph-based models face much noise information and high computational complexity. To solve the problems above, the paper puts forward an entity linking algorithm derived from the asymmetric graph convolutional network and the contextualized semantic relevance, which can make full use of the neighboring node information as well as deal with unnecessary noise in the graph. The semantic vector of the candidate entity is obtained by continuously iterating and aggregating the information from neighboring nodes. The contextualized relevance model is a symmetrical structure that is designed to realize the deep semantic measurement between the mentions and the entities. The experimental results show that the proposed algorithm can fully explore the topology information of the graph and dramatically improve the effect of entity linking compared with the baselines. [ABSTRACT FROM AUTHOR]

This paper considers the offline assignment of fixed priorities in partitioned preemptive real-time systems where tasks have precedence constraints. This problem is crucial in this type of systems, as having a good fixed priority assignment allows for an efficient use of the processing resources while meeting all the deadlines. In the literature, we can find several proposals to solve this problem, which offer varying trade-offs between the quality of their results and their computational complexities. In this paper , we propose a new approach, leveraging existing algorithms that are widely exploited in the field of Machine Learning: Gradient Descent, the Adam Optimizer, and Gradient Noise. We show how to adapt these algorithms to the problem of fixed priority assignment in conjunction with existing worst-case response time analyses. We demonstrate the performance of our proposal on synthetic task-sets with different sizes. This evaluation shows that our proposal is able to find more schedulable solutions than previous heuristics, approximating optimal but intractable algorithms such as MILP or brute-force, while requiring reasonable execution times. [ABSTRACT FROM AUTHOR]

With low hardware cost and power consumption, direction-of-arrival (DOA) estimation exploiting one-bit quantized array data has become an attractive topic. In this paper, the gridless compressed sensing (CS) with multiple measurement vectors for one-bit DOA estimation is investigated. First, the one-bit quantized signal model is established. Then an atomic norm minimization scheme is proposed based on the output of one-bit quantizer, in which the objective function is reformulated as a semidefinite programming problem combined with a one-sided l 1 -norm constraint, representing the sign inconsistency between the quantized and unquantized measurements. To efficiently solve such a problem and reduce its computational complexity, an accelerated proximal gradient-based algorithm is developed. The proposed approach outperforms the one-bit MUSIC in a small number of measurements, and avoids the grid-mismatch issue of several existing one-bit CS methods. Numerical experiments are conducted to validate the superiorities of the proposed one-bit DOA estimation approach in accuracy and running time. [ABSTRACT FROM AUTHOR]

Split cuts constitute a class of cutting planes that has been successfully employed by the majority of branch-and-cut solvers for mixed-integer linear programs. Given a basis of the linear programming (LP) relaxation and a split disjunction, the corresponding split cut can be computed with a closed-form expression. In this paper, we use the lift-and-project framework introduced by Balas and Perregaard to provide the basis, and the reduce-and-split algorithm as described by Cornuéjols and Nannicini to compute the split disjunction. We propose a cut generation algorithm that starts from a Gomory mixed-integer cut and alternates between lift-and-project and reduce-and-split in order to strengthen it. This paper has two main contributions. First, we extend the Balas and Perregaard procedure for strengthening cuts arising from split disjunctions involving one variable to split disjunctions on multiple variables. Second, we apply the reduce-and-split algorithm to nonoptimal bases of the LP relaxation. We provide detailed computational testing of the proposed methods. [ABSTRACT FROM AUTHOR]

Lane line detection is a fundamental and critical task for geographic information perception of driverless and advanced assisted driving. However, the traditional lane line detection method relies on manual adjustment of parameters, and has poor universality, a heavy workload, and poor robustness. Most deep learning-based methods make it difficult to effectively balance accuracy and efficiency. To improve the comprehensive perception ability of lane line geographic information in a natural traffic environment, a lane line detection algorithm based on a mixed-attention mechanism residual network (ResNet) and row anchor classification is proposed. A mixed-attention mechanism is added after the backbone network convolution, normalization and activation layers, respectively, so that the model can focus more on important lane line features to improve the pertinence and efficiency of feature extraction. In addition, to achieve faster detection speed and solve the problem of no vision, the method of lane line location selection and classification based on the row direction is used to detect whether there are lane lines in each candidate point according to the row anchor, reducing the high computational complexity caused by segmentation on a pixel-by-pixel basis of traditional semantic segmentation. Based on TuSimple and CurveLane datasets, multi-scene, multi-environment, multi-linear road image datasets and video sequences are integrated and self-built, and several experiments are designed and tested to verify the effectiveness of the proposed method. The test accuracy of the mixed-attention mechanism network model reached 95.96%, and the average time efficiency is nearly 180 FPS, which can achieve a high level of accuracy and real-time detection process. Therefore, the proposed method can meet the safety perception effect of lane line geographic information in natural traffic environments, and achieve an effective balance between the accuracy and efficiency of actual road application scenarios. [ABSTRACT FROM AUTHOR]

In this study, a tyre defect detection model is improved and optimized under the YOLOv5 framework, aiming at radial tyre defects with characteristics such as an elongated shape and various target sizes and defect types. The DySneakConv module is introduced to replace the first BotteneckCSP in the Backbone network. The deformation offset of the DySneakConv module is used to make the convolutional energy freely adapt to the structure to improve the recognition rate of tyre defects with elongated features; the AIFI module is introduced to replace the fourth BotteneckCSP, and the self-attention mechanism and the processing of large-scale features are used to improve the recognition rate of tyre defects with elongated features using the AIFI module. This latter module has a self-attention mechanism and the ability to handle large-scale features to solve the problems of diverse tyre defects and different sizes. Secondly, the CARAFE up-sampling operator is introduced to replace the up-sampling operator in the Neck network. The up-sampling kernel prediction module in the CARAFE operator is used to increase the receptive field and allow the feature reorganization module to capture more semantic information to overcome the information loss problem of the up-sampling operator. Finally, based on the improved YOLOv5 detection algorithm, the Channel-wise Knowledge Distillation algorithm lightens the model, reducing its computational requirements and size while ensuring detection accuracy. Experimental studies were conducted on a dataset containing four types of tyre defects. Experimental results for the training set show that the improved algorithm improves the mAP0.5 by 4.6 pp, reduces the model size by 25.6 MB, reduces the computational complexity of the model by 31.3 GFLOPs, and reduces the number of parameters by 12.7 × 106 compared to the original YOLOv5m algorithm. Experimental results for the test set show that the improved algorithm improves the mAP0.5 by 2.6 pp compared to the original YOLOv5m algorithm. This suggests that the improved algorithm is more suitable for tyre defect detection than the original YOLOv5. [ABSTRACT FROM AUTHOR]

In this paper, the berth allocation problem with stochastic vessel handling times is formulated as a bi-objective problem. To solve the resulting problem, an evolutionary algorithm-based heuristic and a simulation-based Pareto front pruning algorithm is proposed. Computational examples show that the proposed approach provides solutions superior to the ones where the expected value of the vessel handling times is used. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the optimization of process planning in which various flexibilities are considered. The objective is to minimize total weighted sum of manufacturing costs. Various flexibilities, including process flexibility, sequence flexibility, machine flexibility, tool flexibility, and tool access direction (TAD) flexibility, generally exist in process planning and consideration of these flexibilities is essential for improving production efficiency and system flexibility. However, process planning is strongly NP-hard due to the existence of various flexibilities as well as complex machining precedence constraints. To tackle this problem, an imperialist competitive algorithm (ICA) is employed to find promising solutions with reasonable computational cost. ICA is a novel socio-politically motivated metaheuristic algorithm inspired by imperialist competition. It starts with an initial population and proceeds through assimilation, position exchange, imperialistic competition, and elimination. Computational experiments on three sets of process planning problem taken from literature are carried out, and comparisons with some existing algorithms developed for process planning are presented. The results show that the algorithm performs significantly better than existing algorithms like genetic algorithm (GA), simulated annealing (SA), tabu search (TS), and particle swarm optimization (PSO). [ABSTRACT FROM AUTHOR]

Solving new problems can be made easier if one can build on experiences with other problems one has already successfully solved. The ability to exploit earlier problem-solving experiences in solving new problems seems to require several cognitive sub-abilities. Minimally, one needs to be able to retrieve relevant knowledge of earlier solved problems and their solutions (solved-exemplar retrieval), to determine whether or not a retrieved problem is sufficient analogous to the problem at hand (analogy derivation), and to infer how the solution-method used for the old problem can be used for the new problem (candidate inference projection). All three processes have successfully been modeled under the framework of Structure-Mapping Theory (SMT). It has long been known that analogy derivation under SMT is computationally intractable, meaning that all (exact) algorithms implementing this ability run impractically long. In this paper we show that the same holds for the other two sub-processes. In sharp contrast to this theoretical intractability, empirical research reveals that in certain situations humans can quickly retrieve appropriate problem-exemplars and quickly make goal-relevant candidate inference projections. How can this speed of processing be explained within the framework of SMT? We consider several possible explanations, both existing and new, and assess their explanatory validity by performing computational-level complexity analyses. Our analyses not only reveal that explanations that have been conjectured to date are incomplete but also identify a set of complete explanations that can guide future empirical research on analogical problem solving. [ABSTRACT FROM AUTHOR]

This paper proposes an improved subspace-based optimization method (SOM) by using a new construction method for the ambiguous part of the induced current. The new current construction method reduces not only the computational complexity of the current construction in every iteration of the optimization but also the computational complexity of the singular-value decomposition of the mapping from the induced current to scattered fields. Thus, the improved SOM is able to deal with the 3-D inverse-scattering problems. Numerical tests validate the algorithm. [ABSTRACT FROM AUTHOR]

Due to the limitation of energy consumption and power consumption, the embedded platform cannot meet the real-time requirements of the far-infrared image pedestrian detection algorithm. To solve this problem, this paper proposes a new real-time infrared pedestrian detection algorithm (RepVGG-YOLOv4, Rep-YOLO), which uses RepVGG to reconstruct the YOLOv4 backbone network, reduces the amount of model parameters and calculations, and improves the speed of target detection; using space spatial pyramid pooling (SPP) obtains different receptive field information to improve the accuracy of model detection; using the channel pruning compression method reduces redundant parameters, model size, and computational complexity. The experimental results show that compared with the YOLOv4 target detection algorithm, the Rep-YOLO algorithm reduces the model volume by 90%, the floating-point calculation is reduced by 93.4%, the reasoning speed is increased by 4 times, and the model detection accuracy after compression reaches 93.25%. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel algorithm for solving the classical P-median problem. The essential aim is to identify the optimal extended Lagrangian multipliers corresponding to the optimal solution of the underlying problem. For this, we first explore the structure of the data matrix in P-median problem to recast it as another equivalent global optimization problem over the space of the extended Lagrangian multipliers. Then we present a stochastic search algorithm to find the extended Lagrangian multipliers corresponding to the optimal solution of the original P-median problem. Numerical experiments illustrate that the proposed algorithm can effectively find a global optimal or very good suboptimal solution to the underlying P-median problem, especially for the computationally challenging subclass of P-median problems with a large gap between the optimal solution of the original problem and that of its Lagrangian relaxation. [ABSTRACT FROM AUTHOR]

An important aspect in the solution process of constraint satisfaction problems is to identify exclusion boxes which are boxes that do not contain feasible points. This paper presents a certificate of infeasibility for finding such boxes by solving a linearly constrained nonsmooth optimization problem. Furthermore, the constructed certificate can be used to enlarge an exclusion box by solving a nonlinearly constrained nonsmooth optimization problem. [ABSTRACT FROM AUTHOR]

To solve the problem of task scheduling in the cloud computing system, this paper proposes a scheduling algorithm for cloud computing based on the driver of dynamic essential path (DDEP). This algorithm applies a predecessor-task layer priority strategy to solve the problem of constraint relations among task nodes. The strategy assigns different priority values to every task node based on the scheduling order of task node as affected by the constraint relations among task nodes, and the task node list is generated by the different priority value. To address the scheduling order problem in which task nodes have the same priority value, the dynamic essential long path strategy is proposed. This strategy computes the dynamic essential path of the pre-scheduling task nodes based on the actual computation cost and communication cost of task node in the scheduling process. The task node that has the longest dynamic essential path is scheduled first as the completion time of task graph is indirectly influenced by the finishing time of task nodes in the longest dynamic essential path. Finally, we demonstrate the proposed algorithm via simulation experiments using Matlab tools. The experimental results indicate that the proposed algorithm can effectively reduce the task Makespan in most cases and meet a high quality performance objective. [ABSTRACT FROM AUTHOR]

This paper focuses on the multiobjective solutions of the flow shop scheduling problem with and without sequence dependent setup times. In our case, the two objectives are the minimization of makespan and total flowtime. These problems are solved with a novel multiobjective local search framework-based decomposition, called multiobjective local search based decomposition (MOLSD), which decomposes a multiobjective problem into a number of single objective optimization subproblems using aggregation method and optimizes them simultaneously. First, a problem-specific Nawaz–Enscore–Hoam heuristic is used to initialize the population to enhance the quality of the initial solution. Second, a Pareto local search embedded with a heavy perturbation operator is applied to search the promising neighbors of each nondominated solution found so far. Then, when solving each subproblem, a single insert-based local search, a multiple local search strategy, and a doubling perturbation mechanism are designed to exploit the new individual. Finally, a restarted method is used to avoid the algorithm trapping into the local optima, which has a significant effect on the performance of the MOLSD. Comprehensive experiments have been conducted by two standard multiobjective metrics: 1) hyper-volume indicator; and 2) set coverage. The experimental results show that the proposed MOLSD provides better solutions that several state of the art algorithms. [ABSTRACT FROM PUBLISHER]

One novel control policy named selective siphon control policy is proposed to solve for deadlock problems of flexible manufacturing systems (FMSs). The new policy not only solves the deadlock problem successfully but also obtains maximally permissive controllers. According to our awareness, the policy is the first one to achieve the goal of obtaining maximally permissive controllers for all S3PR (one system of simple sequential processes with resources, S3PR) models in existing literature. However, one main problem is still needed to solve in their algorithm. The problem is that the proposed policy cannot check the exact number of maximally permissive states of a deadlock net in advance. After all iterating steps, the final maximally permissive states can then be known. Additionally, all legal markings are still to be checked again and again until all critical markings vanished. In this paper, one computationally improved methodology is proposed to solve the two problems. According to the experimental results, the computational efficiency can be enhanced based on the proposed methodology in this paper. [ABSTRACT FROM AUTHOR]

This paper discusses vehicle routing problem involving split deliveries and pickups, in which the customer has pickup and delivery demands that can exceed the capacity of the vehicle, and one customer can be visited by no more than one vehicle or by one vehicle for no more than one time. The objective of the problem is to minimize total travel cost. A new heuristic algorithm, the competitive decision algorithm, is proposed to solve the problem. Computational experiments on the benchmark provided by Mitra are performed to evaluate our algorithm against the previously proposed method. The experiment shows that our algorithm provides the best solutions to a total of 110 problems whether or not the number of vehicles used is restricted to the minimum. [ABSTRACT FROM AUTHOR]

Cloud computing has become one of the major computing paradigms. Not only the number of offered cloud services has grown exponentially but also many different providers compete and propose very similar services. This situation should eventually be beneficial for the customers, but considering that these services slightly differ functionally and non-functionally -wise (e.g., performance, reliability, security), consumers may be confused and unable to make an optimal choice. The emergence of cloud service brokers addresses these issues. A broker gathers information about services from providers and about the needs and requirements of the customers, with the final goal of finding the best match. In this paper, we formalize and study a novel problem that arises in the area of cloud brokering. In its simplest form, brokering is a trivial assignment problem, but in more complex and realistic cases this does not longer hold. The novelty of the presented problem lies in considering services which can be sold in bundles. Bundling is a common business practice, in which a set of services is sold together for the lower price than the sum of services' prices that are included in it. This work introduces a multi-criteria optimization problem which could help customers to determine the best IT solutions according to several criteria. The Cloud Brokering with Bundles (CBB) models the different IT packages (or bundles) found on the market while minimizing (maximizing) different criteria. A proof of complexity is given for the single-objective case and experiments have been conducted with a special case of two criteria: the first one being the cost and the second is artificially generated. We also designed and developed a benchmark generator, which is based on real data gathered from 19 cloud providers. The problem is solved using an exact optimizer relying on a dichotomic search method. The results show that the dichotomic search can be successfully applied for small instances corresponding to typical cloud-brokering use cases and returns results in terms of seconds. For larger problem instances, solving times are not prohibitive, and solutions could be obtained for large, corporate clients in terms of minutes. [ABSTRACT FROM AUTHOR]

The m-machine no-wait flowshop scheduling problem, with the objective of minimizing total completion time subject to the constraint that makespan has to be less than or equal to a certain value, is addressed in this paper. First, an algorithm is proposed to find an upper bound on the makespan in case the upper bound is not given or unknown. Given the upper bound on makespan, a proposed algorithm ( PAL) with five versions L (1, 5, 10, 15, and 20) and a genetic algorithm ( GA) are utilized for solving the problem. Furthermore, a dominance relation is established for the case of four machines. The five versions of PAL and GA are evaluated on randomly generated problems with different number of jobs and number of machines. Computational experiments show that the errors of PA10, PA15, and PA20 are much smaller than that of GA while the CPU times of PA10, PA15, and PA20 are significantly smaller than that of GA. Therefore, the algorithms PA10, PA15, and PA20 are superior to the GA algorithm. [ABSTRACT FROM AUTHOR]

As a strongly NP-hard problem, the hybrid flow-shop problem with multiprocessor tasks (HFSPMT) has gained increasing attention due to its academic significance and application value. In this paper, an effective algorithm based on the shuffled frog leaping algorithm (SFLA) is proposed for solving the HFSPMT. First, three decoding methods are used together to decode a solution to a better schedule. Especially, the forward scheduling decoding method is employed, aiming at narrowing the idle time between consecutive operations in the processor as well as increasing the flexibility in selecting processors to schedule the following operations. Second, a bilevel crossover is designed to make each individual share the good “meme” within each memeplex and exchange the good “meme” between different memeplexes. Third, multiple local search operators are used in an effective way by employing the meta-Lamarckian learning strategy to enhance the local exploitation ability. Meanwhile, the use of crossover and local search together in the SFLA can enrich the memetic search behavior and balance the exploration and exploitation abilities. In addition, the effect of parameter setting of the algorithm is investigated based on the Taguchi method of design of experiment, and suitable values are suggested for the parameters. Extensive testing results based on two types of well-known benchmarks are provided. And the effectiveness of the proposed algorithm is demonstrated by the comparisons with some existing algorithms. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the geodetic convexity of graphs, focusing on the problem of the complexity of computing a minimum hull set of a graph in several graph classes. For any two vertices of a connected graph , the closed interval of and is the set of vertices that belong to some shortest -path. For any , let . A subset is geodesically convex or convex if . In other words, a subset is convex if, for any and for any shortest -path , . Given a subset , the convex hull of is the smallest convex set that contains . We say that is a hull set of if . The size of a minimum hull set of is the hull number of , denoted by . The Hull Number problem is to decide whether , for a given graph and an integer . Dourado et al. showed that this problem is NP-complete in general graphs. In this paper, we answer an open question of Dourado et al. (2009) [1] by showing that the Hull Number problem is NP-hard even when restricted to the class of bipartite graphs. Then, we design polynomial-time algorithms to solve the Hull Number problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in Araujo et al. (2011) [2] to the class of -graphs and to cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an -node graph without simplicial vertices is at most in general, at most if is regular or has no triangle, and at most if has girth at least . [Copyright &y& Elsevier]

This paper describes a generic branch-and-cut algorithm applicable to the solution of multiobjective optimization problems for which a lower bound can be defined as a polynomially solvable multiobjective problem. The algorithm closely follows standard branch and cut except for the definition of the lower and upper bounds and some optional speed-up mechanisms. It is applied to a routing problem called the multilabel traveling salesman problem, a variant of the traveling salesman problem in which labels are attributed to the edges. The goal is to find a Hamiltonian cycle that minimizes the tour length and the number of labels in the tour. Implementations of the generic multiobjective branch-and-cut algorithm and speed-up mechanisms are described. Computational experiments are conducted, and the method is compared to the classical ∈-constraint method. [ABSTRACT FROM AUTHOR]

Route planning in large-scale time-dependent road networks is an important practical application of the shortest-path problem that greatly benefits from speedup techniques. In this paper, we extend a two-level hierarchical approach for point-to-point shortest-path computations to the time-dependent case. This method, also known as core routing in the literature for static graphs, consists of the selection of a small subnetwork where most of the computations can be carried out, thus reducing the search space. We combine this approach with bidirectional goal-directed search to obtain an algorithm capable of finding shortest paths in a matter of milliseconds on continental-sized networks. Moreover, we tackle the dynamic scenario where the piecewise linear functions that we use to model time-dependent arc costs are not fixed but can have their coefficients updated requiring only a small computational effort. [ABSTRACT FROM AUTHOR]

Abstract: “Clarithmetic” is a generic name for formal number theories similar to Peano arithmetic, but based on computability logic instead of the more traditional classical or intuitionistic logics. Formulas of clarithmetical theories represent interactive computational problems, and their “truth” is understood as existence of an algorithmic solution. Imposing various complexity constraints on such solutions yields various versions of clarithmetic. The present paper introduces a system of clarithmetic for polynomial time computability, which is shown to be sound and complete. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a polynomial time solution and, furthermore, such a solution can be efficiently extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a polynomial time solution is represented by some theorem T of the system. The paper is written in a semitutorial style and targets readers with no prior familiarity with computability logic. [Copyright &y& Elsevier]

Abstract We study, in this paper, a taxi-sharing problem, called Dial-a-Ride problem with money as an incentive (DARP-M). This problem consists in defining a set of taxis that will be shared by different clients in order to reduce their bill by a given factor α < 1. To achieve this, each client shares the cost of the ride with other passengers. More precisely, the fragments of the ride in which the client is alone is fully paid by this client and, for each fragment in which the client shares the taxi with other passengers, the cost is equally divided between the passengers. In addition to this cost constraint, the taxi must satisfy a time window constraint for each passenger and a capacity constraint. We define three versions of the problem: max-DARP-M where the objective is to drive the maximum number of clients with an arbitrarily large number of taxis; max-1-DARP-M in which we want to drive the maximum number of clients with one taxi; and 1-DARP-M which consists in deciding whether it is possible to drive at least one client while satisfying the constraints. We study the parameterized complexity and approximability of those problems with respect to four parameters: the factor α , the capacity c a p a of the taxis, the maximum size TW of the time windows of the clients, and the value S of an optimal solution. Among other results, we prove that 1-DARP-M is NP-Complete and max-DARP-M and max-1-DARP-M cannot be approximated in polynomial time to within any variable ratio even if α , c a p a and TW are fixed and if the road network is a planar graph. We also give a polynomial algorithm for max-1-DARP-M for the case where c a p a and TW are fixed and where the network does not contain a circuit. This algorithm implies a 1 n -polynomial approximation for max-DARP-M. [ABSTRACT FROM AUTHOR]

Abstract This paper proposes an exact exponential algorithm for the single machine total tardiness problem. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property that solves the problem with worst-case complexity in time O ⁎ (3 n) and polynomial space. The proposed algorithm, called branch-and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation. Its time complexity converges to O ⁎ (2 n) keeping the space complexity polynomial. This improves upon the best-known complexity result for this problem provided by dynamic programming across the subsets with O ⁎ (2 n) worst-case time and space complexity. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the following basic problem: After having executed a sequence of actions, find a sequence of actions that brings the agent back to the state just before this execution. It emerges, for example, if an agent needs to find out which action sequences are undoable, and which ones are committed choices. A prototypical scenario is in the context of plan execution in a nondeterministic environment: Upon detecting that after executing some steps of the plan, an unintended state has been reached, backtracking to an earlier state by taking appropriate undo actions can be useful for recovery. In this paper, we consider the problem of undoing the effects of an action sequence by means of a reverse plan. Intuitively, by executing a reverse plan for an action sequence AS at the state reached after AS, the agent can always reach the state S she was at just before executing AS, possibly subject to conditions on the current state and S. Notably, this problem is different from a vanilla planning problem, since the state we have to get back to is in general unknown. We study this problem in a general logic-based action representation framework that can accommodate nondeterminism and concurrency. We formally define the notion of a reverse plan and determine the computational complexity of the existence and the recognition of such a plan. Guided by these results, we then present algorithms for constructing reverse plans. Unsurprisingly, the problem is intractable in general, and we present a knowledge compilation approach that constructs offline a reverse plan library for efficient (in some cases, linear time) online computation of action reversals. Our results for the generic framework can be adapted for expressive action languages such as or . [Copyright &y& Elsevier]

In the last two decades, a number of algorithms for the linear single-commodity min-cost flow (MCF) problem have been proposed, and several efficient codes are available that implement different variants of the algorithms. The practical significance of the algorithms has been tested by comparing the time required by their implementations for solving "from-scratch" instances of MCF, of different classes, as the size of the problem (number of nodes and arcs) increases. However, in many applications several closely related instances of MCF have to be sequentially solved, so that reoptimization techniques can be used to speed up computations, and the most attractive algorithm is the one that minimizes the total time required to solve all the instances in the sequence. In this paper we compare the performances of four different efficient implementations of algorithms for MCF under cost reoptimization in the context of decomposition algorithms for the multicommodity min-cost flow (MMCF) problem, showing that for some classes of instances the relative performances of the codes doing "from-scratch" optimization do not accurately predict the relative performances when reoptimization is used. Because the best solver depends both on the class and on the size of the instance, this work also shows the usefulness of a standard interface for MCF problem solvers that we have proposed and implemented. [ABSTRACT FROM AUTHOR]

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

Versatile Video Coding (VVC) introduces many new coding technologies, such as quadtree with nested multi-type tree (QTMT), which greatly improves the efficiency of VVC coding. However, its computational complexity is higher, which affects the application of VVC in real-time scenarios. Aiming to solve the problem of the high complexity of VVC intra coding, we propose a low-complexity partition algorithm based on edge features. Firstly, the Laplacian of Gaussian (LOG) operator was used to extract the edges in the coding frame, and the edges were divided into vertical and horizontal edges. Then, the coding unit (CU) was equally divided into four sub-blocks in the horizontal and vertical directions to calculate the feature values of the horizontal and vertical edges, respectively. Based on the feature values, we skipped unnecessary partition patterns in advance. Finally, for the CUs without edges, we decided to terminate the partition process according to the depth information of neighboring CUs. The experimental results show that compared with VTM-13.0, the proposed algorithm can save 54.08% of the encoding time on average, and the BDBR (Bjøntegaard delta bit rate) only increases by 1.61%. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the joint design of a transmit beampattern and angular waveform (AW) for colocated multiple-input multiple-output (MIMO) radars. The importance of the AW in the proposed signal processing strategy is first clarified, and then, two optimization models are established, which are aimed at either the power spectral density (PSD) design or the spectral compatibility and similarity design of the AW. There are two main differences between the proposed models and existing models. First, instead of matching a desired template or maximizing the transmit power on specific regions, the transmit beampattern in this paper is optimized to approach several key points, which guarantees the high transmit gain and the flexible adjustment of each beam gain. Second, instead of optimizing the performance of the transmit waveform, only the characteristics of the AW are examined, and they can be constrained quantitatively according to their relationship with the transmit gain. The two models can be unified into the same framework, and an efficient algorithm is proposed to solve the problem under a constant modulus constraint. The convergence of the proposed algorithm is demonstrated, and some improvements to reduce the computational complexity are proposed. Numerical simulations showed that compared to the existing methods, the proposed approach can be used to obtain a higher transmit gain, flexibly adjust each beam gain, and more accurately control the PSD, spectral compatibility, and similarity of the AW. Moreover, numerical simulations showed that, compared to the use of existing methods, the proposed algorithm has higher computational efficiency. [ABSTRACT FROM AUTHOR]

We report on the First International Competition on Computational Models of Argumentation (ICCMA'15) which took place in the first half of 2015 and focused on reasoning tasks in abstract argumentation frameworks. Performance of submitted solvers was evaluated on four computational problems wrt. four different semantics relating to the verification of the acceptance status of arguments, and computing jointly acceptable sets of arguments. In this paper, we describe the technical setup of the competition, and give an overview on the submitted solvers. Moreover, we report on the results and discuss our findings. [ABSTRACT FROM AUTHOR]

Considerable effort has been expanded in attempts to combine the power found in algorithmic languages with the power found in program libraries. However, most of these attempts to construct problem-solving systems for a particular class of users have failed to achieve their objective of providing the user with the potential benefits inherent in such systems. This paper attempts to define and place problem-solving systems in a general context, and thereby shows when the potential for failure or success is high. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the applicability of a constraint satisfaction problem solving (CSP) model, recently developed for deadline scheduling, to more commonly studied problems of schedule optimization. Our hypothesis is twofold: (1) that CSP scheduling techniques provide a basis for developing high-performance approximate solution procedures in optimization contexts, and (2) that the representational assumptions underlying CSP models allow these procedures to naturally accommodate the idiosyncratic constraints that complicate most real-world applications. We focus specifically on the objective criterion of makespan minimization, which has received the most attention within the job shop scheduling literature. We define an extended solution procedure somewhat unconventionally by reformulating the makespan problem as one of solving a series of different but related deadline scheduling problems, and embedding a simple CSP procedure as the subproblem solver. We first present the results of an empirical evaluation of our procedure performed on a range of previously studied benchmark problems. Our procedure is found to provide strong cost/performance, producing solutions competitive with those obtained using recently reported shifting bottleneck search procedures at reduced computational expense. To demonstrate generality, we also consider application of our procedure to a more complicated, multi-product hoist scheduling problem. With only minor adjustments, our procedure is found to significantly outperform previously published procedures for solving this problem across a range of input assumptions. [ABSTRACT FROM AUTHOR]

Satisfiability problems are of importance for many practical problems. They are NP-complete problems. However, some instances of the SAT problem can be solved efficiently. This paper reports on a study concerning the behaviour of a variety of algorithmic approaches to this problem tested on a set of problems collected at FAW. The results obtained give a lot of insight into the algorithms and problems, yet also show some general technical and methodological problems associated with such comparisons. [ABSTRACT FROM AUTHOR]

Since wind power is integrated into the thermal power operation system, dynamic economic emission dispatch (DEED) has become a new challenge due to its uncertain characteristics. This paper proposes an adaptive grid based multi-objective Cauchy differential evolution (AGB-MOCDE) for solving stochastic DEED with wind power uncertainty. To properly deal with wind power uncertainty, some scenarios are generated to simulate those possible situations by dividing the uncertainty domain into different intervals, the probability of each interval can be calculated using the cumulative distribution function, and a stochastic DEED model can be formulated under different scenarios. For enhancing the optimization efficiency, Cauchy mutation operation is utilized to improve differential evolution by adjusting the population diversity during the population evolution process, and an adaptive grid is constructed for retaining diversity distribution of Pareto front. With consideration of large number of generated scenarios, the reduction mechanism is carried out to decrease the scenarios number with covariance relationships, which can greatly decrease the computational complexity. Moreover, the constraint-handling technique is also utilized to deal with the system load balance while considering transmission loss among thermal units and wind farms, all the constraint limits can be satisfied under the permitted accuracy. After the proposed method is simulated on three test systems, the obtained results reveal that in comparison with other alternatives, the proposed AGB-MOCDE can optimize the DEED problem while handling all constraint limits, and the optimal scheme of stochastic DEED can decrease the conservation of interval optimization, which can provide a more valuable optimal scheme for real-world applications. [ABSTRACT FROM AUTHOR]

Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits k and the maximum degree r are taken together as a combined parameter, the problems are tractable (i.e. in FPT ), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural k + r parameterization. [ABSTRACT FROM AUTHOR]

Despite the success of stochastic variance-reduced gradient (SVRG) algorithms in solving large-scale problems, their stochastic gradient complexity often scales linearly with data size and is expensive for huge data. Accordingly, we propose a hybrid stochastic-deterministic minibatch proximal gradient (HSDMPG) algorithm for strongly convex problems with linear prediction structure, e.g., least squares and logistic/softmax regression. HSDMPG enjoys improved computational complexity that is data-size-independent for large-scale problems. It iteratively samples an evolving minibatch of individual losses to estimate the original problem, and can efficiently minimize the sampled subproblems. For strongly convex loss of $n$ n components, HSDMPG attains an $\epsilon$ ε -optimization-error within $\mathcal {O} \left(\kappa \log ^{\zeta +1}\left(\frac{1}{\epsilon }\right)\frac{1}{\epsilon }\bigwedge n\log ^{\zeta }\left(\frac{1}{\epsilon }\right)\right)$ O κ log ζ + 1 1 ε 1 ε ⋀ n log ζ 1 ε stochastic gradient evaluations, where $\kappa$ κ is condition number, $\zeta =1$ ζ = 1 for quadratic loss and $\zeta =2$ ζ = 2 for generic loss. For large-scale problems, our complexity outperforms those of SVRG-type algorithms with/without dependence on data size. Particularly, when $\epsilon =\mathcal {O}(1/\sqrt{n})$ ε = O (1 / n) which matches the intrinsic excess error of a learning model and is sufficient for generalization, our complexity for quadratic and generic losses is respectively $\mathcal {O} (n^{0.5}\log ^{2}(n))$ O (n 0. 5 log 2 (n)) and $\mathcal {O} (n^{0.5}\log ^{3}(n))$ O (n 0. 5 log 3 (n)) , which for the first time achieves optimal generalization in less than a single pass over data. Besides, we extend HSDMPG to online strongly convex problems and prove its higher efficiency over the prior algorithms. Numerical results demonstrate the computational advantages of HSDMPG. [ABSTRACT FROM AUTHOR]

In this paper, we consider a generalized longest common subsequence problem, in which a constraining sequence of length s must be included as a substring and the other constraining sequence of length t must be included as a subsequence of two main sequences and the length of the result must be maximal. For the two input sequences X and Y of lengths n and m, and the given two constraining sequences of length s and t, we present an O(nmst) time dynamic programming algorithm for solving the new generalized longest common subsequence problem. The time complexity can be reduced further to cubic time in a more detailed analysis. The correctness of the new algorithm is proved. [ABSTRACT FROM AUTHOR]

In the Possible winner problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the Possible winner problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge [10] . In this paper, we settle this open question for many common voting rules. We show that the Possible winner problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that includes the Borda voting rule does not admit a polynomial kernel with the number of candidates as the parameter. We show however that the Coalitional manipulation problem which is an important special case of the Possible winner problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the Possible winner problem is harder than the Coalitional manipulation problem since the Coalitional manipulation problem admits a polynomial kernel whereas the Possible winner problem does not admit a polynomial kernel. [ABSTRACT FROM AUTHOR]

The single machine scheduling problem with sequence-dependent setup times with the objective of minimizing the total weighted tardiness is a challenging problem due to its complexity, and has a huge number of applications in real production environments. In this paper, we propose a memetic algorithm that combines and extends several ideas from the literature, including a crossover operator that respects both the absolute and relative position of the tasks, a replacement strategy that improves the diversity of the population, and an effective but computationally expensive neighborhood structure. We propose a new decomposition of this neighborhood that can be used by a variable neighborhood descent framework, and also some speed-up methods for evaluating the neighbors. In this way we can obtain competitive running times. We conduct an experimental study to analyze the proposed algorithm and prove that it is significantly better than the state-of-the-art in standard benchmarks. [ABSTRACT FROM AUTHOR]

The Closest String problem asks to find a string s which is not too far from each string in a set of m input strings, where the distance is taken as the Hamming distance. This well-studied problem has various applications in computational biology and drug design. In this paper, we introduce a new variant of Closest String where the input strings can contain wildcards that can match any letter in the alphabet, and the goal is to find a solution string without wildcards. We call this problem the Closest String with Wildcards problem, and we analyze it in the framework of parameterized complexity. Our study determines for each natural parameterization whether this parameterization yields a fixed-parameter algorithm, or whether such an algorithm is highly unlikely to exist. [ABSTRACT FROM AUTHOR]