首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
In a recent paper Glover (J. Heuristics 9:175–227, 2003) discussed a variety of surrogate constraint-based heuristics for solving optimization problems in graphs. The key ideas put forth in the paper were illustrated by giving specializations designed for certain covering and coloring problems. In particular, a family of methods designed for the maximum cardinality independent set problem was presented. In this paper we report on the efficiency and effectiveness of these methods based on considerable computational testing carried out on test problems from the literature as well as some new test problems.  相似文献   

2.
Let 1/5 < θ ≤ 1. We prove that there exists a positive constant δ such that the number of even integers in the interval [X, X + X θ] which are not a sum of two primes is 《 X θ−δ. The proof uses the circle method, a sieve method, exponential sum estimates and zero-density estimates for L-functions. Current address: Department of Mathematics, 20014 University of Turku, Finland. Author’s address: Department of Mathematics, University of London, Royal Holloway, Egham, Surrey TW20 0EX, UK  相似文献   

3.
The rectangular assignment problem is a generalization of the linear assignment problem (LAP): one wants to assign a number of persons to a smaller number of jobs, minimizing the total corresponding costs. Applications are, e.g., in the fields of object recognition and scheduling. Further, we show how it can be used to solve variants of the LAP, such as the k-cardinality LAP and the LAP with outsourcing by transformation. We introduce a transformation to solve the machine replacement LAP.  相似文献   

4.
In this paper two new theorems are proved in association with the problem of matching three dimensional solid bodies. Rigorous mathematical criteria are given in order to test if two such bodies actually match in a certain position. Since this problem finds important application to the actual problem of reassembling fragmented objects e.g. archaeological, special care is taken to account for small gaps between matching fragments and fuzziness of the matching parameters.  相似文献   

5.
6.
In this paper, we present a new lower bounding scheme for the one-dimensional bin packing problem based on a destructive approach and we prove its effectiveness to solve hard instances. Performance comparison to other available lower bounds shows the effectiveness of our proposed lower bounds.  相似文献   

7.
In this paper, we find new proofs of modular relations for the Göllnitz-Gordon functions established earlier by S.-S. Huang and S.-L. Chen. We use Schröter’s formulas and some simple theta-function identities of Ramanujan to establish the relations. We also find some new modular relations of the same nature.  相似文献   

8.
The Orienteering Problem (OP) is an important problem in network optimization in which each city in a network is assigned a score and a maximum-score path from a designated start city to a designated end city is sought that is shorter than a pre-specified length limit. The Generalized Orienteering Problem (GOP) is a generalized version of the OP in which each city is assigned a number of scores for different attributes and the overall function to optimize is a function of these attribute scores. In this paper, the function used was a non-linear combination of attribute scores, making the problem difficult to solve. The GOP has a number of applications, largely in the field of routing. We designed a two-parameter iterative algorithm for the GOP, and computational experiments suggest that this algorithm performs as well as or better than other heuristics for the GOP in terms of solution quality while running faster. Further computational experiments suggest that our algorithm also outperforms the leading algorithm for solving the OP in terms of solution quality while maintaining a comparable solution speed.  相似文献   

9.
In this paper we prove that at least one solution of the obstacle problem for a linear elliptic operator perturbed by a nonlinearity having quadratic growth in the gradient satisfies the Lewy–Stampacchia inequality.
Résumé Nous démontrons dans cet article qu’au moins une solution du problème de l’obstacle pour un opérateur elliptique linéaire perturbé par une non linéarité à croissance quadratique par rapport au gradient vérifie l’inégalité de Lewy–Stampacchia.


Mathematics Subject Classification (2000) 35J85, 47J20  相似文献   

10.
11.
With a plane curve singularity one associates a multi-index filtration on the ring of germs of functions of two variables defined by the orders of a function on irreducible components of the curve. The Poincaré series of this filtration turns out to coincide with the Alexander polynomial of the curve germ. For a finite set of divisorial valuations on the ring corresponding to some components of the exceptional divisor of a modification of the plane, in a previous paper there was obtained a formula for the Poincaré series of the corresponding multi-index filtration similar to the one associated with plane germs. Here we show that the Poincaré series of a set of divisorial valuations on the ring of germs of functions of two variables defines “the topology of the set of the divisors” in the sense that it defines the minimal resolution of this set up to combinatorial equivalence. For the plane curve singularity case, we also give a somewhat simpler proof of the statement by Yamamoto which shows that the Alexander polynomial is equivalent to the embedded topology.  相似文献   

