ALIO/EURO V conference on combinatorial optimization
I. Charon, O. Hudry (2008)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
I. Charon, O. Hudry (2008)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Mario Furnari, Antonio Massarotti (1988)
Stochastica
Similarity:
In this note we discuss some drawbacks of some approaches to the classification of NP-complete optimization problems. Then we analyze the Theory of Analytical Computational Complexity to gain some insight about the notions of approximation and approximate algorithms. We stress the different roles played by these notions within the theories of Analytical and Algebraic Complexity. We finally outline a possible strategy to capture a more useful notion of approximation which is inspired...
Jens Clausen, Jakob Krarup (1995)
The Yugoslav Journal of Operations Research
Similarity:
J.K. Lenstra, A.H.G. Rinnooy (1981)
Qüestiió
Similarity:
This is a tutorial survey of recent results in the area of multiprocessor scheduling. Computational complexity theory provides the framework in which these results are presented. They involve on one hand the development of new polynomial optimization algorithms, and on the other hand the application of the concept of NP-hardness as well as the analysis of approximation algorithms.
Renaud Sirdey, Hervé L. M. Kerivin (2007)
RAIRO - Operations Research
Similarity:
This paper is devoted to the exact resolution of a strongly -hard resource-constrained scheduling problem, the , which arises in relation to the operability of certain high-availability real-time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process move programs, we present a branch-and-cut algorithm along with extensive computational results demonstrating its practical relevance, in terms of both exact...
Roman Dębski (2014)
International Journal of Applied Mathematics and Computer Science
Similarity:
Effective, simulation-based trajectory optimization algorithms adapted to heterogeneous computers are studied with reference to the problem taken from alpine ski racing (the presented solution is probably the most general one published so far). The key idea behind these algorithms is to use a grid-based discretization scheme to transform the continuous optimization problem into a search problem over a specially constructed finite graph, and then to apply dynamic programming to find an...
Clarisse Dhaenens, Patrick Siarry, El-Ghazali Talbi (2008)
RAIRO - Operations Research
Similarity:
Petrica Pop, Corina Pop Sitar (2011)
The Yugoslav Journal of Operations Research
Similarity:
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...
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...
M. Minoux (1987)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity: