Displaying similar documents to “Fast approximation of minimum multicast congestion – Implementation versus theory”

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

Jérôme Monnot (2002)

RAIRO - Operations Research - Recherche Opérationnelle

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

Approximation of the Snell envelope and american options prices in dimension one

Vlad Bally, Bruno Saussereau (2002)

ESAIM: Probability and Statistics

Similarity:

We establish some error estimates for the approximation of an optimal stopping problem along the paths of the Black–Scholes model. This approximation is based on a tree method. Moreover, we give a global approximation result for the related obstacle problem.

Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut

Francisco Barahona, László Ladányi (2006)

RAIRO - Operations Research

Similarity:

We present a Branch-and-Cut algorithm where the volume algorithm is applied instead of the traditionally used dual simplex algorithm to the linear programming relaxations in the root node of the search tree. This means that we use fast approximate solutions to these linear programs instead of exact but slower solutions. We present computational results with the Steiner tree and Max-Cut problems. We show evidence that one can solve these problems much faster with the volume algorithm...

Improved approximation of the general soft-capacitated facility location problem

Laurent Alfandari (2007)

RAIRO - Operations Research

Similarity:

The soft-capacitated facility location problem, where each facility is composed of a variable number of fixed-capacity production units, has been recently studied in several papers, especially in the metric case. In this paper, we only consider the general problem where connection costs do not systematically satisfy the triangle inequality property. We show that an adaptation of the set covering greedy heuristic, where the subproblem is approximately solved by a fully polynomial-time...