12.
Hyper-heuristics or “methodologies to choose heuristics” are becoming increasingly popular given their suitability to solve hard real world combinatorial optimisation problems. Their distinguishing feature is that they operate in the space of heuristics or heuristic components rather than in the solution space. In Dispatching Rule Based Genetic Algorithms (DRGA) solutions are represented as sequences of dispatching rules which are called one at a time and used to sequence a number of operations onto machines. The number of operations that each dispatching rule in the sequence handles is a parameter to which DRGA is notoriously sensitive. This paper proposes a new hybrid DRGA which searches simultaneously for the best sequence of dispatching rules and the number of operations to be handled by each dispatching rule. The investigated DRGA uses the selection mechanism of NSGA-II when handling multi-objective problems.  相似文献   

13.
Let (X i ) be a stationary and ergodic Markov chain with kernel Q and f an L 2 function on its state space. If Q is a normal operator and f=(I?Q)1/2 g (which is equivalent to the convergence of \(\sum_{n=1}^{\infty}\frac{\sum_{k=0}^{n-1}Q^{k}f}{n^{3/2}}\) in L 2), we have the central limit theorem [cf. (Derriennic and Lin in C.R. Acad. Sci. Paris, Sér. I 323:1053–1057, 1996; Gordin and Lif?ic in Third Vilnius conference on probability and statistics, vol. 1, pp. 147–148, 1981)]. Without assuming normality of Q, the CLT is implied by the convergence of \(\sum_{n=1}^{\infty}\frac{\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}}{n^{3/2}}\), in particular by \(\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}=o(\sqrt{n}/\log^{q}n)\), q>1 by Maxwell and Woodroofe (Ann. Probab. 28:713–724, 2000) and Wu and Woodroofe (Ann. Probab. 32:1674–1690, 2004), respectively. We show that if Q is not normal and f∈(I?Q)1/2 L 2, or if the conditions of Maxwell and Woodroofe or of Wu and Woodroofe are weakened to \(\sum_{n=1}^{\infty}c_{n}\frac{\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}}{n^{3/2}}<\infty\) for some sequence c n ↘0, or by \(\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}=O(\sqrt{n}/\log n)\), the CLT need not hold.  相似文献   

14.
The paper refines the classical Ostrowski disk theorem and suggests lower bounds for the smallest-in-modulus eigenvalue and the smallest singular value of a square matrix under certain diagonal dominance conditions. A lower bound for the smallest-in-modulus eigenvalue of a product of m ≥ 2 matrices satisfying joint diagonal dominance conditions is obtained. The particular cases of the bounds suggested that correspond to the infinity norm are discussed separately and compared with some known results. Bibliography: 8 titles.  相似文献   

15.
The singular value decomposition and spectral norm of a matrix are ubiquitous in numerical analysis. They are extensively used in proofs, but usually it is not necessary to compute them. However, there are some important applications in the realm of verified error bounds for the solution of ordinary and partial differential equations where reasonably tight error bounds for the spectral norm of a matrix are mandatory. We present various approaches to this together with some auxiliary useful estimates.  相似文献   

16.
17.
This paper examines how three eighth grade students coordinated lower and higher dimensional units (e.g., composite units and pairs) in the context of constructing a formula for evaluating sums of consecutive whole numbers while solving combinatorics problems (e.g., 1 + 2 +  + 15 = (16 × 15)/2). The data is drawn from the beginning of an 8-month teaching experiment. The findings from the study include: (1) a framework for understanding how students coordinate lower and higher dimensional units; (2) identification of key learning that occurred as students made the transition between solving two kinds of combinatorics problems; and (3) identification of the links between the way students’ coordinated lower and higher dimensional units and their evaluation of sums of consecutive whole numbers. Implications for research and teaching are considered.  相似文献   

18.
Aequationes mathematicae - Based on a result of de&nbsp;Rham, we give a family of functions solving the Matkowski and Weso?owski problem. This family consists of Hölder continuous...  相似文献   

19.
The aim of this work is to obtain optimal-order error estimates for the LQR (Linear-quadratic regulator) problem in a strongly damped 1-D wave equation. We consider a finite element discretization of the system dynamics and a control law constant in the spatial dimension, which is studied in both point and distributed case. To solve the LQR problem, we seek a feedback control which depends on the solution of an algebraic Riccati equation. Optimal error estimates are proved in the framework of the approximation theory for control of infinite-dimensional systems. Finally, numerical results are presented to illustrate that the optimal rates of convergence are achieved.  相似文献   

20.
In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号