Approximation Results Toward Nearest Neighbor Heuristic
Jérôme Monnot (2002)
The Yugoslav Journal of Operations Research
Similarity:
Jérôme Monnot (2002)
The Yugoslav Journal of Operations Research
Similarity:
Vangelis Th. Paschos (2009)
The Yugoslav Journal of Operations Research
Similarity:
D. Arun Kumar, C. Pandu Rangan (2000)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Viet Hung Nguyen (2007)
RAIRO - Operations Research
Similarity:
Given a weighted undirected graph , a tree (respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree (resp. tour) cover problem is of finding a minimum weight tree (resp. tour) cover of . Arkin, Halldórsson and Hassin (1993) give approximation algorithms with factors respectively 3.5 and 5.5. Later Könemann, Konjevod, Parekh, and Sinha (2003) study the linear programming relaxations...
Francesco M. Malvestuto (2012)
Kybernetika
Similarity:
Decomposable (probabilistic) models are log-linear models generated by acyclic hypergraphs, and a number of nice properties enjoyed by them are known. In many applications the following selection problem naturally arises: given a probability distribution over a finite set of discrete variables and a positive integer , find a decomposable model with tree-width that best fits . If is the generating hypergraph of a decomposable model and is the estimate of under the model,...
Marc Demange, Vangelis Th. Paschos (1999)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Štefan Berežný, Vladimír Lacko (2005)
Kybernetika
Similarity:
Suppose a graph whose edges are partitioned into disjoint categories (colors) is given. In the color-balanced spanning tree problem a spanning tree is looked for that minimizes the variability in the number of edges from different categories. We show that polynomiality of this problem depends on the number of categories and present some polynomial algorithm.
Guangting Chen, Rainer E. Burkard (2003)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.