Second Neighborhood via First Neighborhood in Digraphs

Let D be a simple digraph without loops or digons. For any v ? V(D) v\in V(D) , the first out-neighborhood N⁺(v) is the set of all vertices with out-distance 1 from v and the second neighborhood N⁺⁺(v) of v is the set of all vertices with out-distance 2 from v. We show that every simple digraph without loops or digons contains a vertex v such that |N⁺⁺(v)| 3 g|N⁺(v)| |N^{++}(v)|\geq\gamma|N^+(v)| , where % = 0.657298... is the unique real root of the equation 2x³ + x² -1 = 0.     

Contribution to the General Linear Conjugation Problem for A Piecewise Analytic Vector

Establishing an analogy between the theories of Riemann–Hilbert vector problem and linear ODEs, for the n-dimensional homogeneous linear conjugation problem on a simple smooth closed contour Γ partitioning the complex plane into two domains D⁺ and D^? we show that if we know n?1 particular solutions such that the determinant of the size n?1 matrix of their components omitting those with index k is nonvanishing on D⁺ ∪ Γ and the determinant of the matrix of their components omitting those with index j is nonvanishing on Γ ∪ D^? {∞}, where \(k,j = \overline {1,n} \), then the canonical system of solutions to the linear conjugation problem can be constructed in closed form.     

Expanding Neighborhood GRASP for the Traveling Salesman Problem

In this paper, we present the application of a modified version of the well known Greedy Randomized Adaptive Search Procedure (GRASP) to the TSP. The proposed GRASP algorithm has two phases: In the first phase the algorithm finds an initial solution of the problem and in the second phase a local search procedure is utilized for the improvement of the initial solution. The local search procedure employs two different local search strategies based on 2-opt and 3-opt methods. The algorithm was tested on numerous benchmark problems from TSPLIB. The results were very satisfactory and for the majority of the instances the results were equal to the best known solution. The algorithm is also compared to the algorithms presented and tested in the DIMACS Implementation Challenge that was organized by David Johnson.     

A Second Descent Problem for Quadratic Forms

Let F be a field of characteristic different from 2. We discuss a new descent problem for quadratic forms, complementing the one studied by Kahn and Laghribi. More precisely, we conjecture that for any quadratic form q over F and any Im(W(F) W(F(q))), there exists a quadratic form W(F) such that dim 2 dim and _F(q), where F(q) is the function field of the projective quadric defined by q = 0. We prove this conjecture for dim 3 and any q, and get partial results for dim {4, 5,6}. We also give other related results.     

The Parallel Variable Neighborhood Search for the p-Median Problem

The Variable Neighborhood Search (VNS) is a recent metaheuristic that combines series of random and improving local searches based on systematically changed neighborhoods. When a local minimum is reached, a shake procedure performs a random search. This determines a new starting point for running an improving search. The use of interchange moves provides a simple implementation of the VNS algorithm for the p-Median Problem. Several strategies for the parallelization of the VNS are considered and coded in C using OpenMP. They are compared in a shared memory machine with large instances.     

The Arc‐Weighted Version of the Second Neighborhood Conjecture

Seymour conjectured that every oriented simple graph contains a vertex whose second neighborhood is at least as large as its first. Seymour's conjecture has been verified in several special cases, most notably for tournaments by Fisher  6 . One extension of the conjecture that has been used by several researchers is to consider vertex‐weighted digraphs. In this article we introduce a version of the conjecture for arc‐weighted digraphs. We prove the conjecture in the special case of arc‐weighted tournaments, strengthening Fisher's theorem. Our proof does not rely on Fisher's result, and thus can be seen as an alternate proof of said theorem.     

A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

The aim of this paper is to propose an algorithm based on the philosophy of the Variable Neighborhood Search (VNS) to solve Multi Depot Vehicle Routing Problems with Time Windows. The paper has two main contributions. First, from a technical point of view, it presents the first application of a VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results show that the approach is competitive with an existing Tabu Search algorithm with respect to both solution quality and computation times.     

Very Large-Scale Neighborhood Search for the K-Constraint Multiple Knapsack Problem

