共查询到20条相似文献,搜索用时 0 毫秒
1.
Aubrey Blecher Charlotte Brennan Arnold Knopfmacher Toufik Mansour 《Discrete Mathematics》2017,340(10):2456-2465
We define to be a (totally ordered) alphabet on letters. A word
of length on the alphabet is an element of . A word can be represented by a bargraph (i.e., by a column-convex polyomino whose lower edges lie on the -axis) in which the height of the th column equals the size of the th part of the word. Thus these bargraphs have heights which are less than or equal to . We consider the perimeter, which is the number of edges on the boundary of the bargraph. By way of Cramer’s method and the kernel method, we obtain the generating function that counts the perimeter of words. Using these generating functions we find the average perimeter of words of length over the alphabet . We also show how the mean and variance can be obtained using a direct counting method. 相似文献
2.
《Journal of Functional Analysis》2023,284(1):109732
We prove the existence of global minimizers to the double minimization problem where denotes the perimeter of the set E, is the p-Wasserstein distance between Borel probability measures, and is arbitrary. The result holds in all space dimensions, for all , and for all positive λ. This answers a question of Buttazzo, Carlier, and Laborde. 相似文献
3.
《Discrete Mathematics》2022,345(11):113055
Using the standard Coxeter presentation for the signed symmetric group on letters, two reduced expressions for a given signed permutation are in the same commutation class if one expression can be obtained from the other one by applying a finite sequence of commutations. The commutative classes of a given signed permutation can be seen as the vertices of a graph, called the commutation graph, where two classes are connected by an edge if there are elements in those classes that differ by a long braid relation. We define a rank function for the commutation graph for the longest signed permutation, and use this function to compute the diameter and the radius of the graph. We also prove that the commutation graph for the longest signed permutation is not planar for , and identify the classes with a single element. 相似文献
4.
The transformation method for the simulation and analysis of systems with uncertain parameters 总被引:1,自引:0,他引:1
In this paper, the transformation method is introduced as a powerful approach for both the simulation and the analysis of systems with uncertain model parameters. Based on the concept of α-cuts, the method represents a special implementation of fuzzy arithmetic that avoids the well-known effect of overestimation which usually arises when fuzzy arithmetic is reduced to interval computation. Systems with uncertain model parameters can thus be simulated without any artificial widening of the simulation results. As a by-product of the implementation scheme, the transformation method also provides a measure of influence to quantitatively analyze the uncertain system with respect to the effect of each uncertain model parameter on the overall uncertainty of the model output. By this, a special kind of sensitivity analysis can be defined on the basis of fuzzy arithmetic. Finally, to show the efficiency of the transformation method, the method is applied to the simulation and analysis of a model for the friction interface between the sliding surfaces of a bolted joint connection. 相似文献
5.
Dietmar Ratz 《Journal of Global Optimization》1999,14(4):365-393
In this paper we introduce a pruning technique based on slopes in the context of interval branch-and-bound methods for nonsmooth global optimization. We develop the theory for a slope pruning step which can be utilized as an accelerating device similar to the monotonicity test frequently used in interval methods for smooth problems. This pruning step offers the possibility to cut away a large part of the box currently investigated by the optimization algorithm. We underline the new technique's efficiency by comparing two variants of a global optimization model algorithm: one equipped with the monotonicity test and one equipped with the pruning step. For this reason, we compared the required CPU time, the number of function and derivative or slope evaluations, and the necessary storage space when solving several smooth global optimization problems with the two variants. The paper concludes on the test results for several nonsmooth examples. 相似文献
6.
7.
This paper is concerned with the bifurcation structure of positive stationary solutions for a generalized Lotka–Volterra competition model with diffusion. To establish the structure, the bifurcation theory and the interval arithmetic are employed. 相似文献
8.
In this paper, first we prove that any graph G is 2-connected if diam(G)≤g−1 for even girth g, and for odd girth g and maximum degree Δ≤2δ−1 where δ is the minimum degree. Moreover, we prove that any graph G of diameter diam(G)≤g−2 satisfies that (i) G is 5-connected for even girth g and Δ≤2δ−5, and (ii) G is super-κ for odd girth g and Δ≤3δ/2−1. 相似文献
9.
A graph is superconnected, for short super-κ, if all minimum vertex-cuts consist of the vertices adjacent with one vertex. In this paper we prove for any r-regular graph of diameter D and odd girth g that if D≤g−2, then the graph is super-κ when g≥5 and a complete graph otherwise. 相似文献
10.
The use of interval mathematics to solve non-linear problems is an attractive alternative to traditional real-number techniques. It was demonstrated in a previous paper [Stradi, B., Haven, E., 2005. Optimal investment strategy via interval arithmetic. International Journal of Theoretical and Applied Finance 8(2), 185–205] that interval arithmetic in the form of the Interval-Newton Generalized Bisection (IN/GB) method is effective in solving highly non-linear problems. In this paper we solve a rational expectations models with the help of the IN/GB method. This method is capable of (i) rapidly eliminating no solution sections of the multidimensional space and (ii) concentrate computational efforts on those areas of multidimensional space where there may be a solution. 相似文献
11.
Erika R. Frits Mihály Csaba Markót Zoltán Lelkes Zsolt Fonyó Tibor Csendes Endre Rév 《Journal of Global Optimization》2007,38(2):297-313
An interval arithmetic based branch-and-bound optimizer is applied to find the singular points and bifurcations in studying
feasibility of batch extractive distillation. This kind of study is an important step in synthesizing economic industrial
processes applied to separate liquid mixtures of azeotrope-forming chemical components. The feasibility check methodology
includes computation and analysis of phase plots of differential algebraic equation systems (DAEs). Singular points and bifurcations
play an essential role in judging feasibility. The feasible domain of parameters can be estimated by tracing the paths of
the singular points in the phase plane; bifurcations indicate the border of this domain. Since the algebraic part of the DAE
cannot be transformed to an explicit form, implicit function theorem is applied in formulating the criterion of bifurcation
points. The singular points of the maps at specified process parameters are found with interval methodology. Limiting values
of the parameters are determined by searching for points satisfying bifurcation criteria. 相似文献
12.
《Applied Mathematical Modelling》2014,38(15-16):3706-3723
This paper proposes a new design optimization framework for suspension systems considering the kinematic characteristics, such as the camber angle, caster angle, kingpin inclination angle, and toe angle in the presence of uncertainties. The coordinates of rear inner hardpoints of upper control arm and lower control arm of double wishbone suspension are considered as the design variables, as well as the uncertain parameters. In this way, the actual values of the design variables will vary surrounding their nominal values. The variations result in uncertainties that are described as interval variables with lower and upper bounds. The kinematic model of the suspension is developed in software ADAMS. A high-order response surface model using the zeros of Chebyshev polynomials as sampling points is established, termed as Chebyshev metamodel, to approximate the kinematic model. The Chebyshev meta-model is expected to provide higher approximation accuracy. Interval uncertain optimization problems usually involve a nested computationally expensive double-loop optimization process, in which the inner loop optimization is to calculate the bounds of the interval design functions, while the outer loop is to search the optimum for the deterministic optimization problem. To reduce the computational cost, the interval arithmetic is introduced in the inner loop to improve computational efficiency without compromising numerical accuracy. The numerical results show the effectiveness of the proposed design method. 相似文献
13.
Experiments with a new selection criterion in a fast interval optimization algorithm 总被引:3,自引:0,他引:3
Usually, interval global optimization algorithms use local search methods to obtain a good upper (lower) bound of the solution. These local methods are based on point evaluations. This paper investigates a new local search method based on interval analysis information and on a new selection criterion to direct the search. When this new method is used alone, the guarantee to obtain a global solution is lost. To maintain this guarantee, the new local search method can be incorporated to a standard interval GO algorithm, not only to find a good upper bound of the solution, but also to simultaneously carry out part of the work of the interval B&B algorithm. Moreover, the new method permits improvement of the guaranteed upper bound of the solution with the memory requirements established by the user. Thus, the user can avoid the possible memory problems arising in interval GO algorithms, mainly when derivative information is not used. The chance of reaching the global solution with this algorithm may depend on the established memory limitations. The algorithm has been evaluated numerically using a wide set of test functions which includes easy and hard problems. The numerical results show that it is possible to obtain accurate solutions for all the easy functions and also for the investigated hard problems. 相似文献
14.
Consider a convex polygon V
n
with n sides, perimeter P
n
, diameter D
n
, area A
n
, sum of distances between vertices S
n
and width W
n
. Minimizing or maximizing any of these quantities while fixing another defines 10 pairs of extremal polygon problems (one
of which usually has a trivial solution or no solution at all). We survey research on these problems, which uses geometrical
reasoning increasingly complemented by global optimization methods. Numerous open problems are mentioned, as well as series
of test problems for global optimization and non-linear programming codes. 相似文献
15.
A new pruning method for interval branch and bound algorithms is presented. In reliable global optimization methods there
are several approaches to make the algorithms faster. In minimization problems, interval B&B methods use a good upper bound
of the function at the global minimum and good lower bounds of the function at the subproblems to discard most of them, but
they need efficient pruning methods to discard regions of the subproblems that do not contain global minimizer points. The
new pruning method presented here is based on the application of derivative information from the Baumann point. Numerical
results were obtained by incorporating this new technique into a basic Interval B&B Algorithm in order to evaluate the achieved
improvements.
This work has been supported by the Ministry of Education and Science of Spain through grants TIC 2002-00228, TIN2005-00447,
and research project SEJ2005-06273 and by the Integral Action between Spain and Hungary by grant HH2004-0014.
Boglárka Tóth: On leave from the Research Group on Artificial Intelligence of the Hungarian Academy of Sciences and the University
of Szeged, H-6720 Szeged, Aradi vértanúk tere 1., Hungary. 相似文献
16.
We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k2, in which the route degree is
, the total number of routes is O(k2n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is
, the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ1 for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ1)/{f})2 for any fault f, and a routing ρ2 (using ρ1) for every n-node biconnected graph, in which the route degree is
, the total number of routes is
and D(R(G,ρ2)/{f})2 for any fault f. 相似文献
17.
Normally inventory models of deteriorating items, such as food products, vegetables, etc. involve imprecise parameters, like imprecise inventory costs, fuzzy storage area, fuzzy budget allocation, etc. In this paper, we aim to provide two defuzzification techniques for two fuzzy inventory models using (i) extension principle and duality theory of non-linear programming and (ii) interval arithmetic. On the basis of Zadeh’s extension principle, two non-linear programs parameterized by the possibility level α are formulated to calculate the lower and upper bounds of the minimum average cost at α-level, through which the membership function of the objective function is constructed. In interval arithmetic technique the interval objective function has been transformed into an equivalent deterministic multi-objective problem defined by the left and right limits of the interval. This formulation corresponds to the possibility level, α = 0.5. Finally, the multi-objective problem is solved by a multi-objective genetic algorithm (MOGA). The model has been illustrated through a numerical example and solved for different values of possibility level, α through extension principle and for α = 0.5 via MOGA. As a particular case, the results have been obtained for the inventory model without deterioration. Results from two methods for α = 0.5 are compared. 相似文献
18.
We introduce an interval arithmetic domain decomposition method for linear systems with interval coefficients resulting from the application of difference methods for a class of elliptic boundary value problems on domains with irregular geometry. The efficient treatment of such systems is crucial for the efficiency of globally convergent Newton-like interval methods for the corresponding nonlinear problems. 相似文献
19.
Let D be the diameter of a graph G and let λ1 be the largest eigenvalue of its (0, 1)-adjacency matrix. We give a proof of the fact that there are exactly 69 non-trivial connected graphs with (D + 1)λ1 ? 9. These 69 graphs all have up to 10 vertices and were recently found to be suitable models for small multiprocessor interconnection networks. We also examine the suitability of integral graphs to model multiprocessor interconnection networks, especially with respect to the load balancing problem. In addition, we classify integral graphs with small values of (D + 1)λ1 in connection with the load balancing problem for multiprocessor systems. 相似文献
20.
We consider here a multicommodity flow network optimization problem with non-convex but piecewise convex arc cost functions. We derive complete optimality conditions for local minima based on negative-cost cycles associated with each commodity. These conditions do not extend to the convex non-smooth case. 相似文献