Approximation algorithms for the traveling salesman problem with range condition
D. Arun Kumar, C. Pandu Rangan (2000)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
D. Arun Kumar, C. Pandu Rangan (2000)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Vangelis Th. Paschos (2009)
The Yugoslav Journal of Operations Research
Similarity:
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...
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...
Li, Keqin (1999)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
J. Kacprzyk, W. Stańczak (1984)
Applicationes Mathematicae
Similarity:
Marc Demange, Vangelis Th. Paschos (1999)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Ján Plesník (1988)
Mathematica Slovaca
Similarity:
V. Th. Paschos (1994)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Stanisław Kwapień, Jan Mycielski (2006)
Studia Mathematica
Similarity:
Matic, Dragan (2012)
Serdica Journal of Computing
Similarity:
This paper presents a Variable neighbourhood search (VNS) approach for solving the Maximum Set Splitting Problem (MSSP). The algorithm forms a system of neighborhoods based on changing the component for an increasing number of elements. An efficient local search procedure swaps the components of pairs of elements and yields a relatively short running time. Numerical experiments are performed on the instances known in the literature: minimum hitting set and Steiner triple systems. Computational...
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...