Geometric interpretation of Hamiltonian cycles problem via singularly perturbed Markov decision processes

We consider the Hamiltonian cycle problem (HCP) embedded in a singularly perturbed Markov decision process (MDP). More specifically, we consider the HCP as an optimization problem over the space of long-run state-action frequencies induced by the MDP's stationary policies. We also consider two quadratic functionals over the same space. We show that when the perturbation parameter, ? is sufficiently small the Hamiltonian cycles of the given directed graph are precisely the maximizers of one of these quadratic functionals over the frequency space intersected with an appropriate (single) contour of the second quadratic functional. In particular, all these maximizers have a known Euclidean distance of z _m (?) from the origin. Geometrically, this means that Hamiltonian cycles, if any, are the points in the frequency polytope where the circle of radius z _m (?) intersects a certain ellipsoid.     

Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.     

On inversion and Sobolev estimate results about the weighted Radon transform

In this paper, we derive an inversion of the weighted Radon transform by Fourier transform, Riesz potential, and integral transform. We extend results of Rigaud and Lakhal to the n‐dimensional Euclidean space. Furthermore, we obtain some properties of the weighted Radon transform. Finally, we develop some estimate results of the weighted Radon transform under Sobolev space.     

Approximation theorems by positive linear operators in weighted spaces

In this study, we obtain some Korovkin type approximation theorems by positive linear operators on the weighted space of all real valued functions defined on the real two-dimensional Euclidean space \mathbbR²{\mathbb{R}^2}. This paper is mainly consisted of two parts: a Korovkin type approximation theorem via the concept of A-statistical convergence and a Korovkin type approximation theorem via A{\mathcal {A}}-summability.     

Embedding Tree Metrics into Low-Dimensional Euclidean Spaces

We consider embedding metrics induced by trees into Euclidean spaces with a restricted number of dimensions. We show that any weighted tree T with n vertices and L leaves can be embedded into d -dimensional Euclidean space with ? (L ^1/(d-1) ) distortion. Furthermore, we exhibit an embedding with almost the same distortion which can be computed efficiently. This distortion substantially improves the previous best upper bound of \tilde O (n ^2/d ) and almost matches the best known lower bound of Ω(L ^1/d ) . Received August 17, 1999, and in revised form January 25, 2000.     

Affine Invariant Detection: Edge Maps, Anisotropic Diffusion, and Active Contours

In this paper we undertake a systematic investigation of affine invariant object detection and image denoising. Edge detection is first presented from the point of view of the affine invariant scale-space obtained by curvature based motion of the image level-sets. In this case, affine invariant maps are derived as a weighted difference of images at different scales. We then introduce the affine gradient as an affine invariant differential function of lowest possible order with qualitative behavior similar to the Euclidean gradient magnitude. These edge detectors are the basis for the extension of the affine invariant scale-space to a complete affine flow for image denoising and simplification, and to define affine invariant active contours for object detection and edge integration. The active contours are obtained as a gradient flow in a conformally Euclidean space defined by the image on which the object is to be detected. That is, we show that objects can be segmented in an affine invariant manner by computing a path of minimal weighted affine distance, the weight being given by functions of the affine edge detectors. The gradient path is computed via an algorithm which allows to simultaneously detect any number of objects independently of the initial curve topology. Based on the same theory of affine invariant gradient flows we show that the affine geometric heat flow is minimizing, in an affine invariant form, the area enclosed by the curve.     

Orthomodular lattices in ordered vector spaces

In a partly ordered space the orthogonality relation is defined by incomparability. We define integrally open and integrally semi-open ordered real vector spaces. We prove: if an ordered real vector space is integrally semi-open, then a complete lattice of double orthoclosed sets is orthomodular. An integrally open concept is closely related to an open set in the Euclidean topology in a finite dimensional ordered vector space. We prove: if V is an ordered Euclidean space, then V is integrally open and directed (and is also Archimedean) if and only if its positive cone, without vertex 0, is an open set in the Euclidean topology (and also the family of all order segments , a < b, is a base for the Euclidean topology). Received January 7, 2005; accepted in final form November 26, 2005.     

A weak characterisation of the Delaunay triangulation

We consider a new construction, the weak Delaunay triangulation of a finite point set in a metric space, which contains as a subcomplex the traditional (strong) Delaunay triangulation. The two simplicial complexes turn out to be equal for point sets in Euclidean space, as well as in the (hemi)sphere, hyperbolic space, and certain other geometries. There are weighted and approximate versions of the weak and strong complexes in all these geometries, and we prove equality theorems in those cases also. On the other hand, for discrete metric spaces the weak and strong complexes are decidedly different. We give a short empirical demonstration that weak Delaunay complexes can lead to dramatically clean results in the problem of estimating the homology groups of a manifold represented by a finite point sample.      

Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that, for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions than state-of-the-art algorithms.     

A New Euclidean Tight 6-Design

Euclidean t-designs, which are finite weighted subsets of Euclidean space, were defined by Neumaier-Seidel (1988). A tight t-design is defined as a t-design whose cardinality is equal to the known natural lower bound. In this paper, we give a new Euclidean tight 6-design in ${\mathbb{R}^{22}}$ . Furthermore, we also show its uniqueness up to similar transformation fixing the origin. This design has the structure of coherent configuration, which was defined by Higman, and is obtained from the properties of general permutation groups. We also show that the design is obtained by combining two orbits of McLaughlin simple group.     

