Mixed coordination mechanisms for scheduling games on hierarchical machines

In this paper, we study scheduling games under mixed coordination mechanisms on hierarchical machines. The two scheduling policies involved are ‐ and ‐, where ‐ (resp., ‐) policy sequences jobs in nondecreasing order of their hierarchies, and jobs of the same hierarchy in nonincreasing (resp., nondecreasing) order of their processing times. We first show the existence of a Nash equilibrium. Then we present the price of anarchy and the price of stability for the games with social costs of minimizing the makespan and maximizing the minimum machine load. All the bounds given in this paper are tight.     

Constrained shortest path tour problem: models,valid inequalities,and Lagrangian heuristics

The constrained shortest path tour problem (CSPTP) is an NP‐hard combinatorial optimization problem defined on a connected directed graph , where V is the set of nodes and A is the set of nonnegative weighted arcs. Given two distinct nodes , an integer value , and node disjoint subsets , , the CSPTP aims at finding the shortest trail from s to t while visiting at least one node in every subset , in this order. In this paper, we perform a comparative analysis between two integer programming (IP) models for the problem. We also propose valid inequalities and a Lagrangian‐based heuristic framework. Branch‐and‐bound algorithms from the literature, as well as a metaheuristic approach, are used for comparison. Extensive computational experiments carried out on benchmark data sets show the effective use of valid inequalities and the quality of bounds obtained by the Lagrangian framework. Because benchmark instances do not require a great computational effort of IP models in the sense that their optimality is reached at the root node of the CPLEX branch‐and‐cut search tree, we introduce new challenging CSPTP instances for which our solution approaches outperform existing ones for the problem.     

Crowdfunding mechanism comparison when product quality is uncertain

Many entrepreneurs have recently employed crowdfunding to raise money. Although there are several crowdfunding mechanisms, there is no clear dominant strategy for the type of mechanisms that should be adopted by the entrepreneur. This paper compares two commonly used mechanisms of crowdfunding by building a two‐person and two‐period model where the entrepreneur first makes the decision then two consumers follow. The all‐or‐nothing () mechanism allows entrepreneurs to set a funding target and keep nothing unless the goal is achieved. In contrast, entrepreneurs under the keep‐it‐all () mechanism must also set a target and keep any funds regardless of whether the goal has been achieved. To compare these two mechanisms, we assume that customers are not sure about the quality of the product, which is very common in reward‐based crowdfunding. Using a unified model, our results show that large or poorly scalable projects are more likely to choose the mechanism.     

The generalized discrete ‐centroid problem

The ‐centroid problem or leader–follower problem is generalized considering different customer choice rules where a customer may use facilities belonging to different firms, if the difference in travel distance (or time) is small enough. Assuming essential goods, some particular customer choice rules are analyzed. Linear programming formulations for the generalized ‐medianoid and ‐centroid problems are presented and an exact solution approach is applied. Some computational examples are included.     

Direct synthesis of reduced order H controllers for a class of multivariable plants

Given an nth order, -control input, p-measured output generalized plant, this article proposes a simple, direct approach to design an output feedback H controller with order satisfying for , or for . For this purpose, the output feedback H control problem is transformed into an H state feedback problem for an augmented generalized system. A class of plants for which this transformation always exists and the ensuing controller has order as above, is identified. As a result, for such plants, the reduced order H controller gains are found just by solving a simple linear matrix inequality problem used in state feedback based H control. The efficacy of the proposed approach is studied on some benchmark examples.     

TDBF: Two-dimensional belief function

How to efficiently handle uncertain information is still an open issue. In this paper, a new method to deal with uncertain information, named as two-dimensional belief function (TDBF), is presented. A TDBF has two components, T = (), both and are classical belief functions, while is a measure of reliable of . The definition of TDBF and the discounting algorithm are proposed. Compared with the classical discounting model, the proposed TDBF is more flexible and reasonable. Numerical examples are used to show the efficiency and application of the proposed method.     

A new -gain analysis framework for discrete-time switched systems based on predictive Lyapunov function

The work proposes the pre--gain analysis framework based on the newly raised nonweighted pre--gain performance index and predictive Lyapunov function, which is devoted to nonweighted -gain analysis and relevant control of discrete-time switched systems under mode-dependent average dwell time. This also provides new ideas for other disturbance-related studies. To begin with, the predictive Lyapunov function is established for switched nonlinear systems in the sense of better reflecting future system dynamics and future external disturbances. Hence, it is achievable to develop less conservative stability and nonweighted pre--gain criteria for switched linear systems. Further, a new disturbance-output expression is devised to match with the nonweighted pre--gain, whose function is to estimate and optimize the traditional nonweighted -gain of the underlying system through discussions. Then, a solvable condition is formulated to seek the piecewise time-dependent gains of switching controller in a convex structure, ensuring the global uniform exponential stability with nonweighted pre--gain and thereby attaining much smaller non-weighted -gain. Finally, the simulation comprised of a circuit system and a numerical example manifests the impressive potential of the obtained results for the purpose of preferable disturbance attenuation performances.     