The K-Constraint Multiple Knapsack Problem (K-MKP) is a generalization of the multiple knapsack problem, which is one of the representative combinatorial optimization problems known to be NP-hard. In K-MKP, each item has K types of weights and each knapsack has K types of capacity. In this paper, we propose several very large-scale neighborhood search (VLSN) algorithms to solve K-MKP. One of the VLSN algorithms incorporates a novel approach that consists of randomly perturbing the current solution in order to efficiently produce a set of simultaneous non-profitable moves. These moves would allow several items to be transferred from their current knapsacks and assigned to new knapsacks, which makes room for new items to be inserted through multi-exchange movements and allows for improved solutions. Computational results presented show that the method is effective, and provides better solutions compared to exact algorithms run for the same amount of time. This paper was written during Dr. Cunha's sabbatical at the Industrial and Systems Engineering Department at the University of Florida, Gainesville as a visiting faculty     

Unimprovable Integral Estimate for Solutions of the Dirichlet Problem for Quasilinear Elliptic Equations of the Second Order in a Neighborhood of an Edge

We obtain an exact estimate for the second derivatives of solutions (in the weight Sobolev norm) of the Dirichlet problem for quasilinear second-order elliptic equations of nondivergence type in a neighborhood of an edge of a domain.     

一类二阶非自治迭代微分方程的初值问题

本文研究二阶非自治迭代泛函微分方程x＇＇（t）=a（t）x（t）+b（t）x（x（t））的强解的存在性及其性态,给出了过区域{（t,x）|0相似文献   

Stability of Displacement to the Second Fundamental Problem in Plane Elasticity

In this article, by using the stability of Cauchy type integral when the smooth perturbation for integral curve and the Sobolev type perturbation for kernel density happen, we discuss the stability of the second fundamental problem in plane elasticity when the smooth perturbation for the boundary of the elastic domain (unit disk) and the Sobolev type perturbation for the displacement happen. And the error estimate of the displacement between the second fundamental problem and its perturbed problem is obtained.     

Seymour's Second Neighborhood Conjecture for Tournaments Missing a Generalized Star

Seymour's Second Neighborhood Conjecture asserts that every digraph (without digons) has a vertex whose first out‐neighborhood is at most as large as its second out‐neighborhood. We prove its weighted version for tournaments missing a generalized star. As a consequence the weighted version holds for tournaments missing a sun, star, or a complete graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:89–94, 2012     

一类二阶迭代泛函微分方程的初值问题(英文)

本文利用Schauder不动点定理,首次研究了一类二阶迭代泛函微分方程x″(t)= x(x(t)),满足初始条件:x′(σ)= 0;x(σ)= σ的强解的存在性及其性态.     

Cauchy Problem to a Type of Second Order Differential-iterative Equation

Abstract The paper studies the behavior and existence of strong solutions to the second or-der functional-iterative differential equation     

Properties of Solutions to the Parabolic Obstacle Problem in a Neighborhood of the Boundary of a Domain

For the parabolic obstacle problem with homogeneous Dirichlet boundary condition the regularity of the free boundary is studied in a neighborhood of the boundary of a domain. Bibliography: 6 titles.     

Asymptotics of a Solution to the Quasiliniear Neumann Problem in a Neighborhood of a Conical Point

The existence of a small solution to the quasilinear Neumann problem is established in a H\"older class with separated asymptotics. The lower-order asymptotic terms are constructed. The homogeneity exponents of these terms turn out to be dependent on the value of the solution at a conical point. Bibliography: 33 titles.     

各向异性网格下二阶椭圆问题的一个混合元形式

提出了二阶椭圆问题的一个混合变分形式,同时证明了Rariart-Thomas元的各向异性插值性质,并给出了单元的对二阶问题的最优误差估计。     

两级定位-路径问题模型及变邻域粒子群算法

为满足B2C电子商务中高效率、低成本配送需求,建立了两级定位-路径问题的三下标车流模型,提出了一种求解该问题的变邻域粒子群算法。该算法引入路径重连思想,将粒子群算法中粒子动态更新设计为当前解的邻域搜索、当前解与个体历史最优解之间的路径重连、当前解与种群历史最优解之间的路径重连;在此基础上,提出变邻域搜索策略,动态改变邻域结构以拓展搜索空间。实验结果表明,该算法能有效求解两级定位-路径问题。