Displaying similar documents to “Semidefinite Programming Based Algorithms for the Sparsest Cut Problem”

Semidefinite Programming Based Algorithms for the Sparsest Cut Problem

Luis A.A. Meira, Flávio K. Miyazawa (2011)

RAIRO - Operations Research

Similarity:

In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum...

Méthodes géométriques et analytiques pour étudier l'application exponentielle, la sphère et le front d'onde en géométrie sous-riemannienne dans le cas Martinet

Bernard Bonnard, Monique Chyba (2010)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

Consider a sub-riemannian geometry (U,D,g) where U is a neighborhood of 0 in R 3, D is a Martinet type distribution identified to ker ω, ω being the 1-form: ω = d z - y 2 2 d x , q=(x,y,z) and g is a metric on D which can be taken in the normal form:...

Finding the principal points of a random variable

Emilio Carrizosa, E. Conde, A. Castaño, D. Romero–Morales (2010)

RAIRO - Operations Research

Similarity:

The -principal points of a random variable with finite second moment are those points in ℝ minimizing the expected squared distance from to the closest point. Although the determination of principal points involves in general the resolution of a multiextremal optimization problem, existing procedures in the literature provide just a local optimum. In this paper we show that standard Global Optimization techniques can be applied.

Exponential convergence of quadrature for integral operators with Gevrey kernels

Alexey Chernov, Tobias von Petersdorff, Christoph Schwab (2011)

ESAIM: Mathematical Modelling and Numerical Analysis

Similarity:

Galerkin discretizations of integral equations in ℝ d require the evaluation of integrals I = ∫ S ( 1 ) ∫ S ( 2 ) g ( x , y ) d y d x where , are -simplices and has a singularity at = . We assume that is Gevrey smooth for ≠ and satisfies bounds for the derivatives which allow algebraic singularities at = . This holds for kernel functions commonly occurring in integral equations. We construct a family of quadrature rules 𝒬 N using function evaluations of which...

Exponential convergence of quadrature for integral operators with Gevrey kernels

Alexey Chernov, Tobias von Petersdorff, Christoph Schwab (2011)

ESAIM: Mathematical Modelling and Numerical Analysis

Similarity:

Galerkin discretizations of integral equations in ℝ d require the evaluation of integrals I = ∫ S ( 1 ) ∫ S ( 2 ) g ( x , y ) d y d x where , are -simplices and has a singularity at = . We assume that is Gevrey smooth for ≠ and satisfies bounds for the derivatives which allow algebraic singularities at = . This holds for kernel functions commonly occurring in integral equations. We construct a family of quadrature rules 𝒬 N using function evaluations of which...