Correlation and correlation coefficient of generalized orthopair fuzzy sets

Generalized orthopair fuzzy sets are extensions of ordinary fuzzy sets by relaxing restrictions on the degrees of support for and support against. Correlation analysis is to measure the statistical relationships between two samples or variables. In this paper, we propose a function measuring the interrelation of two -rung orthopair fuzzy sets, whose range is the unit interval . First, the correlation and correlation coefficient of -rung orthopair membership grades are presented, and their basic properties are investigated. Second, these concepts are extended to -rung orthopair fuzzy sets on discrete universes. Then, we discuss their applications in cluster analysis under generalized orthopair fuzzy environments. And, a real-world problem involving the evaluation of companies is used to illustrate the detailed processes of the clustering algorithm. Finally, we introduce the correlation and correlation coefficient of -rung orthopair fuzzy sets on both bounded and unbounded continuous universes and provide some numerical examples to substantiate such arguments.     

A nonmonotone accelerated Levenberg–Marquardt method for the -eigenvalues of symmetric tensors

The eigenvalues of tensors become more and more important in the numerical multilinear algebra. In this paper, based on the nonmonotone technique, an accelerated Levenberg–Marquardt (LM) algorithm is presented for computing the -eigenvalues of symmetric tensors, in which an LM step and an accelerated LM step are computed at each iteration. We establish the global convergence of the proposed algorithm using properties of symmetric tensors and norms. Under the local error-bound condition, the cubic convergence of the nonmonotone accelerated LM algorithm is derived. Numerical results show that this method is efficient.     

Two dependency constrained spanning tree problems

We introduce two spanning tree problems with dependency constraints, where an edge can be chosen only if at least one or all edges in its dependency set are also chosen, respectively. The dependencies on the input graph G are described by a digraph D whose vertices are the edges of G, and the in‐neighbors of a vertex are its dependency set. We show that both problems are NP‐hard even if G is an outerplanar chordal graph with diameter 2 or maximum degree 3, and D is a disjoint union of arborescences of height 2. We also prove that the problems are inapproximable to a factor, unless , and that they are W[2]‐hard. As an attempt to narrow the hardness gap, we present two polynomial cases. We test integer linear programming formulations based on directed cut (DCUT) and Miller–Tucker–Zemlin (MTZ) constraints. Computational experiments are reported.     

The provably good parallel seeding algorithms for the k-means problem with penalties

As a classic NP-hard problem in machine learning and computational geometry, the k-means problem aims to partition the given points into k sets to minimize the within-cluster sum of squares. The k-means problem with penalties (k-MPWP), as a generalizing problem of the k-means problem, allows a point that can be either clustered or penalized with some positive cost. In this paper, we mainly apply the parallel seeding algorithm to the k-MPWP, and show sufficient analysis to bound the expected solution quality in the case where both the number of iterations and the number of points sampled in each iteration can be given arbitrarily. The approximate guarantee can be obtained as , where is a polynomial function involving the maximal ratio M between the penalties. On one hand, this result can be viewed as a further improvement on the parallel algorithm for k-MPWP given by Li et al., where the number of iterations depends on other factors. On the other hand, our result also generalizes the one solving the k-means problem presented by Bachem et al., because k-MPWP is a variant of the k-means problem. Moreover, we present a numerical experiment to show the effectiveness of the parallel algorithm for k-means with penalties.     

Research on arithmetic operations over generalized orthopair fuzzy sets

The four fundamental operations of arithmetic for real (and complex) numbers are well known to everybody and quite often used in our daily life. And they have been extended to classical and generalized fuzzy environments with the demand of practical applications. In this paper, we present the arithmetic operations, including addition, subtraction, multiplication, and division operations, over -rung orthopair membership grades, where subtraction and division operations are both defined in two different ways. One is by solving the equation involving addition or multiplication operations, whereas the other is by determining the infimum or supremum of solutions of the corresponding inequality. Not all of -rung orthopairs can be performed by the former method but by the latter method, and it is proved that the former is a special case of the latter. Moreover, the elementary properties of arithmetic operations as well as mixed operations are extensively investigated. Finally, these arithmetic operations are pointwise defined on -rung orthopair fuzzy sets in which the membership degree of each element is a -rung orthopair.     

PAS: A new powerful and simple quantum computing simulator

In recent years, many researchers have been using CPU for quantum computing simulation. However, in reality, the simulation efficiency of the large-scale simulator is low on a single node. Therefore, striving to improve the simulator efficiency on a single node has become a serious challenge that many researchers need to solve. After many experiments, we found that much computational redundancy and frequent memory access are important factors that hinder the efficient operation of the CPU. This paper proposes a new powerful and simple quantum computing simulator: PAS (power and simple). Compared with existing simulators, PAS introduces four novel optimization methods: efficient hybrid vectorization, fast bitwise operation, memory access filtering, and quantum tracking. In the experiment, we tested the QFT (quantum Fourier transform) and RQC (random quantum circuits) of 21 to 30 qubits and selected the state-of-the-art simulator QuEST (quantum exact simulation toolkit) as the benchmark. After experiments, we have concluded that PAS compared with QuEST can achieve a mean speedup of (QFT), (RQC) (up to , ) on the Intel Xeon E5-2670 v3 CPU.     

