Search

Machine vision plays an increasingly important role in industrial product quality detection. During processing, scratches, dents and other defects are inevitable on the surface of a smooth part. Although surface defects do not affect the overall performance of the product, their existence is unacceptable when a perfect product is required. The surface defect detection method based on machine vision and deep convolutional neural networks overcomes, to a certain extent, the problem of low detection efficiency, high false detection and missing detection rates in the traditional detection method. In this paper, a multistream semantic segmentation neural network is proposed to identify defects on smooth parts. Taking a seatbelt buckle as an example, the scratch and crush defects on the surface are classified. The network takes DeepLabV3+ as the framework and three types of image stream as the input of the network. In the backbone feature extraction network, the Xception structure is improved to MobilenetV2 and the convolutional block attention module (CBAM) is introduced into the decoding network, which improves the operational efficiency and accuracy. Compared with other classical networks, this network demonstrates good performance in the image dataset of the seatbelt buckle and realises fast and accurate semantic segmentation and classification of surface defects. The evaluation results of the network model have been significantly improved.

This paper provides a comprehensive convergence analysis of the PoA of both pure and mixed Nash equilibria in atomic congestion games with unsplittable demands., 57 pages

Team formation plays an essential role in the labor market. In this paper, we propose two bicriteria algorithms to construct a balance between gain and cost in a team formation problem under the streaming model, subject to a cardinality constraint. We formulate the problem as maximizing the difference of a non-negative normalized monotone submodular function and a non-negative linear function. As an extension, we also consider the case where the first function is $$\gamma $$ -weakly submodular. Combining the greedy technique with the threshold method, we present bicriteria streaming algorithms and give detailed analysis for both of these models. Our analysis is competitive with that in Ene’s work.

In this paper, we study the generalized submodular maximization problem with a non-negative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter α ∈ [ 0 , 1 ] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for α = 1 . For general value of the curvature parameter α ∈ [ 0 , 1 ] , we present an approximation algorithm with a factor of 1 + h α ( y ) + Δ ⋅ [ 3 + α − ( 2 + α ) y − ( 1 + α ) h α ( y ) ] 2 + α + ( 1 + α ) ( 1 − y ) , where y ∈ [ 0 , 1 ] is a predefined parameter for tuning the ratio. In particular, when α = 1 we obtain a ratio 0.5008 when setting y = 0.9 , coinciding with the renowned state-of-art approximate ratio; when α = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions.

In the k-means problem with penalties, we are given a data set $${\cal D} \subseteq \mathbb{R}^\ell $$ of n points where each point $$j \in {\cal D}$$ is associated with a penalty cost pj and an integer k. The goal is to choose a set $${\rm{C}}S \subseteq {{\cal R}^\ell }$$ with |CS| ≤ k and a penalized subset $${{\cal D}_p} \subseteq {\cal D}$$ to minimize the sum of the total squared distance from the points in D / Dp to CS and the total penalty cost of points in Dp, namely $$\sum\nolimits_{j \in {\cal D}\backslash {{\cal D}_p}} {d^2}(j,{\rm{C}}S) + \sum\nolimits_{j \in {{\cal D}_p}} {p_j}$$. We employ the primal-dual technique to give a pseudo-polynomial time algorithm with an approximation ratio of (6.357+ε) for the k-means problem with penalties, improving the previous best approximation ratio 19.849+∊ for this problem given by Feng et al. in Proceedings of FAW (2019).

In this paper, we introduce the selfish bin packing problem under a new version of cost sharing mechanism based on harmonic mean. The items (as agents) are selfish and intelligent to minimize the cost they have to pay, by selecting a proper bin to fit in. The tricky part is that the one with bigger size pays less and vice versa. We present the motivations and prove the existence of pure Nash Equilibrium under this new defined cost sharing mechanism. Then we study the Price of Anarchy, which is the ratio between the objective value of worst Nash Equilibrium and that of the optimum in the case with central decision maker. We prove the upper bound to be approximately 1.722 and show a 5/3 lower bound for this problem. We then include punishment into the model and prove that in this new model, the Price of Anarchy could be decreased to 3/2.

