共查询到20条相似文献,搜索用时 31 毫秒
1.
Ann Melissa Campbell 《Annals of Operations Research》2006,144(1):99-110
We propose and formulate the vehicle routing problem with demand range (VRPDR), a new variation on the traditional vehicle
routing problem. In the VRPDR, the delivery quantity for each customer i is allowed to vary from its original size d
i
by an amount α d
i
where 0 ≤ α < 1. In adding this limited flexibility to the problem, there is potential to generate significant savings in
the total distance traveled. We address issues such as bounding the impact of a given α on total distance and provide empirical
results to illustrate
“typical” behavior. 相似文献
2.
Ivan Singer 《Numerical Functional Analysis & Optimization》2013,34(7-8):903-915
Recently Deutsch, Li and Swetits [2] have studied, in Hilbert space, a dual problem (Qm ) to the primal problem (P) of minimization of a special class of convex functions f over the intersection of m closed convex sets, where m is finite. In the first part of this paper we obtain, in a locally convex space, some results on problem (Qm ) and on its relations with the usual Lagrangian dual problem (Q) to (P) (studied in [9]), in the case when (P) has a solution. In the second part we give some applications to duality for the distance to the intersection of m closed convex sets in a normed linear space, in the case when a nearest point exists. Most of our results seem to be new even in the particular cases studied in [9] (the case m = 1), [l] (duality formulas for the distance to the intersection of m closed half-spaces in a normed linear space) and [2]. 相似文献
3.
In this paper we generalize the notion of cyclic code and construct codes as ideals in finite quotients of non-commutative
polynomial rings, so called skew polynomial rings of automorphism type. We propose a method to construct block codes of prescribed
rank and a method to construct block codes of prescribed distance. Since there is no unique factorization in skew polynomial
rings, there are much more ideals and therefore much more codes than in the commutative case. In particular we obtain a [40,
23, 10]4 code by imposing a distance and a [42,14,21]8 code by imposing a rank, which both improve by one the minimum distance of the previously best known linear codes of equal
length and dimension over those fields. There is a strong connection with linear difference operators and with linearized
polynomials (or q-polynomials) reviewed in the first section.
相似文献
4.
Alberto Del Lungo Guy Louchard Claudio Marini Franco Montagna 《Journal of Algorithms in Cognition, Informatics and Logic》2005,55(2):3645-176
We introduce a probabilistic variant of the Guessing Secrets problem proposed by Chung et al. in [Electron. J. Combin. 8 (2001) R13]. In our variation, a player tries to discover the identity of a set S of n unknown secrets drawn by a second player, from a space Ω of N secrets. The first player tries to learn as much as possible about the elements of S by asking binary questions. For each question asked, the second player randomly chooses one of the n secrets of S that he uses in supplying the answer, which in any case must be truthful. We define a simple probabilistic guessing algorithm that allows us to guess all secrets of S with probability one. We show that the expected number of questions needed to guess all secrets is 2n2log2N and the expected time complexity of the algorithm is
. We also propose a generalization of this probabilistic guessing secrets problem, and provide some similar results for this generalization. 相似文献
5.
We extend the traveling salesman problem with pickup and delivery and LIFO loading (TSPPDL) by considering two additional factors, namely the use of multiple vehicles and a limitation on the total distance that a vehicle can travel; both of these factors occur commonly in practice. We call the resultant problem the multiple pickup and delivery traveling salesman problem with LIFO loading and distance constraints (MTSPPD-LD). This paper presents a thorough preliminary investigation of the MTSPPD-LD. We propose six new neighborhood operators for the problem that can be used in search heuristics or meta-heuristics. We also devise a two-stage approach for solving the problem, where the first stage focuses on minimizing the number of vehicles required and the second stage minimizes the total travel distance. We consider two possible approaches for the first stage (simulated annealing and ejection pool) and two for the second stage (variable neighborhood search and probabilistic tabu search). Our computational results serve as benchmarks for future researchers on the problem. 相似文献
6.
A differential game with two pursuers and one evader 总被引:1,自引:0,他引:1
This paper is concerned with a coplanar pursuit-evasion problem in which a faster evaderE with constant speedw>1 must pass between two pursuersP
1,P
2 having unit speed, the payoff being the distance of closest approach to either one of the pursuers. The control variables are the directions of the velocities ofP
1,P
2, andE. The path equations are integrated, and a closed-form solution is obtained in terms of elliptic functions of the first and second kind. A closed-loop solution is given graphically in several diagrams, for different values ofw. 相似文献
7.
Ayanendranath Basu Bruce G. Lindsay 《Annals of the Institute of Statistical Mathematics》1994,46(4):683-705
A general class of minimum distance estimators for continuous models called minimum disparity estimators are introduced. The conventional technique is to minimize a distance between a kernel density estimator and the model density. A new approach is introduced here in which the model and the data are smoothed with the same kernel. This makes the methods consistent and asymptotically normal independently of the value of the smoothing parameter; convergence properties of the kernel density estimate are no longer necessary. All the minimum distance estimators considered are shown to be first order efficient provided the kernel is chosen appropriately. Different minimum disparity estimators are compared based on their characterizing residual adjustment function (RAF); this function shows that the robustness features of the estimators can be explained by the shrinkage of certain residuals towards zero. The value of the second derivative of theRAF at zero,A
2, provides the trade-off between efficiency and robustness. The above properties are demonstrated both by theorems and by simulations. 相似文献
8.
We consider the self‐adjoint operator governing the propagation of elastic waves in a perturbed isotropic half‐space (perturbation with compact support of a homogeneous isotropic half‐space) with a free boundary condition. We propose a method to obtain, numerical values included, a complete set of generalized eigenfunctions that diagonalize this operator. The first step gives an explicit representation of these functions using a perturbative method. The unbounded boundary is a new difficulty compared with the method used by Wilcox [25], who set the problem in the complement of bounded open set. The second step is based on a boundary integral equations method which allows us to compute these functions. For this, we need to determine explicitly the Green's function of (A0 – ω2), where A0 is the self‐adjoint operator describing elastic waves in a homogeneous isotropic half‐space. Copyright © 2000 John Wiley & Sons, Ltd. 相似文献
9.
We study a second-order two-grid scheme fully discrete in time and space for solving the Navier–Stokes equations. The two-grid
strategy consists in discretizing, in the first step, the fully non-linear problem, in space on a coarse grid with mesh-size
H and time step Δt and, in the second step, in discretizing the linearized problem around the velocity u
H
computed in the first step, in space on a fine grid with mesh-size h and the same time step. The two-grid method has been applied for an analysis of a first order fully-discrete in time and
space algorithm and we extend the method to the second order algorithm. This strategy is motivated by the fact that under
suitable assumptions, the contribution of u
H
to the error in the non-linear term, is measured in the L
2 norm in space and time, and thus has a higher-order than if it were measured in the H
1 norm in space. We present the following results: if h
2 = H
3 = (Δt)2, then the global error of the two-grid algorithm is of the order of h
2, the same as would have been obtained if the non-linear problem had been solved directly on the fine grid. 相似文献
10.
A well known formulation of the multiple sequence alignment (MSA) problem is the maximum weight trace (MWT), a 0–1 linear
programming problem. In this paper, we propose a new integer quadratic programming formulation of the MSA. The number of constraints
and variables in the problem are only of the order of kL
2, where, k is the number of sequences and L is the total length of the sequences, that is, L = ?i=1kli{L= \sum_{i=1}^{k}l_{i}} , where l
i
is the length of sequence i. Based on this formulation we introduce an equivalent linear constrained 0–1 quadratic programming problem. We also propose
a 0–1 linear programming formulation of the MWT problem, with polynomially many constraints. Our formulation provides the
first direct compact formulation that ensures that the critical circuit inequalities (which are exponentially many) are all
met. 相似文献
11.
Streaming Algorithms for Line Simplification 总被引:1,自引:0,他引:1
M. A. Abam M. de Berg P. Hachenberger A. Zarei 《Discrete and Computational Geometry》2010,43(3):497-515
We study the following variant of the well-known line-simplification problem: we are getting a (possibly infinite) sequence
of points p
0,p
1,p
2,… in the plane defining a polygonal path, and as we receive the points, we wish to maintain a simplification of the path
seen so far. We study this problem in a streaming setting, where we only have a limited amount of storage, so that we cannot
store all the points. We analyze the competitive ratio of our algorithms, allowing resource augmentation: we let our algorithm
maintain a simplification with 2k (internal) points and compare the error of our simplification to the error of the optimal simplification with k points. We obtain the algorithms with O(1) competitive ratio for three cases: convex paths, where the error is measured using the Hausdorff distance (or Fréchet
distance), xy-monotone paths, where the error is measured using the Hausdorff distance (or Fréchet distance), and general paths, where
the error is measured using the Fréchet distance. In the first case the algorithm needs O(k) additional storage, and in the latter two cases the algorithm needs O(k
2) additional storage. 相似文献
12.
A Parameter Selection Method for Wavelet Shrinkage Denoising 总被引:1,自引:0,他引:1
Thresholding estimators in an orthonormal wavelet basis are well established tools for Gaussian noise removal. However, the universal threshold choice, suggested by Donoho and Johnstone, sometimes leads to over-smoothed approximations.For the denoising problem this paper uses the deterministic approach proposed by Chambolle et al., which handles it as a variational problem, whose solution can be formulated in terms of wavelet shrinkage. This allows us to use wavelet shrinkage successfully for more general denoising problems and to propose a new criterion for the choice of the shrinkage parameter, which we call H-curve criterion. It is based on the plot, for different parameter values, of the B
1
1(L
1)-norm of the computed solution versus the L
2-norm of the residual, considered in logarithmic scale. Extensive numerical experimentation shows that this new choice of shrinkage parameter yields good results both for Gaussian and other kinds of noise. 相似文献
13.
We study the satisfiability of randomly generated formulas formed by M clauses of exactly K literals over N Boolean variables. For a given value of N the problem is known to be most difficult when α = M/N is close to the experimental threshold αc separating the region where almost all formulas are SAT from the region where all formulas are UNSAT. Recent results from a statistical physics analysis suggest that the difficulty is related to the existence of a clustering phenomenon of the solutions when α is close to (but smaller than) αc. We introduce a new type of message passing algorithm which allows to find efficiently a satisfying assignment of the variables in this difficult region. This algorithm is iterative and composed of two main parts. The first is a message‐passing procedure which generalizes the usual methods like Sum‐Product or Belief Propagation: It passes messages that may be thought of as surveys over clusters of the ordinary messages. The second part uses the detailed probabilistic information obtained from the surveys in order to fix variables and simplify the problem. Eventually, the simplified problem that remains is solved by a conventional heuristic. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005 相似文献
14.
J. B. G. Frenk J. Gromicho S. Zhang 《Journal of Optimization Theory and Applications》1996,89(1):65-87
This paper studies the problem of deciding whether the present iteration point of some algorithm applied to a planar singlefacility min-max location problem, with distances measured by either anl
p
-norm or a polyhedral gauge, is optimal or not. It turns out that this problem is equivalent to the decision problem of whether 0 belongs to the convex hull of either a finite number of points in the plane or a finite number of differentl
q
-circles
. Although both membership problems are theoretically solvable in polynomial time, the last problem is more difficult to solve in practice than the first one. Moreover, the second problem is solvable only in the weak sense, i.e., up to a predetermined accuracy. Unfortunately, these polynomial-time algorithms are not practical. Although this is a negative result, it is possible to construct an efficient and extremely simple linear-time algorithm to solve the first problem. Moreover, this paper describes an implementable procedure to reduce the second decision problem to the first with any desired precision. Finally, in the last section, some computational results for these algorithms are reported.The work of the second author was supported by JNICT (Portugal), under Contract BD/631/90-RM, during his stay at Erasmus University in Rotterdam.The authors would like to express their acknowledgments to Jan Brinkhuis for his suggestions and support and to Joe Mitchell for suggesting the simplifications leading to Algorithm 3.1. Also, the anonymous referees are acknowledged for their careful reading of the paper and their useful comments. 相似文献
15.
Konno Y. 《Journal of multivariate analysis》1995,52(2)
Suppose that we have (n − a) independent observations from Np(0, Σ) and that, in addition, we have a independent observations available on the last (p − c) coordinates. Assuming that both observations are independent, we consider the problem of estimating Σ under the Stein′s loss function, and show that some estimators invariant under the permutation of the last (p − c) coordinates as well as under those of the first c coordinates are better than the minimax estimators of Eaten. The estimators considered outperform the maximum likelihood estimator (MLE) under the Stein′s loss function as well. The method involved here is computation of an unbiased estimate of the risk of an invariant estimator considered in this article. In addition we discuss its application to the problem of estimating a covariance matrix in a GMANOVA model since the estimation problem of the covariance matrix with extra data can be regarded as its canonical form. 相似文献
16.
R. Scholz 《Numerical Functional Analysis & Optimization》2013,34(3):269-277
A mixed finite element method for second order elliptic problems is considered, where the solution u of the problem and grad u are approximated separately. It is known that with respect to the L 2-norm the approximation of grad u converges with the same rate as the approximation of u does if the solution is sufficiently smooth. The aim of this note is to show that except a logarithmic term the same holds true with respect to the L ∞-norm. 相似文献
17.
Consider a numerical differential problem, which aims to compute the second order derivative of a function stably from its
given noisy data. For this ill-posed problem, we introduce the Lavrent′ev regularization scheme by reformulating this differentiation
problem as an integral equation of the first kind. The advantage of this proposed scheme is that we can give the regularizing
solution by an explicit integral expression, therefore it is easy to be implemented. The a-priori and a-posterior choice strategies for the regularization parameter are considered, with convergence analysis and error estimate of the regularizing
solution for noisy data based on the integral operator decomposition. The validity of the proposed scheme is shown by several
numerical examples. 相似文献
18.
S. M. Ertel 《Mathematical Notes》1995,58(1):762-769
Forn pointsA
i
,i=1, 2, ...,n, in Euclidean space ℝ
m
, the distance matrix is defined as a matrix of the form D=(D
i
,j)
i
,j=1,...,n, where theD
i
,j are the distances between the pointsA
i
andA
j
. Two configurations of pointsA
i
,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices
of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that
the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that
distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear
equations whose matrix is a given distance matrix.
Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995. 相似文献
19.
In this paper, following the ideas of Lax, we prove a blow-up result for a class of solutions of the equation ϕtt−ϕxx−ϕ2xϕxx−ϕ3 = 0, corresponding, in certain cases, to the development of a singularity in the second derivatives of ϕ. These solutions solve locally (in time) the Cauchy problem for smooth initial data belonging to the uniformly local Sobolev spaces considered by Kato and by Majda. 相似文献
20.
Finding independent sets in a graph using continuous multivariable polynomial formulations 总被引:1,自引:0,他引:1
James Abello Sergiy Butenko Panos M. Pardalos Mauricio G.C. Resende 《Journal of Global Optimization》2001,21(2):111-137
Two continuous formulations of the maximum independent set problem on a graph G=(V,E) are considered. Both cases involve the maximization of an n-variable polynomial over the n-dimensional hypercube, where n is the number of nodes in G. Two (polynomial) objective functions F(x) and H(x) are considered. Given any solution to x
0 in the hypercube, we propose two polynomial-time algorithms based on these formulations, for finding maximal independent sets with cardinality greater than or equal to F(x0) and H(x0), respectively. A relation between the two approaches is studied and a more general statement for dominating sets is proved. Results of preliminary computational experiments for some of the DIMACS clique benchmark graphs are presented. 相似文献