Displaying similar documents to “A note on a two dimensional knapsack problem with unloading constraints”

Analysis of a near-metric TSP approximation algorithm

Sacha Krug (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the -metric traveling salesman problem ( -TSP), , the TSP restricted to graphs satisfying the -triangle inequality ({}) ≤ (({}) + ({})), for some cost function and any three vertices . The well-known path matching Christofides algorithm (PMCA) guarantees an approximation ratio of 3 /2 and is the best known algorithm for the -TSP, for 1 ≤  ≤ 2....

Computing and proving with pivots

Frédéric Meunier (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

A simple idea used in many combinatorial algorithms is the idea of . Originally, it comes from the method proposed by Gauss in the 19th century for solving systems of linear equations. This method had been extended in 1947 by Dantzig for the famous simplex algorithm used for solving linear programs. From since, a pivoting algorithm is a method exploring subsets of a ground set and going from one subset to a new one ′ by deleting an element inside and adding an element outside : ′ =  ...

Differential approximation of NP-hard problems with equal size feasible solutions

Jérôme Monnot (2010)

RAIRO - Operations Research

Similarity:

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem  which only differ on a linear transformation of their objective functions. This...

Pointwise constrained radially increasing minimizers in the quasi-scalar calculus of variations

Luís Balsa Bicho, António Ornelas (2014)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

We prove of vector minimizers () =  (||) to multiple integrals ∫ ((), |()|)  on a  ⊂ ℝ, among the Sobolev functions (·) in + (, ℝ), using a  : ℝ×ℝ → [0,∞] with (·) and . Besides such basic hypotheses, (·,·) is assumed to satisfy also...

Trivial Cases for the Kantorovitch Problem

Serge Dubuc, Issa Kagabo, Patrice Marcotte (2010)

RAIRO - Operations Research

Similarity:

Let and be two compact spaces endowed with respective measures and satisfying the condition . Let be a continuous function on the product space . The mass transfer problem consists in determining a measure on whose marginals coincide with and , and such that the total cost be minimized. We first show that if the cost function is decomposable, i.e., can be represented as the sum of two continuous functions defined on and , respectively, then every feasible measure is optimal....

Hydrodynamic limit of a d-dimensional exclusion process with conductances

Fábio Júlio Valentim (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

Fix a polynomial of the form () = + ∑2≤≤    =1 with (1) gt; 0. We prove that the evolution, on the diffusive scale, of the empirical density of exclusion processes on 𝕋 d , with conductances given by special class of functions, is described by the unique weak solution of the non-linear parabolic partial differential equation = ∑    ...

Hereditary properties of words

József Balogh, Béla Bollobás (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Let be a hereditary property of words, , an infinite class of finite words such that every subword (block) of a word belonging to is also in . Extending the classical Morse-Hedlund theorem, we show that either contains at least words of length for every  or, for some , it contains at most words of length for every . More importantly, we prove the following quantitative extension of this result: if has words of length then, for every , it contains at most ⌈( + 1)/2⌉⌈( + 1)/2⌈...

Means in complete manifolds: uniqueness and approximation

Marc Arnaudon, Laurent Miclo (2014)

ESAIM: Probability and Statistics

Similarity:

Let be a complete Riemannian manifold,  ∈ ℕ and  ≥ 1. We prove that almost everywhere on  = ( ,, ) ∈  for Lebesgue measure in , the measure μ ( x ) = N ∑ k = 1 N x k μ ( x ) = 1 N ∑ k = 1 N δ x k has a unique–mean (). As a consequence, if  = ( ,, ) is a -valued random variable with absolutely continuous law, then almost surely (()) has a unique –mean. In particular if ( ...

Upper large deviations for maximal flows through a tilted cylinder

Marie Theret (2014)

ESAIM: Probability and Statistics

Similarity:

We consider the standard first passage percolation model in ℤ for  ≥ 2 and we study the maximal flow from the upper half part to the lower half part (respectively from the top to the bottom) of a cylinder whose basis is a hyperrectangle of sidelength proportional to and whose height is () for a certain height function . We denote this maximal flow by (respectively ). We emphasize the fact that the cylinder may be tilted. We look at the probability that...

Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the complexity of the infinite word associated with the Rényi expansion of in an irrational base . When is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity . For such that is finite we provide a simple description of the structure of special factors of the word . When =1 we show that . In the cases when or max} we show that the first difference of the complexity function takes value in for every , and consequently we determine...

Variational approximation of a functional of Mumford–Shah type in codimension higher than one

Francesco Ghiraldin (2014)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

In this paper we consider a new kind of Mumford–Shah functional () for maps : ℝ → ℝ with  ≥ . The most important novelty is that the energy features a singular set of codimension greater than one, defined through the theory of distributional jacobians. After recalling the basic definitions and some well established results, we prove an approximation property for the energy ()  −convergence, in the same spirit of the work by Ambrosio and Tortorelli [L....

Plug-in estimation of level sets in a non-compact setting with applications in multivariate risk theory

Elena Di Bernardino, Thomas Laloë, Véronique Maume-Deschamps, Clémentine Prieur (2013)

ESAIM: Probability and Statistics

Similarity:

This paper deals with the problem of estimating the level sets () =  {() ≥ }, with  ∈ (0,1), of an unknown distribution function on ℝ . A plug-in approach is followed. That is, given a consistent estimator of , we estimate () by () =  { () ≥ }. In our setting, non-compactness property is required for the level sets to estimate. We state consistency results with respect to the Hausdorff distance and the volume of the symmetric...