Relevance and diversity are two desirable properties in data retrieval applications, an important field in data science and machine learning. In this paper, we consider three maximization problems to balance these two factors. The objective function in each problem is the sum of a monotone submodular function f and a supermodular function g, where f and g capture the relevance and diversity of any feasible solution, respectively. In the first problem, we consider a special supermodular diversity function g of a sum-sum format satisfying the relaxed triangle inequality, for which we propose a greedy-type approximation algorithm with an $$\left( 1-1/e,1/(2\alpha )\right) $$ -bifactor approximation ratio, improving the previous $$\left( 1/(2\alpha ),1/(2\alpha )\right) $$ -bifactor approximation ratio. In the second problem, we consider an arbitrary supermodular diversity function g, for which we propose a distorted greedy method to give a $$\min \left\{ 1-k_{f}e^{-1},1-k^{g}e^{-(1-k^{g})}\right\} $$ -approximation algorithm, improving the previous $$k_f^{-1}\left( 1-e^{-k_f(1-k^{g})}\right) $$ -approximation ratio, where $$k_f$$ and $$k^g$$ are the curvatures of the submodular function f and the supermodular funciton g, respectively. In the third problem, we generalize the uniform matroid constraint to the p matroid constraints, for which we present a local search algorithm to improve the previous $$\frac{1-k^g}{(1-k^g)k^f+p}$$ -approximation ratio to $$\min \left\{ \frac{p+1-k_f}{p(p+1)},\left( \frac{1-k^g}{p}+\frac{k^g(1-k^g)^2}{p+(1-k^g)^2}\right) \right\} $$ .

In this paper, we consider the Bregman k-means problem (BKM) which is a variant of the classical k-means problem. For an n-point set $${\mathcal {S}}$$ and $$k \le n$$ with respect to $$\mu $$ -similar Bregman divergence, the BKM problem aims first to find a center subset $$C \subseteq {\mathcal {S}}$$ with $$ \mid C \mid = k$$ and then separate $${\mathcal {S}}$$ into k clusters according to C, such that the sum of $$\mu $$ -similar Bregman divergence from each point in $${\mathcal {S}}$$ to its nearest center is minimized. We propose a $$\mu $$ -similar BregMeans++ algorithm by employing the local search scheme, and prove that the algorithm deserves a constant approximation guarantee. Moreover, we extend our algorithm to solve a variant of BKM called noisy $$\mu $$ -similar Bregman k-means++ (noisy $$\mu $$ -BKM++) which is BKM in the noisy scenario. For the same instance and purpose as BKM, we consider the case of sampling a point with an imprecise probability by a factor between $$1-\varepsilon _1$$ and $$1+ \varepsilon _2$$ for $$\varepsilon _1 \in [0,1)$$ and $$\varepsilon _2 \ge 0$$ , and obtain an approximation ratio of $$O(\log ^2 k)$$ in expectation.

It is well-known that second-order optimizer can accelerate the training of deep neural networks, however, the huge computation cost of second-order optimization makes it impractical to apply in real practice. In order to reduce the cost, many methods have been proposed to approximate a second-order matrix. Inspired by KFAC, we propose a novel Trace-based Hardware-driven layer-ORiented Natural Gradient Descent Computation method, called THOR, to make the second-order optimization applicable in the real application models. Specifically, we gradually increase the update interval and use the matrix trace to determine which blocks of Fisher Information Matrix (FIM) need to be updated. Moreover, by resorting the power of hardware, we have designed a Hardware-driven approximation method for computing FIM to achieve better performance. To demonstrate the effectiveness of THOR, we have conducted extensive experiments. The results show that training ResNet-50 on ImageNet with THOR only takes 66.7 minutes to achieve a top-1 accuracy of 75.9 % under an 8 Ascend 910 environment with MindSpore, a new deep learning computing framework. Moreover, with more computational resources, THOR can only takes 2.7 minutes to 75.9 % with 256 Ascend 910.

Second-order optimization methods have the ability to accelerate convergence by modifying the gradient through the curvature matrix. There have been many attempts to use second-order optimization methods for training deep neural networks. In this work, inspired by diagonal approximations and factored approximations such as Kronecker-factored Approximate Curvature (KFAC), we propose a new approximation to the Fisher information matrix (FIM) called Trace-restricted Kronecker-factored Approximate Curvature (TKFAC), which can hold the certain trace relationship between the exact and the approximate FIM. In TKFAC, we decompose each block of the approximate FIM as a Kronecker product of two smaller matrices and scaled by a coefficient related to trace. We theoretically analyze TKFAC's approximation error and give an upper bound of it. We also propose a new damping technique for TKFAC on convolutional neural networks to maintain the superiority of second-order optimization methods during training. Experiments show that our method has better performance compared with several state-of-the-art algorithms on some deep network architectures.