Stubborn state estimation for nonlinear distributed parameter systems subject to measurement outliers

In this article, the state estimation problem is investigated for a class of distributed parameter systems (DPSs). In order to estimate the state of DPSs, we give a partition of spatial interval with a finite sequence and, on each subinterval, one sensor is placed to receive the measurements from the DPS. Due to the unexpected environment changes, the measurements will probably contain some outliers. To eliminate the effects of the possibly occurring outliers, we construct a stubborn state estimator where the innovation is constrained by a saturation function. By using Lyapunov functional, Wirtinger inequality and piecewise integration, some sufficient conditions are obtained under which the resulting estimation error system is exponentially stable and the performance requirement is satisfied. According to the obtained analysis results, the desired state estimator is designed in terms of the solution to a set of matrix inequalities. Finally, a numerical simulation example is given to verify the effectiveness of the proposed state estimation scheme.     

Graph fragmentation problem: analysis and synthesis

Vulnerability metrics play a key role in the understanding of cascading failures and target/random attacks to a network. The graph fragmentation problem (GFP) is the result of a worst‐case analysis of a random attack. We can choose a fixed number of individuals for protection, and a nonprotected target node immediately destroys all reachable nodes. The goal is to minimize the expected number of destroyed nodes in the network. In this paper, we address the GFP by several approaches: metaheuristics, approximation algorithms, polytime methods for specific instances, and exact methods for small instances. The computational complexity of the GFP is included in our analysis, where we formally prove that the corresponding decision version of the problem is ‐complete. Furthermore, a strong inapproximability result holds: there is no polynomial approximation algorithm with factor lower than 5/3, unless . This promotes the study of specific instances of the problem for tractability and/or exact methods in exponential time. As a synthesis, we propose new vulnerability/connectivity metrics and an interplay with game theory using a closely related combinatorial problem called component order connectivity.     

Stabilization of the planar vertical take-off and landing using nonlinear feedback control

This article presents a new control strategy for the well-known problem of the planar vertical take-off and landing. The total thrust is computed using a nonlinear feedback compensation so that the altitude reaches the desired altitude. The horizontal position x is then controlled by choosing the orientation angle as a smooth saturation function of x and . A proof of convergence is presented using a Lyapunov approach. The proposed control strategy is successfully tested in numerical simulations.     

Full complexity analysis of the diameter‐constrained reliability

Let be a simple graph with nodes and links, a subset of “terminals,” a vector , and a positive integer d, called “diameter.” We assume that nodes are perfect but links fail stochastically and independently, with probabilities . The “diameter‐constrained reliability” (DCR) is the probability that the terminals of the resulting subgraph remain connected by paths composed of d links, or less. This number is denoted by . The general DCR computation belongs to the class of ‐hard problems, since it subsumes the problem of computing the probability that a random graph is connected. The contributions of this paper are twofold. First, a full analysis of the computational complexity of DCR subproblems is presented in terms of the number of terminal nodes and the diameter d. Second, we extend the class of graphs that accept efficient DCR computation. In this class, we include graphs with bounded co‐rank, graphs with bounded genus, planar graphs, and, in particular, Monma graphs, which are relevant to robust network design.     

Computational and structural analysis of the contour of graphs

Let be a finite, simple, and connected graph. The closed interval of a set is the set of all vertices lying on a shortest path between any pair of vertices of S. The set S is geodetic if . The eccentricity of a vertex v is the number of edges in the greatest shortest path between v and any vertex w of G. A vertex v is a contour vertex if no neighbor of v has eccentricity greater than v. The contour of G is the set formed by the contour vertices of G. We consider two problems: the problem of determining whether the contour of a graph class is geodetic; the problem of determining if there exists a graph such that is not geodetic. We obtain a sufficient condition that is useful for both problems; we prove a realization theorem related to problem and show two infinite families such that is not geodetic. Using computational tools, we establish the minimum graphs for which is not geodetic; and show that all graphs with , and all bipartite graphs with , are such that is geodetic.     

Linguistic-induced ordered weighted averaging operator for multiple attribute group decision-making

To solve the problems of making decision with uncertain and imprecise information, Zadeh proposed the concept of Z-number as an ordered pair, the first component of which is a restriction of variable, and the second one is a measure of reliability of the first component. But the decision-makers’ confidence in decision-making was neglected. In this paper, firstly, we present a new method to evaluate and rank -numbers based on the operations of trapezoidal Type 2 fuzzy numbers and generalized trapezoidal fuzzy numbers. Then, linguistic-induced ordered weighted averaging operator and linguistic combined weighted averaging aggregation operator are developed to solve multiple attribute group decision-making problems. And we analyze the main properties of them by utilizing some operational laws of fuzzy linguistic variables. Finally, a numerical example is provided to illustrate the rationality of the proposed method.