On the volume functional of compact manifolds with boundary with constant scalar curvature

We study the volume functional on the space of constant scalar curvature metrics with a prescribed boundary metric. We derive a sufficient and necessary condition for a metric to be a critical point, and show that the only domains in space forms, on which the standard metrics are critical points, are geodesic balls. In the zero scalar curvature case, assuming the boundary can be isometrically embedded in the Euclidean space as a compact strictly convex hypersurface, we show that the volume of a critical point is always no less than the Euclidean volume bounded by the isometric embedding of the boundary, and the two volumes are equal if and only if the critical point is isometric to a standard Euclidean ball. We also derive a second variation formula and apply it to show that, on Euclidean balls and “small” hyperbolic and spherical balls in dimensions 3 ≤ n ≤ 5, the standard space form metrics are indeed saddle points for the volume functional.     

Polygons in Buildings and their Refined Side Lengths

As in a symmetric space of noncompact type, one can associate to an oriented geodesic segment in a Euclidean building a vector valued length in the Euclidean Weyl chamber Δ _euc . In addition to the metric length it contains information on the direction of the segment. In this paper we study restrictions on the Δ _euc -valued side lengths of polygons in Euclidean buildings. The main result is that for thick Euclidean buildings X the set Pn(X){\mathcal{P}n(X)} of possible Δ _euc -valued side lengths of oriented n-gons depends only on the associated spherical Coxeter complex. We show moreover that it coincides with the space of Δ _euc -valued weights of semistable weighted configurations on the Tits boundary ∂ _Tits X. The side lengths of polygons in symmetric spaces of noncompact type are studied in the related paper [KLM1]. Applications of the geometric results in both papers to algebraic group theory are given in [KLM2].     

Pinching of the first eigenvalue of the Laplacian and almost-Einstein hypersurfaces of the Euclidean space

In this article, we prove new pinching theorems for the first eigenvalue λ₁(M) of the Laplacian on compact hypersurfaces of the Euclidean space. These pinching results are associated with the upper bound for λ₁(M) in terms of higher order mean curvatures H _k . We show that under a suitable pinching condition, the hypersurface is diffeomorpic and almost-isometric to a standard sphere. Moreover, as a corollary, we show that a hypersurface of the Euclidean space which is almost-Einstein is diffeomorpic and almost-isometric to a standard sphere.      

A Pair of Explicitly Solvable Singular Stochastic Control Problems

We consider a general model of singular stochastic control with infinite time horizon and we prove a ``verification theorem' under the assumption that the Hamilton—Jacobi—Bellman (HJB) equation has a C <sup>2</sup> solution. In the one-dimensional case, under the assumption that the HJB equation has a solution in W <sub>loc</sub> <sup>2,p</sup>(R) with , we prove a very general ``verification theorem' by employing the generalized Meyer—Ito change of variables formula with local times. In what follows, we consider two special cases which we explicitly solve. These are the formal equivalent of the one-dimensional infinite time horizon LQG problem and a simple example with radial symmetry in an arbitrary Euclidean space. The value function of either of these problems is C ² and is expressed in terms of special functions, and, in particular, the confluent hypergeometric function and the modified Bessel function of the first kind, respectively. Accepted 21 February 1997     

Note on hypergraphs and sphere orders

We show that each partial order ≤ of height 2 can be represented by spheres in Euclidean space, where inclusion represents ≤. If each element has at most k elements under it, we can do this in 2k ? 1-dimensional space. This extends a result (and a method) of Scheinerman for the case k = 2. © 1993 John Wiley & Sons, Inc.     

k-major order in real infinite-dimensional linear space and its application

In this paper,the k-major cone and strict k-major cone in real infinite-dimensional linear space are introduced ,through which the k-major order is defined ,and their properties are also discussed. Therefore ,with the help of them any two elements in real infinite-dimensional linear space can be compared.     

Stochastic programming with incomplete information:a surrey of results on postoptimization and sensitivity analysis

The possibility of successful applications of stochastic programming decision models has been limited by the assumed complete knowledge of the distribution Fof the random parameters as well as by the limited scope of the existing numerical procedures.

We shall give a survey of selected methods which can be used to deal with the incomplete knowledge of the distribution F, namely to study robustness of the optimal solution and the optimal value of the objective function relative to small changes of the underlying distribution and to get error bounds in approximation schemes.     

On the Single-Source Unsplittable Flow Problem

be a capacitated directed graph with a source s and k terminals with demands , . We would like to concurrently route every demand on a single path from s to the corresponding terminal without violating the capacities. There are several interesting and important variations of this unsplittable flow problem. If the necessary cut condition is satisfied, we show how to compute an unsplittable flow satisfying the demands such that the total flow through any edge exceeds its capacity by at most the maximum demand. For graphs in which all capacities are at least the maximum demand, we therefore obtain an unsplittable flow with congestion at most 2, and this result is best possible. Furthermore, we show that all demands can be routed unsplittably in 5 rounds, i.e., all demands can be collectively satisfied by the union of 5 unsplittable flows. Finally, we show that 22.6% of the total demand can be satisfied unsplittably. These results are extended to the case when the cut condition is not necessarily satisfied. We derive a 2-approximation algorithm for congestion, a 5-approximation algorithm for the number of rounds and a -approximation algorithm for the maximum routable demand. Received: July 12, 1998