The spherical k-means problem (SKMP) is an important variant of the k-means clustering problem (KMP). In this paper, we consider the SKMP, which aims to divide the n points in a given data point set $${\mathcal {S}}$$ into k clusters so as to minimize the total sum of the cosine dissimilarity measure from each data point to their respective closest cluster center. Our main contribution is to design an expected constant approximation algorithm for the SKMP by integrating the seeding algorithm for the KMP and the local search technique. By utilizing the structure of the clusters, we further obtain an improved LocalSearch++ algorithm involving $$\varepsilon k$$ local search steps.

In the paper, we consider the problem of maximizing the multilinear extension of a nonsubmodular set function subject to a k-cardinality constraint with adaptive rounds of evaluation queries. We devise an algorithm which achieves a ratio of ( 1 − e − γ 2 − ϵ ) and requires O ( log ⁡ n / ϵ 2 ) adaptive rounds and O ( n log ⁡ n / ϵ 2 ) queries, where γ is the continuous generic submodularity ratio that compares favorably in flexibility to the traditional submodularity ratio proposed by Das and Kempe. The key idea of our algorithm is originated from the parallel-greedy algorithm proposed by Chekuri et al., but incorporating with two major changes to retain the performance guarantee: First, identify all good coordinates with the continuous generic submodularity ratio and gradient values approximately as large as the best coordinate, and increase along all these coordinates uniformly; Second, increase x along these coordinates by a dynamical increment whose value depends on γ. The key difficulty of our algorithm is that when the function is nonsubmodular, the set of the best coordinate does not decrease during iterations; while provided submodularity, the decreasing can be ensured by the parallel-greedy algorithm. Our algorithms slightly compromise performance guarantee for the sake of extending to constrained nonsubmodular maximization with parallelism, provided that the state-of-art algorithm for the corresponding submodular version attains an approximation ratio of ( 1 − 1 / e − ϵ ) and requires O ( log ⁡ n / ϵ 2 ) adaptive rounds.

The price of anarchy (PoA) is a standard measure for the inefficiency of selfish routing in the static Wardrop traffic model. Empirical studies and a recent analysis reveal a surprising property that the PoA tends to one when the total demand T gets large. These results are extended by a new framework for the limit analysis of the PoA in arbitrary nonatomic congestion games that apply to arbitrary growth patterns of T and all regularly varying cost functions. For routing games with Bureau of Public Road (BPR) cost functions, the convergence follows a power law determined by the degree of the BPR functions, and a related conjecture need not hold. These findings are confirmed by an empirical analysis of traffic in Beijing.

Submodular maximization is well studied in the fields of data mining and machine learning. We study the submodular maximization subject to a cardinality constraint k for large scale scenarios applications under two combined settings. One is that all elements arrive in a streaming fashion, and the other is that some elements may be invalid at last. For this problem, which is called streaming robust submodular maximization (SRSM) problem, we explore an approximation algorithm, returning a subset S from the ground set V with a limit size, such that it represents V and is robust to a broken set E well. Our algorithm only makes one pass over data, and achieves a constant-factor 0.1224 approximation guarantee, independent of the cardinality constraint parameter k . Based on the algorithm for SRSM problem, we continue to discuss this problem over sliding windows, in which we are asked to obtain a proper set that only considers the last W elements, and derive an algorithm with a constant ( 0 . 0612 − ϵ ) -approximation guarantee. At last we also propose numerical experiments on some applications to well demonstrate our algorithm for SRSM problem over sliding windows.

In this paper, we study the k-level facility location problem with outliers (k-LFLPWO), which is an extension of the well-known k-level facility location problem (k-LFLP). In the k-LFLPWO, we are given k facility location sets, a client location set of cardinality n and a non-negative integer $$q

