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:
Displaying similar documents to “Approximation Results Toward Nearest Neighbor Heuristic”
Approximation algorithms for the traveling salesman problem with range condition
An Overview on Polynomial Approximation of NP-Hard Problems
Vangelis Th. Paschos (2009)
The Yugoslav Journal of Operations Research
Similarity:
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...
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...
Analysis of an approximation algorithm for scheduling indepentent parallel tasks.
Li, Keqin (1999)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
A discrete approximation of the Weber problem with Euclidean distance
J. Kacprzyk, W. Stańczak (1984)
Applicationes Mathematicae
Similarity:
Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems
Marc Demange, Vangelis Th. Paschos (1999)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Two heuristics for the absolute -center problem in graphs
Ján Plesník (1988)
Mathematica Slovaca
Similarity:
A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set
V. Th. Paschos (1994)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Erratum to the paper "On the Kaczmarz algorithm of approximation in infinite-dimensional spaces" (Studia Math. 148 (2001), 75-86)
Stanisław Kwapień, Jan Mycielski (2006)
Studia Mathematica
Similarity:
A Variable Neighborhood Search Approach for Solving the Maximum Set Splitting Problem
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...