Displaying similar documents to “Extension of Reverse Elimination Method Through a Dynamic Management of the Tabu List”

Solving multi-agent scheduling problems on parallel machines with a global objective function

F. Sadi, A. Soukhal, J.-C. Billaut (2014)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this study, we consider a scheduling environment with ( ≥ 1) parallel machines. The set of jobs to schedule is divided into disjoint subsets. Each subset of jobs is associated with one agent. The agents compete to perform their jobs on common resources. The objective is to find a schedule that minimizes a global objective function , while maintaining the regular objective function of each agent, , at a level no greater than a fixed value, ...

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 : ′ =  ...

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....

Three tabu search methods for the MI-FAP applied to 802.11 networks

Sacha Varone, Nicolas Zufferey (2009)

RAIRO - Operations Research

Similarity:

Wireless LAN using IEEE 802.11 networks are now widely deployed at home by residential users or in hot spots by telecommunication operators. A hot spot is a place where a set of access points (APs) are located nearby each other and can serve many users. Since perturbations can degrade the quality of the signal, a careful channel assignment to each AP has to be done. Channel assignment of APs at hot spots, and more generally setup configuration and management, is still often done manually....

Inequality-sum: a global constraint capturing the objective function

Jean-Charles Régin, Michel Rueher (2010)

RAIRO - Operations Research

Similarity:

This paper introduces a new method to prune the domains of the variables in constrained optimization problems where the objective function is defined by a sum , and where the integer variables are subject to difference constraints of the form . An important application area where such problems occur is deterministic scheduling with the as optimality criteria. This new constraint is also more general than a sum constraint defined on a set of ordered variables. Classical...

A note on a two dimensional knapsack problem with unloading constraints

Jefferson Luiz Moisés da Silveira, Eduardo Candido Xavier, Flávio Keidi Miyazawa (2013)

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

Similarity:

In this paper we address the two-dimensional knapsack problem with unloading constraints: we have a bin , and a list of rectangular items, each item with a class value in {1,...,}. The problem is to pack a subset of into , maximizing the total profit of packed items, where the packing must satisfy the unloading constraint: while removing one item , items with higher class values can not block . We present a (4 + )-approximation algorithm when the bin is a square. We also present (3 + )-approximation...

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...

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...

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....

Fixed-α and fixed-β efficiencies

Christopher S. Withers, Saralees Nadarajah (2013)

ESAIM: Probability and Statistics

Similarity:

Consider testing :  ∈  against :  ∈  for a random sample , ..., from , where and are two disjoint sets of cdfs on ℝ = (−∞, ∞). Two non-local types of efficiencies, referred to as the fixed- and fixed- efficiencies, are introduced for this two-hypothesis testing situation. Theoretical tools are developed to evaluate these efficiencies for some of the most...

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⌈...