Most existing facility location models assume that the facility cost is either a fixed setup cost or made up of a fixed setup and a problem-specific concave or submodular cost term. This structural property plays a critical role in developing fast branch-and-price, Lagrangian relaxation, constant ratio approximation, and conic integer programming reformulation approaches for these NP-hard problems. Many practical considerations and complicating factors, however, can make the facility cost no longer concave or submodular. By removing this restrictive assumption, we study a new location model that considers general nonlinear costs to operate facilities in the facility location framework. The general model does not even admit any approximation algorithms unless P = NP because it takes the unsplittable hard-capacitated metric facility location problem as a special case. We first reformulate this general model as a set-partitioning model and then propose a branch-and-price approach. Although the corresponding pricing problem is NP-hard, we effectively analyze its structural properties and design an algorithm to solve it efficiently. The numerical results obtained from two implementation examples of the general model demonstrate the effectiveness of the solution approach, reveal the managerial implications, and validate the importance to study the general framework.

In the spherical k-means problem (SKMP), which is a well-studied clustering problem in text mining, we are given an n-point set D in d-dimensional unit sphere S d , and an integer k ≤ n . The goal is to find a center subset S ⊂ S d with | S | ≤ k that minimizes the sum of cosine dissimilarity measure for each point in D to the nearest center. We prove that any γ-approximation algorithm for the k-means problem (KMP) can be adapted to the SKMP with 2γ-approximation ratio. It follows that there is a local search ( 18 + ϵ ) -approximation algorithm for the SKMP, by leveraging the classical local search ( 9 + ϵ ) -approximation algorithm for the KMP. Therefore, an interesting problem arises, that is whether there exists an approximation algorithm using local search scheme directly for the SKMP. In this paper, we present a local search approximation algorithm for the SKMP and prove its performance guarantee is ( 2 ( 4 + 7 ) + ϵ ) . We also conduct numerical computation to show the efficiency of the local search approximation algorithm by single-swap operation in the end.

In this work, we investigate online bicriteria algorithms that consider both coverage and cost in the team formation problem, which selects a set of experts with the objective of maximizing the difference of two set functions f − l , where function f is non-negative normalized monotone approximately submodular, and function l is non-negative linear. By exploiting the problem's combinatorial structure, we present three bicriteria algorithms along with their corresponding competitive analysis. The first two algorithms handle the cases where function f is γ-weakly submodular, and strictly γ-weakly submodular, respectively. The last algorithm is more general by integrating the first two with extra parameters introduced.

In this paper, we investigate the two-stage submodular maximization problem, where there is a collection F = { f 1 , . . . , f m } of m submodular functions which are defined on the same element ground set Ω. The goal is to select a subset S ⊆ Ω of size at most l such that 1 m ∑ f ∈ F max T ⊆ S , T ∈ I ⁡ f ( T ) is maximized, where I denotes a specifically-defined independence system. We consider the two-stage submodular maximization with a P-matroid constraint and present a ( 1 / ( P + 1 ) ) ( 1 − 1 / e ( P + 1 ) ) -approximation algorithm. Furthermore, we extend the algorithm to the two-stage submodular maximization with a more generalized P-exchange system constraint and show the approximation ratio can be maintained with slightly modifications of the algorithm.

In this paper, we consider the dynamic k-level facility location problem, which is a generalization of the uncapacitated k-level facility location problem when considering time factor. We present a combinatorial primal-dual approximation algorithm for the problem which finds a solution within 6 times the optimum. This approximation ratio under a dynamic setting coincides with that of the simple dual ascent 6-approximation algorithm for the (static) multilevel facility location problem (Bumb, 2001) with a weak triangle inequality property.

We propose and study the MpUFLP (universal facility location problem in the p-th power of metric space) in this paper, where the universal facility location problem (UFLP) extends several classical facility location problems like the uncapacitated facility location, hard-capacitated facility location, soft-capacitated facility location, incremental-cost facility location, concave-cost facility location, etc. In UFLP, a set of facilities, a set of clients, as well as the distances between them are given. Each facility has its specific cost function w.r.t. the amount of clients assigned to that facility. The goal is to assign the clients to facilities such that the sum of facility cost and service cost is minimized. In traditional facility location problems, the unit service cost is proportional to the distance between the client and its assigned facility and thus metric. However, in our work, this assumption is removed and a generalized version of universal facility location problem is proposed, which is the so-called MnUFLP. When p = 2 , it is also known as l 2 2 measure considered by Jain and Vazirani [J. ACM'01] and Fernandes et al. [Math. Program.'15]. Particularly in this case, we extend their work to include the aforementioned variants of facility location and a local search based ( 11.18 + e ) -approximation algorithm is proposed. Furthermore, the reanalysis of the proposed algorithm gives a p-related performance guarantee for general p.

