Displaying similar documents to “Editorial”

Comparing notions of approximation.

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

An introduction to multiprocessor scheduling.

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.

A branch-and-cut algorithm for a resource-constrained scheduling problem

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

High-performance simulation-based algorithms for an alpine ski racer's trajectory optimization in heterogeneous computer systems

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

Editorial

Clarisse Dhaenens, Patrick Siarry, El-Ghazali Talbi (2008)

RAIRO - Operations Research

Similarity:

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

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