In this paper, we consider the $$\tau $$ -relaxed soft capacitated facility location problem ( $$\tau $$ -relaxed SCFLP), which extends several well-known facility location problems like the squared metric soft capacitated facility location problem (SMSCFLP), soft capacitated facility location problem (SCFLP), squared metric facility location problem and uncapacitated facility location problem. In the $$\tau $$ -relaxed SCFLP, we are given a facility set $$\mathcal {F}$$ , a client set and a parameter $$\tau \ge 1$$ . Every facility $$i \in \mathcal {F}$$ has a capacity $$u_i$$ and an opening cost $$f_i$$ , and can be opened multiple times. If facility i is opened l times, this facility can be connected by at most $$l u_i$$ clients and incurs an opening cost of $$l f_i$$ . Every facility-client pair has a connection cost. Under the assumption that the connection costs are non-negative, symmetric and satisfy the $$\tau $$ -relaxed triangle inequality, we wish to open some facilities (once or multiple times) and connect every client to an opened facility without violating the capacity constraint so as to minimize the total opening costs as well as connection costs. As our main contribution, we propose a primal-dual based $$(3 \tau + 1)$$ -approximation algorithm for the $$\tau $$ -relaxed SCFLP. Furthermore, our algorithm not only extends the applicability of the primal-dual technique but also improves the previous approximation guarantee for the SMSCFLP from $$11.18+ \varepsilon $$ to 10.

Submodular optimization has been well studied in combinatorial optimization. However, there are few works considering about non-submodular optimization problems which also have many applications, such as experimental design, some optimization problems in social networks, etc. In this paper, we consider the maximization of non-submodular function under a knapsack constraint, and explore the performance of the greedy algorithm, which is characterized by the submodularity ratio $$\beta $$ and curvature $$\alpha $$ . In particular, we prove that the greedy algorithm enjoys a tight approximation guarantee of $$ (1-e^{-\alpha \beta })/{\alpha }$$ for the above problem. To our knowledge, it is the first tight constant factor for this problem. We further utilize illustrative examples to demonstrate the performance of our algorithm.

Correlation clustering problem is a clustering problem which has many applications such as protein interaction networks, cross-lingual link detection, communication networks, and social computing. In this paper, we introduce two variants of correlation clustering problem: correlation clustering problem on uncertain graphs and correlation clustering problem with non-uniform hard constrained cluster sizes. Both problems overcome part of the limitations of the existing variants of correlation clustering problem and have practical applications in the real world. We provide a constant approximation algorithm and two approximation algorithms for the former and the latter problem, respectively.

Given a seller with k types of items and n single-minded buyers, i.e., each buyer is only interested in a particular bundle of items, to maximize the revenue, the seller must assign some amount of bundles to each buyer with respect to the buyer's accepted price. Each buyer b i is associated with a value function v i ( ⋅ ) such that v i ( x ) is the accepted unit bundle price b i is willing to pay for x bundles. In this paper, we assume that bundles can be sold fractionally. The single-minded item selling problem is proved to be NP-hard. Moreover, we give an O ( k ) -approximation algorithm. For the online version, i.e., buyers come one by one and the decision must be made immediately on the arrival of each buyer, an O ( k ⋅ ( log ⁡ h + log ⁡ k ) ) -competitive algorithm is given, where h is the highest unit item price among all buyers.

Purpose The aim of the study was to provide an applied and digital anatomical basis of acquiring extended deep inferior epigastric perforator (DIEP) flaps for clinical use. Methods Five formalin-soaked specimens were received red latex injection and dissected by layers. The arteriography using the modified mixture of lead oxide-gelatin was performed on 10 adult cadavers that were serially scanned by a spiral computed tomography. The DIEPs were 3 dimensionally reconstructed by Mimics. Results The medial row perforators of DIEP arteries are located in the medial 1/third of rectus abdominis muscle, and lateral row perforators in the lateral 1/third of the muscle. The perforators distribute mainly from the upper tendinous intersection of umbilicus to below umbilicus within 8.0 cm, especially 4.0 cm. There are constant diameter 0.8-mm perforators or greater accompanied with nerveswithin this region. The main perforators are shown by fast direct volume rendering (VR) reconstruction method, and 3-dimensional images of DIEPs are acquired by dynamic reconstruction (DR) method. Consecutively, the adjacent perforators can be combined freely and the position and anastomosis of extended branches can be easily observed. The extended DIEP flaps were designed by VR and DR methods. Conclusions The DIEPs can obtain large extended perforator flaps accompanied with nerves. The perforator close to the umbilicus should be selected while designing the DIEP flap. The 3-dimensional model of extended DIEP flaps can be established conveniently and intuitively by VR and DR methods of Mimics.

Hard-capacitated k-means (HCKM) is one of the fundamental problems remaining open in combinatorial optimization and engineering. In HCKM, one is required to partition a given n-point set into k disjoint clusters with known capacity so as to minimize the sum of within-cluster variances. It is known to be at least APX-hard, and most of the work on it has been done from a meta heuristic or bi-criteria approximation perspective. To the best our knowledge, no constant approximation algorithm or existence proof of such an algorithm is known. As our main contribution, we propose an FPT(k) approximation algorithm with constant performance guarantee for HCKM in this paper.

Spherical k-means clustering as a known NP-hard variant of the k-means problem has broad applications in data mining. In contrast to k-means, it aims to partition a collection of given data distributed on a spherical surface into k sets so as to minimize the within-cluster sum of cosine dissimilarity. In the paper, we introduce spherical k-means clustering with penalties and give a $$2\max \{2,M\}(1+M)(\ln k+2)$$-approximation algorithm. Moreover, we prove that when against spherical k-means clustering with penalties but on separable instances, our algorithm is with an approximation ratio $$2\max \{3,M+1\}$$ with high probability, where M is the ratio of the maximal and the minimal penalty cost of the given data set.

In this paper, we consider the uniform capacitated k-means problem (UC-k-means), an extension of the classical k-means problem (k-means) in machine learning. In the UC-k-means, we are given a set $$\mathcal {D}$$ of n points in d-dimensional space and an integer k. Every point in the d-dimensional space has an uniform capacity which is an upper bound on the number of points in $$\mathcal {D}$$ that can be connected to this point. Every two-point pair in the space has an associated connecting cost, which is equal to the square of the distance between these two points. We want to find at most k points in the space as centers and connect every point in $$\mathcal {D}$$ to some center without violating the capacity constraint, such that the total connecting costs is minimized. Based on the technique of local search, we present a bi-criteria approximation algorithm, which has a constant approximation guarantee and violates the cardinality constraint within a constant factor, for the UC-k-means.

In the network scheduling, jobs (tasks) must be scheduled on uniform machines (processors) connected by a complete graph so as to minimize the total weighted completion time. This setting can be ap...

This paper concerns computing approximate pure Nash equilibria in weighted congestion games, which has been shown to be PLS-complete. With the help of $\hatΨ$-game and approximate potential functions, we propose two algorithms based on best response dynamics, and prove that they efficiently compute $\fracρ{1-ε}$-approximate pure Nash equilibria for $ρ= d!$ and $ρ=\frac{2\cdot W\cdot(d+1)}{2\cdot W+d+1}\le {d + 1}$, respectively, when the weighted congestion game has polynomial latency functions of degree at most $d \ge 1$ and players' weights are bounded from above by a constant $W \ge 1$. This improves the recent work of Feldotto et al.[2017] and Giannakopoulos et al. [2022] that showed efficient algorithms for computing $d^{d+o(d)}$-approximate pure Nash equilibria., 31 pages

An independent set game is a cooperative game defined on graphs and dealing with profit-sharing in maximum independent set problems. A population monotonic allocation scheme is a rule specifying how to share the profit of each coalition among its participants such that every participant is better off when the coalition expands. In this paper, we provide a necessary and sufficient characterization for population monotonic allocation schemes in independent set games. Moreover, our characterization can be verified efficiently.

The maglev flight tunnel is a novel conceptual aerodynamics test facility, in which the complicated aerodynamic characteristics caused by the high-speed translation of a moving model in a long, straight, closed tunnel, and wave propagation and aero-structure single-way coupling problems can be investigated. The unsteady characteristics originating from a high-speed model in the maglev flight tunnel were investigated and evaluated with regard to aero–structure coupling. The new conservation element and solution element method was used to solve the 3-D compressible fluid surrounding a moving model in a tunnel, and the variations in the aerodynamic parameters, wave propagation characteristics, and pressure distribution in the tunnel were obtained. The results provide support for key technical problems, such as a wave-absorbing construction design of the maglev flight wind tunnel.